Drawing the longest line segment contained in an area
Inside a rectangle, this line segment would be its diagonal.
Inside a circle, this line segment would be its diameter.
Inside a more "jagged" shape, it would be:
However, suppose we consider an irregular area, such as
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.
Solution 1:
Try this geometric solution:
- 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.
- Place the shape on a coordinate plane so that $O_0$ is at the origin of the coordinate plane.
- Add rays extending from the origin.
- 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.
- Starting from $O_0$, shift the $x$ and $y$ coordinates of the shape so that the origin traverses the exterior edge.
- 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.
- Continue this process until you have traversed the entire shape.
- 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.
- 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.