Algorithm to find the largest inscribed chord of a closed polyline

Question

I'm looking for an algorithm to find the longest chord ("diameter") of a closed polyline. Unfortunately that polyline doesn't have to be convex, but the chord should lie entirely within the curve. Here's an example:

The solution I'm looking for is the dashed red segment.

Can you suggest an efficient algorithm for this? The best we've been able to achieve so far is the N² algorithm that tries all pairs of vertices, but even that seems incorrect since the chord doesn't necessarily pass through two vertices (or does it?).

I'm also interested in the related problem where we are looking for the biggest segment joining two vertices (or the longest part of that segment that lies within the curve if the segment in not fully inscribed). In that case, the N² algorithm works, but is slow for a large number of points.

Answer 1

I think the solution will always include at-least two vertex. So calculating a list all the lines segments between all the vertex, including the one extending to touch another of the polygon's line segment will do the trick.

To calculate if any of the line segment converted to ray will intersect with another line segment see the answer: How do you check for intersection between a line segment and a line ray emanating from a point at an angle from horizontal?

After that check if our list of line segments are fully within the polygon. The following answer will allow you to check that, eliminating the ones going out of bounds. determine if line segment is inside polygon

Now the longest of the remaining should be the answer.