Lin-Canny Algorithm

Lin-Canny: closest features via Voronoi regions

Given two convex polygons, many algorithms (continuous collision detection, distance-based contact handling, path planning) need the pair of points on their boundaries that are closest to each other, together with the separation distance. Testing every vertex/edge of polygon A against every vertex/edge of polygon B directly is only $O(n_A \cdot n_B)$, cheap once, but far too much when this query has to run every single time step for every pair of nearby objects in a simulation. The Lin-Canny algorithm [LC91] instead maintains a single candidate pair of features (a vertex or an edge on each polygon) and updates it incrementally, needing only a handful of tests per step once it has locked on.

Voronoi regions of a convex polygon

Every point in the plane has a uniquely closest feature on a convex polygon's boundary (a vertex or an edge), and the set of points that are closest to a particular feature is called that feature's Voronoi region:

• An edge's Voronoi region is the infinite strip perpendicular to the edge, bounded by the two lines through its endpoints that are perpendicular to it.
• A vertex's Voronoi region is the wedge outside the polygon bounded by the perpendiculars of its two adjacent edges — exactly the two dashed rays drawn from the currently tracked vertex in the simulation.

These regions partition the whole plane (outside the polygon) without gaps or overlaps. Consequently, a candidate feature $f$ is the closest feature to a point $p$ if and only if $p$ lies in $f$'s Voronoi region — a test that only needs the two edges neighboring $f$, not the whole polygon.

The algorithm

Starting from a candidate pair of features $(f_A, f_B)$ (one on each polygon), each iteration performs a simple local check:

1. Compute the closest points $p_A \in f_A$ and $p_B \in f_B$ between the current pair of features (point–point, point–segment or segment–segment, depending on whether $f_A, f_B$ are vertices or edges).
2. Test whether $p_B$ lies in the Voronoi region of $f_A$. If not, $f_A$ cannot be part of the closest pair yet — replace it with the neighboring feature on the side of the violated boundary and repeat from step 1.
3. Otherwise, test whether $p_A$ lies in the Voronoi region of $f_B$. If not, replace $f_B$ with its corresponding neighbor and repeat from step 1.
4. If both regions already contain the other feature's point, the pair $(f_A, f_B)$ is the closest pair of features, and $\|p_A - p_B\|$ is the separation distance.

Because the polygons are convex, this purely local, greedy walk is guaranteed to reach the globally closest pair — it can never get stuck in a wrong local candidate, which is precisely the property the original 1991 paper proves. Compare the "Distance (Lin-Canny)" and "Distance (brute force)" statistics: apart from rare, momentarily unconverged states in step-by-step mode, they always agree, confirming this on every frame.

Why this is fast: temporal coherence

Object shapes and positions rarely change much from one simulation step to the next. If the walk is restarted from the pair found in the previous step ("warm start"), it typically only needs zero to a few iterations to re-converge, since the true closest pair has usually not moved far either. Restarting from an arbitrary fixed feature every time ("cold start") needs far more iterations in general, up to $O(n_A + n_B)$ in the worst case. The "Iterations (warm start)" and "Iterations (cold restart)" statistics make this difference directly measurable: watch how much smaller the warm count stays as the polygons drift and rotate, compared to the cold count computed from scratch for reference on every frame.

Use "Reset walk (cold start)" to throw away the current tracked pair and see how many steps are actually spent recovering it, or switch to step-by-step mode to single-step through the walk and watch each Voronoi-region test and feature update individually.

Properties and limitations

• Expected near-constant cost per step once locked on, versus the $O(n_A \cdot n_B)$ of testing every feature pair — the same "exploit temporal coherence to avoid brute force" idea already used by the axis choice and re-sorting in the sweep and prune broad phase.
• Requires convex polygons (or, in 3D, convex polytopes with a similarly defined Voronoi structure per vertex/edge/face) — the correctness proof relies on convexity.
• Designed for separated objects. This simplified version does not special-case interpenetration; the original algorithm detects when the polygons start to overlap and switches to a separate penetration-depth computation instead of continuing the walk.
• An alternative: the Gilbert–Johnson–Keerthi (GJK) algorithm [GJK88] solves the same closest-distance problem without needing explicit per-feature neighbor connectivity, which makes it easier to generalize to arbitrary convex shapes (not just polygons/polytopes given as an explicit vertex/edge graph).

References

• [LC91] Ming C. Lin, John F. Canny. A Fast Algorithm for Incremental Distance Calculation. In Proceedings of the IEEE International Conference on Robotics and Automation, 1991.
• [GJK88] E. G. Gilbert, D. W. Johnson, S. S. Keerthi. A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space. IEEE Journal of Robotics and Automation, 1988.
• [Eri04] Christer Ericson. Real-Time Collision Detection. Morgan Kaufmann, 2004.