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:

• The connecting lines cannot intersect each other
• The connecting lines cannot intersect the polygons
• The connecting lines can touch lines/vertices of the polygons

Example picture:

Any suggestions?

CodePudding user response：

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).