Turning a simple polygon with holes into exterior-bounded only

Question

I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior boundary only. To overcome this restriction, I plan to “cut through the body of the shape” — joining a pair of nodes of exterior and interior boundary (see figure, left), thus creating a zero-width way into the shape's former interior space that will then technically become exterior (see figure, right).

So the question is: which nodes to join? (Not that it's unacceptable to create new nodes in suitable locations, but undesirable.) An obvious and ideal choice would be the two nodes most close to each other; moreover, I suppose that those would automatically constitute a valid solution — i. e. the new segments won't intersect any existing one. Consequently, the question becomes: how to find the closest node pair?

Googling on this topic yields many results for similar questions which vary in degree of “similarity”, complexity of understanding the algorithm and computational complexity. But most importantly, as far as I noticed, they vary in applicability to input data, — that is, some are designed for convex polygons only, others fail on “overlapping” polygons (I suppose that includes my case, too). So I decided to ask: which algorithms are optimal or at least suitable for my particular task?

Answer 1

The closest vertices between the inner and outer polygons do not necessarily produce a valid solution as shown in the following figure:

You just need to find a pair of vertices between the inner and outer polygons whose corresponding edge does not intersect either polygon. Search for vertices $u$ and $v$ from the inner and outer polygons such that the edge $(u,v)$ does not cross any other edge (some care needs to be taken that you don't slip between two edges as shown on the right above -- choosing the closer vertex avoids this problem).

A straight forward approach would scan all such $u,$ $v,$ and all edges resulting in $O(n^3)$ time in the worst case -- in practice you'll find a solution fairly quickly. This can be sped up by placing all the vertices in a BSP tree whose half-spaces are defined by the polygon edges -- then you only considering vertices $v$ in the same half-space as $u.$

Answer 2

For two sets there is an $O(n \log n)$ (where $n$ is the total number of points) algorithm found by Godfried T. TOUSSAINT and Binay K. BHATTACHARYA in Optimal algorithms for computing the distance between two finite planar sets.

They prove that the edge you are looking for is in the minimum spanning tree and there is algorithms to compute this tree in $O(n \log n)$ in the plane. Then you just have to explore the tree in linear time to find the edge.

It seems to me that this algorithm can be generalized when you have $k$ interiors boundaries : all the $k$ edges you are looking for ($k$ because it's a tree beetween $k+1$ nodes : the exterior and the $k$ interiors) are in the minimum spanning tree. The proof is almost the same that for 2. Thus the running time is still $O(n \log n)$ in worst case.

Since neither your polygons are convex nor their coordinates are integers (?), I think you can't have a better result.