Main homepageRotating Calipers homepagePrevious problemNext problemApplet homepage


Critical support lines

Critical support lines (commonly referred to as CS lines) between two convex polygons are lines tangent to both polygons but such that they lie on opposite sides of the line. In other words, they separate the polygons.
CS lines have applications in motion planning, visibility, range fitting.

Illustrated below are two convex polygons and the two critical support lines between them.
Critical support lines for two convex polygons
Note that assuming the data is given in standard form, CS lines will only intersect the two polygons at two vertices only. Hence, a CS line is determined by a pair of vertices between the polygons.
The following result characterizes this pair:

Given two convex polygons P, Q, two vertices p(i), q(j) (belonging to P and Q respectively) determine a CS line if, and only if:
  1. p(i), q(j) form an anti-podal pair between the polygons.
  2. p(i-1),p(i+1) lie on one side of the line (p(i), q(j)) while q(j-1),q(j+1) lie on the other.
Using this result, the CS lines can easily be determined. Only anti-podal pairs between the polygons need to be checked. Thus, Toussaint proposes to use the Rotating Calipers. Assuming the polygons are given in standard form and clockwise order, consider the following:
  1. Compute the vertex with minimum y coordinate for P (call it yminP) and the vertex with maximum y coordinate for Q (call it ymaxQ).
  2. Construct two lines of support LP and LQ for the polygons at yminP and ymaxQ such that the polygons lie to the right of their respective lines of support. Then LP and LQ have opposite direction, and yminP and ymaxQ form an anti-podal pair between the polygons.
  3. Let p(i)= yminP, and let q(j)= ymaxQ. (p(i), q(j)) form an anti-podal pair between the polygons. Check if p(i-1),p(i+1) lie on one side of the line (p(i), q(j)) and if q(j-1),q(j+1) lie on the other. If so, then (p(i), q(j)) determine a CS line.
  4. Rotate the lines clockwise until one of them coincides with an edge of its polygon.
  5. A new anti-podal pair is determined. If both lines of support coincide with edges, then a total of three anti-podal pairs (combinations of the previous vertices and the new vertices) need to be considered. For all new anti-podal pairs, perform the above checks.
  6. Repeat steps 4 and 5, until the new pair considered is (yminP,ymaxQ).
  7. Output the CS lines.

This algorithm basically rotates the lines of support around the polygons, sequentially finding all anti-podal pairs between them. Every time a pair is determined, all necessary checks are performed. By the above result characterizing CS lines, then all critical support lines are found.
The algorithm's running time is dominated by steps 1 and 6, which take O(n) time each (all checks are done with unit-time cost. Since there are O(n) anti-podal pairs, the total cost is O(n)).

The final operation on convex polygons studied is the vector sums of convex polygons.
Main homepageRotating Calipers homepagePrevious problemNext problemApplet homepage
December 17th, 1998