What I am trying to do is to link all the polygons together by segments in a such way that:
- each of the segments does not intersect any polygons in between (i.e. it connects the "visible" points of the polygon)
- the path along the segments from one polygon to another does not have any loops(if you consider polygons to be the nodes of the graph and the segments to be the edges then the graph has no cycles, i.e. there is a tree of polygons).
At the moment I am solving the problem by brute force search of the segments from each polygon to all the others checking if there is no intersections in between. And then I am using Kruskal algorithm to find a tree, so the path could be constructed. The solution is ok for "simple" polygons but quite time consuming for more complex ones when the number of vertices and polygons is big.
Are there similar problems or better solutions to this problem ?