Logo_iSurf_org

Subscribe
to eAlerts

for Geom Site
Updates

CLICK HERE

 

Tangents to & between 2D Polygons

by Dan Sunday

 

 

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:

  1. Tangents from a point to a convex polygon.
  2. 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, O(log-n) 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 OMEGA when L touches OMEGA it without crossing its boundary. If L is an infinite line, then it must be external to OMEGA, and intersect the polygon in either an isolated point (a vertex of OMEGA) or a line segment (an edge of OMEGA). In both cases, the tangent goes through a vertex of the polygon, and OMEGA 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 OMEGA be given by n vertices V0,V1,..,Vn-1,Vn=V0 going counterclockwise (ccw) around the polygon. Also let ei be the i-th edge segment from vertex Vi to Vi+1 for i=0,n-1; and evi=Vi+1-Vi be the edge vector. We say that point P is inside ei if P is left of the line through ei, otherwise P is outside ei.

Next, let P be an arbitrary point external to OMEGA. Then, for a vertex Vi of OMEGA, there is an easy test to determine whether the line from P to Vi is a tangent. Consider the two edges, ei–1 and ei, meeting at Vi. If P is inside both of these edges, or outside both edges, then those two edges are on different sides of PVi, and thus PVi cannot be a tangent. On the other hand, if P is inside one edge and outside the other, then PVi is locally tangent to OMEGA at Vi. The two possible cases are shown in the following diagram. For vertex Vi, the point P is outside (to the right of) edge ei–1 and inside (to the left of) edge ei. Thus, Vi gives a rightmost tangent TR from P to OMEGA. Similarly, for Vk, P is inside edge ek–1 and outside edge ek; and thus Vk is a leftmost tangent TL from P to OMEGA.

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 O(n)  time (see Melkman’s Fast Convex Hull for a Simple 2D Polyline).

Alternatively, using a brute-force algorithm, one could find all local tangents to the original polygon and then use the extreme rightmost and leftmost tangents, TR and TL at extreme right and left vertices VR and VL respectively. This algorithm also takes O(n) time.


Brute-Force Algorithm

The brute-force algorithm for finding the tangents to an arbitrary polygon just tests the edge conditions at every vertex of OMEGA, and thus discovers the two vertices, the rightmost VR and the leftmost VL, giving the tangents from P to OMEGA. This is an O(n) algorithm that is easy to implement, is usually adequate when n is relatively small, and works for nonconvex polygons. Here is pseudo-code that works for any polygon:

Input: OMEGA = {V0,V1,...,Vn-1,Vn=V0}  is any 2D polygon
       P = a 2D point

VR = VL = V0;
for each vertex Vi (i=1,n-1)
{
    eprev = (P is left of Vi-1Vi);    // left of edge ei-1
    enext = (P is left of ViVi+1);    // left of edge ei
    if ((NOT eprev) and enext) {
        if (Vi is not below VR)     // handles nonconvex case
            VR = Vi;
    }
    else if (eprev and (NOT enext)) {
        if (Vi is not above VL)     // handles nonconvex case
            VL = Vi;
    }
}

return tangent points VR and VL

 

An efficient implementation of this generally useful algorithm is given below in tangent_PointPoly(). Note that if the polygon OMEGA 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 Vi is above Vk relative to P, if Vk is left of the line from P to Vi, as illustrated in the diagram:

Additionally, an edge ei of OMEGA is increasing relative to P if Vi+1 is above Vi for this ordering. This is equivalent to the condition that P is right of, and thus is outside, the edge ei. Conversely, ei is decreasing relative to P if Vi+1 is below Vi, which is equivalent to P being inside the edge ei. With these definitions, Algorithm 14 can be directly transcribed to produce a binary search for tangents in O(log-n) time.

