9

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:

enter image description here

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.

Community
  • 1
  • 1
static_rtti
  • 53,760
  • 47
  • 136
  • 192
  • Have you considered visibility polygon algorithms? https://stackoverflow.com/questions/13429856/find-any-vertex-of-a-polygon-visible-from-other-vertex Don't sure whether it could be useful here. – MBo Jul 05 '17 at 11:18
  • 7
    If I am right, the longest distance between points on two line segments necessarily joins the endpoints (this is not true for the shortest distance). And if the distance is "blocked" by some other polygon edge, the blocking is done by a vertex. So in all cases, the longest segment should go through two vertices. –  Jul 05 '17 at 12:20
  • @YvesDaoust: I agree, this seems to be true. – static_rtti Jul 05 '17 at 12:29
  • Surprisingly this has not yet come up either here or at [math.se], although there are similar questions both places. – AakashM Jul 05 '17 at 12:46
  • just a silly comment but diameter must go through center of curvature which is not possible for inscribing a concave polygon like in your example ... so you want largest chord not the diameter. – Spektre Jul 05 '17 at 12:46
  • @Spektre: center of curvature ?? –  Jul 05 '17 at 12:49
  • @YvesDaoust for planar polyline `center of curve` see [Circular approximation of polygon (or its part)](https://stackoverflow.com/a/27251997/2521214) – Spektre Jul 05 '17 at 12:53
  • @Spektre: this link does not define "a" center of a curve. And I don't think that any of the local curvature centers is mandated to be on a polygon diameter. –  Jul 05 '17 at 12:56

1 Answers1

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.

HelloWorld
  • 158
  • 9
  • Correct, YvesDaoust rounded it up in much less words! – HelloWorld Jul 26 '17 at 08:43
  • Yes, that's what we ended up doing. One remaining unanswered question is, can we be smarter and check only a subset of vertex pairs? Avoiding the O(N²) complexity would be nice. – static_rtti Jul 26 '17 at 10:06