5
$\begingroup$

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

Turning internal boundary into external

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 exiting 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?

$\endgroup$
  • 1
    $\begingroup$ What approaches have you considered? A k-d tree might work nicely. Another approach is a linear scan around the external perimeter: imagine one finger pointing at a node on the external polygon, another finger pointing on a node at the internal polygon; at each step you move the first finger to the next node clockwise around the external polygon, then move the second finger forward so it points to the node on the interior that's closest to your first finger. $\endgroup$ – D.W. Jun 19 '15 at 18:55
4
$\begingroup$

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

enter image description here

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.