15

Inside a rectangle, this line segment would be its diagonal.

enter image description here

Inside a circle, this line segment would be its diameter.

enter image description here

Inside a more "jagged" shape, it would be:

enter image description here

However, suppose we consider an irregular area, such as

enter image description here

The longest possible line segment that can be drawn would not be as intuitive any more. Is there any geometrical approach (hopefully an efficient one) which would allow us to determine this mentioned line segment for any (enclosed) areas, in general?

Just to clarify, the line segment in question is a straight line. The entire line segment must be contained within the area. It cannot cross the boundary.

Yiyuan Lee
  • 14,435
  • Does the line have to be "all-inside" the shape or can it go outside at certain places? – barak manos Jun 27 '14 at 15:15
  • You mean, must be on the edges of the shape (I can't see how the longest line may start or end inside the shape). – barak manos Jun 27 '14 at 15:17
  • I supposed that is true as well :) – Yiyuan Lee Jun 27 '14 at 15:18
  • Perhaps the Convex Hull algorithm embeds the answer to that? – barak manos Jun 27 '14 at 15:19
  • Could you explain how can one implement the mentioned algorithm for this problem? (Hopefully as an answer) – Yiyuan Lee Jun 27 '14 at 15:22
  • Emphasis on perhaps (and to answer your question - no, not really)... – barak manos Jun 27 '14 at 15:23
  • You should be calling it a "line segment" rather than a "line". Is the maximal segment allowed to touch the boundary of the region? For example, in a kidney-shaped region, it is plausible that a maximal segment might be contained in the region but internally tangent to the boundary--is that allowed, or do you require that the segment be contained in the (open) interior of the region? – MPW Jun 27 '14 at 15:37
  • Note that the length of the maximal segments is well defined; but there can be many such maximal segments, as in the case of a regular polygon or a circle. This makes it difficult to set up an algorithm for finding such a segment. – Christian Blatter Jun 27 '14 at 15:48
  • @barakmanos Sorry I made a mistake on the rules earlier on. – Yiyuan Lee Jun 27 '14 at 16:02
  • @MPW Yes it is allowed, as long as the line doesn't cross the boundary. – Yiyuan Lee Jun 27 '14 at 16:07
  • 1
    If we consider only centrally symmetric regions given in polar coordinates as $r\le f(\theta)$, then finding such a segment is equivalent to finding global maximum of $f$, which could be an arbitrary continuous function. There is no efficient algorithm for that (as far as I know). And that's a very special case of the problem you stated. –  Jun 27 '14 at 17:42

1 Answers1

10

Try this geometric solution:

  1. Designate a point on the shape as your starting point, $O_0$. I recommend this be your initial guess for the longest line’s starting/stopping point as seen in the picture. Estimate a starting point
  2. Place the shape on a coordinate plane so that $O_0$ is at the origin of the coordinate plane.Align start point at origin
  3. Add rays extending from the origin. Add sunburst
  4. Add a circle $C_0$, centered at the origin whose radius $r_0$ is equal to the length of the longest uninterrupted ray. Define a point $P_0$ where the circle meets this longest uninterrupted ray. Designate terminal point of longest ray
  5. Starting from $O_0$, shift the $x$ and $y$ coordinates of the shape so that the origin traverses the exterior edge. Traverse the shape
    1. While traversing the edge, if the shape extends beyond the boundary of $C_0$ (point A) check if a new maxline should be drawn by ruling out interrupted rays (such as those in area B). If a ray is uninterrupted from the origin to the farthest edge, draw a new circle centered at the origin with radius $r_1 > r_0$, where $r_1$ is the length of the new longest uninterrupted ray. The point at which this occurred $P_1$ is your new max line end point, and the point at the origin $O_1$ is the starting point. Check other possible maximums
    2. Continue this process until you have traversed the entire shape.
    3. Once fully traversed, the line from $O_i$ to $P_i$ (where $i$ is the newest index) is the longest line that fits in the shape. Finish!
Austin D
  • 478