
Constructing tangents is a fundamental geometric operation. The most efficient algorithms for constructing tangents assume they are to convex objects. However, the tangents for a nonconvex object are the same as the tangents to its convex hull, which can generally be efficiently computed. This month we consider tangents to convex polygons. We discuss two cases:
 Tangents from a point to a convex polygon.
 Tangents between two disjoint convex polygons.
Finding polygon tangents can be viewed as finding extreme vertices of the polygon. Algorithm 14 about Extreme Points of Convex Polygons showed how to find maximum and minimum points. For tangents, we want to find the maximum and minimum in a pencil of lines. By applying similar binary search methods, we can construct fast, time, algorithms to find tangents.
Tangents: Point to Polygon
A straight line is said to touch a circle which, meeting the circle and being produced, does not cut the circle. [Book III, Definition 2]
From a given point to draw a straight line touching a given circle. [Book III, Proposition 17] [Euclid, 300 BC]
A 2D line L is tangent to a polygon when L touches it without crossing its boundary. If L is an infinite line, then it must be external to , and intersect the polygon in either an isolated point (a vertex of ) or a line segment (an edge of ). In both cases, the tangent goes through a vertex of the polygon, and must lie completely on one side of L. Further, there are exactly two tangents from an exterior point to a nondegenerate polygon.
Let the 2D polygon be given by n vertices going counterclockwise (ccw) around the polygon. Also let e_{i} be the ith edge segment from vertex V_{i} to V_{i+1} for i=0,n1; and be the edge vector. We say that point P is inside e_{i} if P is left of the line through e_{i}, otherwise P is outside e_{i}.
Next, let P be an arbitrary point external to . Then, for a vertex V_{i} of , there is an easy test to determine whether the line from P to V_{i} is a tangent. Consider the two edges, e_{i–1} and e_{i}, meeting at V_{i}. If P is inside both of these edges, or outside both edges, then those two edges are on different sides of PV_{i}, and thus PV_{i} cannot be a tangent. On the other hand, if P is inside one edge and outside the other, then PV_{i} is locally tangent to at V_{i}. The two possible cases are shown in the following diagram. For vertex V_{i}, the point P is outside (to the right of) edge e_{i–1} and inside (to the left of) edge e_{i}. Thus, V_{i} gives a rightmost tangent T_{R} from P to . Similarly, for V_{k}, P is inside edge e_{k–1} and outside edge e_{k}; and thus V_{k} is a leftmost tangent T_{L} from P to .
For a convex polygon, as shown, there is exactly one instance of each case, corresponding with the two unique tangents. For a nonconvex polygon, one could first compute the convex hull, and then find the hull's tangents which will also be tangent to the polygon. An advantage of doing this is that the hull generally has significantly fewer vertices than the original polygon. So, if many tangents will be computed to the same polygon, using its convex hull makes sense. This can also be relatively fast since the convex hull of a 2D simple polygon can be quickly computed in time (see Melkman’s Fast Convex Hull for a Simple 2D Polyline).
Alternatively, using a bruteforce algorithm, one could find all local tangents to the original polygon and then use the extreme rightmost and leftmost tangents, T_{R} and T_{L} at extreme right and left vertices V_{R} and V_{L} respectively. This algorithm also takes time.
BruteForce Algorithm
The bruteforce algorithm for finding the tangents to an arbitrary polygon just tests the edge conditions at every vertex of , and thus discovers the two vertices, the rightmost V_{R} and the leftmost V_{L}, giving the tangents from P to . This is an algorithm that is easy to implement, is usually adequate when n is relatively small, and works for nonconvex polygons. Here is pseudocode that works for any polygon:

