See Amato, Nancy M (1994) for details of the difference between separation (sigma: σ) and closest visible vertex (CVV).
Refer to P
and Q
as the two polygons with n
and m
vertices, respectively.
For the purposes of this discussion, a key insight is that it is enough to find the closest edge to each vertex in order to compute the minimum separation between P
and Q
.
This means iterating over all vertices, and finding a nearest neighbour. Thus, a time complexity in O((m + n) * log(m * n))
should be expected.
It should be noted that the minimum distance involves at least one vertex:
- If the nearest edges of each polygon are parallel, you can slide along the edges so that one of the points is a vertex of one of the polygons
- if not, it is obvious that one of the points is a vertex of one of the polygons.
In order to locate vertices of Q
within P
, we compute a triangulation of P
such that edges of P
are edges of the triangulation. This is known as a constrained triangulation:
- First, a Delaunay triangulation is built from the vertices of
P
- Edges of
P
are inserted one by one by removing triangles from the triangulation - Building this triangulation has an output sensitive complexity: constraining an edge of the polygon has a cost proportional to the number of triangles which must be removed.
The triangulation should include a special vertex called the infinite vertex, which easily allows the convex hull of the vertices of the triangulation to be found. This will help to determine if a located point q
is inside or outside P
.
This step is necessary to determine whether a vertex is inside or outside P
.
-
First find a vertex of
P
belonging to an “infinite” edge (i.e., the edge includes the “infinite” vertex) -
From this vertex, find an “infinite” triangle, tag it as outside
P
. -
Iterate over the triangles which share a common edge with this triangle, such that triangles contain either an edge of
P
or two vertices belonging toP
- Also tag these triangles as outside
P
; they are the triangles comprising the non-convex vertices ofP
. This operation should be O(n) since triangles have only three neighbour triangles, and always have a vertex ofP
as vertex
- Also tag these triangles as outside
- For each vertex
q
ofQ
, check whether it is contained in one of the triangles tagged as outside:- If
q
is not contained within any of the triangles the algorithm terminates: the distance is 0, sinceP
andQ
intersect
- If
- If
q
is contained within one of the triangles:- Compute the distance between
q
and each edge and each vertex of the triangle, storing the minimum distance.
- Compute the distance between
The minimum distance between vertices of Q
and P
has now been calculated.
Repeat the operation, reversing the role of the polygons:
- The triangulation of
Q
is computed and the closest vertexp
ofP
toQ
is calculated. - The minimum Polygon distance is the minimum distance between this operation and the minimum distance found in Step 3.