An algorithm for determining the minimum distance between two non-convex polygons

minimum_polygon_distance.md

Adapted from https://www.quora.com/How-do-you-compute-the-distance-between-two-non-convex-polygons-in-linear-time/answer/Tom-Dreyfus

Calculating the Minimum Distance Between Two Non-Convex Polygons

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.

Step 1

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.

Step 2: Tagging Triangles of the Triangulation as Interior or Exterior.

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 to P

  • Also tag these triangles as outside P; they are the triangles comprising the non-convex vertices of P. This operation should be O(n) since triangles have only three neighbour triangles, and always have a vertex of P as vertex

Step 3: Locating and Computing Distances

• For each vertex q of Q, 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, since P and Q intersect
• 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.

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 vertex p of P to Q is calculated.
• The minimum Polygon distance is the minimum distance between this operation and the minimum distance found in Step 3.