CODEWITHSUNDEEP
algorithmgeometrypolygon
mbison
mbison

Reputation: 137

Algorithm for connecting 2D polygons without intersections

I'm looking for an algorithm that generates lines (or polylines if needed) that connect polygons.

Input: contains N polygons with coordinates for their vertices. The polygons are not intersecting, but may be inside each other.
Output: Vertices for N-1 lines (or polylines if necessary) connecting

Rules:

Example picture:

Blue lines: input polygons, Red lines: connecting lines/polylines

Any suggestions?

Upvotes: 1

Views: 297

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Borrowing a trick from Kruskal's playbook, while there is more one polygon,

  1. Find the closest pair of polygons (in general, a polygon can actually be a set of polygons with connecting bridges);

  2. Connect them at their closest points with a straight line segment.

By taking the closest connection we can guarantee that its interior doesn't touch anything it shouldn't (otherwise the crossing would yield a shorter connection).

Upvotes: 3

Related Questions