Pseudo-code 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 pseudo-code. 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: LAMBDA with m vertices = {Vi} (i=0, m) , and OMEGA with n vertices = {Wk} (k=0, n). Finding these tangents is similar to finding the point-to-polygon tangents, although the algorithm is somewhat more complicated because:

  1. One must scan the vertices of two distinct polygons in some synchronous manner.
  2. For two disjoint convex polygons, there are 4 distinct tangents, as illustrated.

There are fast polygon-to-polygon tangency algorithms when both polygons are convex. For nonconvex polygons one could use a slow brute-force 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 O(m) and O(n) time using Melkman’s algorithm, and then the tangents between them can be found in O(m+n) or even O(log(m+n)) time.


Brute-Force Algorithm

The simple brute-force tangency algorithm tests every line that joins a vertex of LAMBDA to a vertex of OMEGA for tangency with both polygons. Since there are mn vertex pairs, there are mn such lines to test, and this gives an O(mn) 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 OMEGA, is convex, then this algorithm can be easily improved to O(m.log-n) time. For each of the m vertices of LAMBDA, the two tangents from it to OMEGA are found using an O(log-n) point-to-convex_polygon algorithm. For each m, there are only two lines to test for tangency to LAMBDA. The result is an O(m.log-n) algorithm that might be useful for some applications.


Linear Search Algorithm

But, if both polygons are convex, then there is a straightforward linear O(m+n) tangency algorithm. The idea of this algorithm is to alternate searching for tangent endpoints between the two polygons, LAMBDA and OMEGA, 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 divide-and-conquer 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 OMEGA and counterclockwise on LAMBDA, and . This results in finding line #5 as the tangent TRL which is rightmost on polygon LAMBDA and leftmost on OMEGA. 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 O(m+n) linear algorithm.

One complication with this algorithm is the need to select two initial vertices, one each from LAMBDA and OMEGA, that can clearly see the other polygon. This can be done, in O(log(mn)) time, by selecting vertices that are closest to a separating line between LAMBDA and OMEGA. However, another alternative is to use the binary search point-to-convex polygon algorithm. First, select any point from LAMBDA, say V0, and find its upper (or lower) tangent to OMEGA, say at vertex Wk0. Then, from this vertex, find the upper (or lower) tangent to LAMBDA, say at Vi0. These two vertices Vi0 and Wk0 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 LAMBDA and OMEGA.

An implementation of this algorithm is given below as RLtangent_PolyPolyC() which finds the Right-Left tangent from LAMBDA to OMEGA. By interchanging the polygons when calling this function, it also finds the Left-Right tangent. A slightly modified routine will also find the Right-Right and Left-Left 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 O(log(m)log(n)) algorithm. Further, both [Overmars & van Leeuwen, 1981] and [Kirkpatrick & Snoeyink, 1995] have described O(log(m+n)) algorithms that find the outer tangents between two convex polygons. The [Kirkpatrick & Snoeyink, 1995] (KS) algorithm is particularly interesting, using a "tentative prune-and-search" 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 Left|On|Right 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[n-1], 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[c-1], 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[n-1], 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[c-1], 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

    // ping-pong 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[ix2-1]) >= 0){
            --ix2;                       // get Ltangent from V[ix1] to W
            done = FALSE;                // not done if had to adjust this
        }
    }
    *t1 = ix1;
    *t2 = ix2;
    return;
}
//===================================================================
 


References

Jean-Daniel 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 III-IX) (1956)

David Kirkpatrick & Jack Snoeyink, "Computing Common Tangents without a Separating Line", Workshop on Algorithms and Data Structures, 183-193 (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.7-3.8, 88-95 (1998)

Mark Overmars & J. van Leeuwen, "Maintenance of configurations in the plane", J. Comput. Sys. Sci. 23, 166-204 (1981)

Franco Preparata & S.J. Hong, "Convex Hulls of Finite Sets of Points in Two and Three Dimensions", Comm ACM 20, 87-93 (1977)

 

© Copyright 2012 Dan Sunday, 2001 softSurfer