Input: = {V_{0},V_{1},...,Vn1,V_{n}=V_{0}} is any 2D polygon P = a 2D point
V_{R} = V_{L} = V_{0}; for each vertex V_{i} (i=1,n1) { e_{prev} = (P is left of V_{i1}V_{i}); // left of edge e_{i1} e_{next} = (P is left of V_{i}V_{i+1}); // left of edge e_{i} if ((NOT e_{prev}) and e_{next}) { if (V_{i} is not below V_{R}) // handles nonconvex case V_{R} = V_{i}; } else if (e_{prev} and (NOT e_{next})) { if (V_{i} is not above V_{L}) // handles nonconvex case V_{L} = V_{i}; } }
return tangent points V_{R }and V_{L}


An efficient implementation of this generally useful algorithm is given below in tangent_PointPoly(). Note that if the polygon is known to be convex, then the nonconvex tests indicated can be omitted. However, for convex polygons it is usually better to use a binary search algorithm.
Binary Search Algorithm
For a convex polygon, a faster algorithm to find its tangents uses a binary search on the vertices, the same as Algorithm 14 for Extreme Points of Convex Polygons. This algorithm simply defines an ordering on the polygon's vertices so that the two tangent vertices correspond to the maximum and minimum for the ordering. The natural order is based on lines going through the point P. We say that a vertex V_{i} is above V_{k} relative to P, if V_{k} is left of the line from P to V_{i}, as illustrated in the diagram:
Additionally, an edge e_{i} of is increasing relative to P if V_{i+1} is above V_{i} for this ordering. This is equivalent to the condition that P is right of, and thus is outside, the edge e_{i}. Conversely, e_{i} is decreasing relative to P if V_{i}_{+1} is below V_{i}, which is equivalent to P being inside the edge e_{i}. With these definitions, Algorithm 14 can be directly transcribed to produce a binary search for tangents in time.
Pseudocode for an algorithm that selects the maximum tangent using this new ordering is exactly the same as for the Algorithm 14 extreme point binary search pseudocode. The only difference in the implementation is using a different test for the new order relation. With this algorithm, instead of finding the two tangents simultaneously, the rightmost and leftmost tangents are found separately by running the algorithm twice. Despite this overhead, the convex binary search is more efficient even for very small polygons. Timing tests with our implementation show the break even point to be n=4, a quadrilateral. So, it is generally best to use the binary search algorithm. Our implementation is given below in tangent_PointPolyC().
Tangents: Polygon to Polygon
Next, we will find common tangents between two distinct polygons: with m vertices = {V_{i}} (i=0, m) , and with n vertices = {W_{k}} (k=0, n). Finding these tangents is similar to finding the pointtopolygon tangents, although the algorithm is somewhat more complicated because:
 One must scan the vertices of two distinct polygons in some synchronous manner.
 For two disjoint convex polygons, there are 4 distinct tangents, as illustrated.
There are fast polygontopolygon tangency algorithms when both polygons are convex. For nonconvex polygons one could use a slow bruteforce algorithm; or instead, replace the polygons with their convex hulls. If the polygons are simple, the latter alternative is faster since the two convex hulls can be computed in and time using Melkman’s algorithm, and then the tangents between them can be found in or even time.
BruteForce Algorithm
The simple bruteforce tangency algorithm tests every line that joins a vertex of to a vertex of for tangency with both polygons. Since there are mn vertex pairs, there are mn such lines to test, and this gives an quadratic time algorithm. Although this is slow, it does work for any two polygons whether or not they are convex. However, it is faster and easier to just compute and use the convex hulls of the two polygons.
If even one of the polygons, say , is convex, then this algorithm can be easily improved to time. For each of the m vertices of , the two tangents from it to are found using an pointtoconvex_polygon algorithm. For each m, there are only two lines to test for tangency to . The result is an algorithm that might be useful for some applications.
Linear Search Algorithm
But, if both polygons are convex, then there is a straightforward linear tangency algorithm. The idea of this algorithm is to alternate searching for tangent endpoints between the two polygons, and , until both ends of the line segment simultaneous satisfy the tangency condition. This algorithm was originally described by [Preparata & Hong, 1977] as part of the convex hull divideandconquer algorithm, and is presented by [Boissonnat & Yvinec, 1998] and [O'Rourke, 1998].
The algorithm starts by finding vertices on each polygon that can clearly see the other polygon; that is, the tangents from each point to the other polygon are exterior to both polygons. Then, the endpoints of the line segment joining the vertices are sequentially changed. First one endpoint is sequentially advanced on its polygon until the line segment becomes tangent to that polygon. Then, the endpoint on the other polygon is advanced until the line is tangent to the second polygon. Next, one goes back to the first polygon, and continues with this procedure until the line joining the vertices becomes tangent to both polygons at the same time. The direction in which the vertices are changed determines which of the four tangents will be found. The direction can either be clockwise or counterclockwise on each of the two polygons, and this gives four cases that are associated with the four tangents. For example, in the following diagram, starting with line #1, the algorithm advances clockwise on and counterclockwise on , and . This results in finding line #5 as the tangent T_{RL} which is rightmost on polygon and leftmost on . After initialization, the vertices chosen are always advancing in the same direction, either increasing or decreasing. Thus, there is no backtracking, and there are at most (m+n) vertex pairs and lines to test for tangency, so this is an linear algorithm.
One complication with this algorithm is the need to select two initial vertices, one each from and , that can clearly see the other polygon. This can be done, in time, by selecting vertices that are closest to a separating line between and . However, another alternative is to use the binary search pointtoconvex polygon algorithm. First, select any point from , say V_{0}, and find its upper (or lower) tangent to , say at vertex W_{k}_{0}. Then, from this vertex, find the upper (or lower) tangent to , say at V_{i}_{0}. These two vertices V_{i}_{0} and W_{k}_{0} are very good initial points for the linear search algorithm. Note that, like [Kirkpatrick & Snoeyink, 1995], this approach does not require finding a separating line between and .
An implementation of this algorithm is given below as RLtangent_PolyPolyC() which finds the RightLeft tangent from to . By interchanging the polygons when calling this function, it also finds the LeftRight tangent. A slightly modified routine will also find the RightRight and LeftLeft tangents.
Binary Search Algorithms
There are even faster sublinear time algorithms that do synchronized binary searches on the two polygons. A nested binary search on the two polygons results in a algorithm. Further, both [Overmars & van Leeuwen, 1981] and [Kirkpatrick & Snoeyink, 1995] have described algorithms that find the outer tangents between two convex polygons. The [Kirkpatrick & Snoeyink, 1995] (KS) algorithm is particularly interesting, using a "tentative pruneandsearch" technique of theirs. Their paper, which is downloadable from Snoeyink's web site (see Ref), both describes and analyzes this algorithm in detail, as well as giving a C code implementation in an appendix.
Implementation
Here are some sample "C++" implementations of these algorithms.
// Copyright 2002 softSurfer, 2012 Dan Sunday // This code may be freely used and modified for any purpose // providing that this copyright notice is included with it. // SoftSurfer makes no warranty for this code, and cannot be held // liable for any real or imagined damage resulting from its use. // Users of this code must verify correctness for their application.
// Assume that classes are already given for the objects: // Point with coordinates {float x, y;} //===================================================================
// isLeft(): test if a point is LeftOnRight of an infinite line. // Input: three points P0, P1, and P2 // Return: >0 for P2 left of the line through P0 and P1 // =0 for P2 on the line // <0 for P2 right of the line // See: Algorithm 1 on Area of Triangles inline float isLeft( Point P0, Point P1, Point P2 ) { return (P1.x  P0.x)*(P2.y  P0.y)  (P2.x  P0.x)*(P1.y  P0.y); }
// tests for polygon vertex ordering relative to a fixed point P #define above(P,Vi,Vj) (isLeft(P,Vi,Vj) > 0) // true if Vi is above Vj #define below(P,Vi,Vj) (isLeft(P,Vi,Vj) < 0) // true if Vi is below Vj //===================================================================
// tangent_PointPoly(): find any polygon's exterior tangents // Input: P = a 2D point (exterior to the polygon) // n = number of polygon vertices // V = array of vertices for any 2D polygon with V[n]=V[0] // Output: *rtan = index of rightmost tangent point V[*rtan] // *ltan = index of leftmost tangent point V[*ltan] void tangent_PointPoly( Point P, int n, Point* V, int* rtan, int* ltan ) { float eprev, enext; // V[i] previous and next edge turn direction
*rtan = *ltan = 0; // initially assume V[0] = both tangents eprev = isLeft(V[0], V[1], P); for (int i=1; i<n; i++) { enext = isLeft(V[i], V[i+1], P); if ((eprev <= 0) && (enext > 0)) { if (!below(P, V[i], V[*rtan])) *rtan = i; } else if ((eprev > 0) && (enext <= 0)) { if (!above(P, V[i], V[*ltan])) *ltan = i; } eprev = enext; } return; } //===================================================================
// tangent_PointPolyC(): fast binary search for tangents to a convex polygon // Input: P = a 2D point (exterior to the polygon) // n = number of polygon vertices // V = array of vertices for a 2D convex polygon with V[n] = V[0] // Output: *rtan = index of rightmost tangent point V[*rtan] // *ltan = index of leftmost tangent point V[*ltan] void tangent_PointPolyC( Point P, int n, Point* V, int* rtan, int* ltan ) { *rtan = Rtangent_PointPolyC(P, n, V); *ltan = Ltangent_PointPolyC(P, n, V); }
// Rtangent_PointPolyC(): binary search for convex polygon right tangent // Input: P = a 2D point (exterior to the polygon) // n = number of polygon vertices // V = array of vertices for a 2D convex polygon with V[n] = V[0] // Return: index "i" of rightmost tangent point V[i] int Rtangent_PointPolyC( Point P, int n, Point* V ) { // use binary search for large convex polygons int a, b, c; // indices for edge chain endpoints int upA, dnC; // test for up direction of edges a and c
// rightmost tangent = maximum for the isLeft() ordering // test if V[0] is a local maximum if (below(P, V[1], V[0]) && !above(P, V[n1], V[0])) return 0; // V[0] is the maximum tangent point
for (a=0, b=n;;) { // start chain = [0,n] with V[n]=V[0] c = (a + b) / 2; // midpoint of [a,b], and 0<c<n dnC = below(P, V[c+1], V[c]); if (dnC && !above(P, V[c1], V[c])) return c; // V[c] is the maximum tangent point
// no max yet, so continue with the binary search // pick one of the two subchains [a,c] or [c,b] upA = above(P, V[a+1], V[a]); if (upA) { // edge a points up if (dnC) // edge c points down b = c; // select [a,c] else { // edge c points up if (above(P, V[a], V[c])) // V[a] above V[c] b = c; // select [a,c] else // V[a] below V[c] a = c; // select [c,b] } } else { // edge a points down if (!dnC) // edge c points up a = c; // select [c,b] else { // edge c points down if (below(P, V[a], V[c])) // V[a] below V[c] b = c; // select [a,c] else // V[a] above V[c] a = c; // select [c,b] } } } }
// Ltangent_PointPolyC(): binary search for convex polygon left tangent // Input: P = a 2D point (exterior to the polygon) // n = number of polygon vertices // V = array of vertices for a 2D convex polygon with V[n]=V[0] // Return: index "i" of leftmost tangent point V[i] int Ltangent_PointPolyC( Point P, int n, Point* V ) { // use binary search for large convex polygons int a, b, c; // indices for edge chain endpoints int dnA, dnC; // test for down direction of edges a and c
// leftmost tangent = minimum for the isLeft() ordering // test if V[0] is a local minimum if (above(P, V[n1], V[0]) && !below(P, V[1], V[0])) return 0; // V[0] is the minimum tangent point
for (a=0, b=n;;) { // start chain = [0,n] with V[n] = V[0] c = (a + b) / 2; // midpoint of [a,b], and 0<c<n dnC = below(P, V[c+1], V[c]); if (above(P, V[c1], V[c]) && !dnC) return c; // V[c] is the minimum tangent point
// no min yet, so continue with the binary search // pick one of the two subchains [a,c] or [c,b] dnA = below(P, V[a+1], V[a]); if (dnA) { // edge a points down if (!dnC) // edge c points up b = c; // select [a,c] else { // edge c points down if (below(P, V[a], V[c])) // V[a] below V[c] b = c; // select [a,c] else // V[a] above V[c] a = c; // select [c,b] } } else { // edge a points up if (dnC) // edge c points down a = c; // select [c,b] else { // edge c points up if (above(P, V[a], V[c])) // V[a] above V[c] b = c; // select [a,c] else // V[a] below V[c] a = c; // select [c,b] } } } } //===================================================================
// RLtangent_PolyPolyC(): get the RL tangent between two convex polygons // Input: m = number of vertices in polygon 1 // V = array of vertices for convex polygon 1 with V[m]=V[0] // n = number of vertices in polygon 2 // W = array of vertices for convex polygon 2 with W[n]=W[0] // Output: *t1 = index of tangent point V[t1] for polygon 1 // *t2 = index of tangent point W[t2] for polygon 2 void RLtangent_PolyPolyC( int m, Point* V, int n, Point* W, int* t1, int* t2 ) { int ix1, ix2; // search indices for polygons 1 and 2
// first get the initial vertex on each polygon ix1 = Rtangent_PointPolyC(W[0], m, V); // right tangent from W[0] to V ix2 = Ltangent_PointPolyC(V[ix1], n, W); // left tangent from V[ix1] to W
// pingpong linear search until it stabilizes int done = FALSE; // flag when done while (done == FALSE) { done = TRUE; // assume done until... while (isLeft(W[ix2], V[ix1], V[ix1+1]) <= 0){ ++ix1; // get Rtangent from W[ix2] to V } while (isLeft(V[ix1], W[ix2], W[ix21]) >= 0){ ix2; // get Ltangent from V[ix1] to W done = FALSE; // not done if had to adjust this } } *t1 = ix1; *t2 = ix2; return; } //===================================================================
References
JeanDaniel Boissonnat & Mariette Yvinec, Algorithmic Geometry, Chap 9 "Convex Hulls" (1998)
Euclid, The Elements, Alexandria (300 BC)
Thomas Heath, The Thirteen Books of Euclid's Elements, Vol 2 (Books IIIIX) (1956)
David Kirkpatrick & Jack Snoeyink, "Computing Common Tangents without a Separating Line", Workshop on Algorithms and Data Structures, 183193 (1995) [downloadable with C code from http://www.cs.ubc.ca/spider/snoeyink/papers/nosep.ps.gz ]
Joseph O'Rourke, Computational Geometry in C (2nd Edition), Sects 3.73.8, 8895 (1998)
Mark Overmars & J. van Leeuwen, "Maintenance of configurations in the plane", J. Comput. Sys. Sci. 23, 166204 (1981)
Franco Preparata & S.J. Hong, "Convex Hulls of Finite Sets of Points in Two and Three Dimensions", Comm ACM 20, 8793 (1977)
