Algorithm 14
|
|
|
 |
| Input: L
= {V0,V1,...,Vn-1,Vn=V0}
is any 2D polygon P = a 2D point
VR = VL = V0; |
An efficient implementation of this generally useful algorithm is given below in tangent_PointPoly(). Note that if the polygon L 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.
For a convex polygon, a faster algorithm to find its tangents uses a binary search on the vertices, the same as Algorithm 13 about 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 L 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 13 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 Dec 2001 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().
We now want to find common tangents to two distinct polygons: L with m vertices = {Vi} (i=0, m) , and W 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:
One must scan the vertices of two distinct polygons in some synchronous manner.
There are 4 distinct tangents for two disjoint convex polygons, as illustrated.
There are fast polygon-to-polygon tangency algorithms are 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, and then their tangents can also be found in O(m+n) or even O(log(m+n)) time.
The simple brute-force tangency algorithm tests every line that joins a vertex of L to a vertex of W 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 would be faster and easier to just compute and use the convex hulls of the two polygons.
If even one of the polygons, say W, is convex, then this algorithm can be easily improved to O(m log n) time. For each of the m vertices of L, the two tangents from it to W 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 L. The result is an O(m log n) algorithm that might be useful for some applications.
However, if both polygons are convex, 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, L and W, 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 counterclockwise on the first polygon L, and clockwise on W. This results in finding line #5 as the tangent TRL which is rightmost on polygon L and leftmost on W. 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, making this is an O(m+n) linear algorithm.
One complication with this algorithm is the need to select two initial vertices, one each from L and W, that can clearly see the other polygon. This is typically done, in O(log(mn)) time, by selecting vertices that are closest to a separating line between L and W. However, another alternative is to use the binary search point-to-convex polygon algorithm. First, select any point from L, say V0, and find its upper (or lower) tangent to W, say at vertex Wk0. Then, from this vertex, find the upper (or lower) tangent to L, 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 L and W.
An easy implementation of this algorithm is given below as RLtangent_PolyPolyC() which finds the Right-Left tangent from L to W. 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.
There are fast sublinear 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.
Here are some sample "C++" implementations of these algorithms.
// Copyright 2002, softSurfer (www.softsurfer.com)
// 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: the January 2001
Algorithm 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(): binary search for convex polygon tangents
// 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;
}
//===================================================================
Jean-Daniel Boissonnat & Mariette Yvinec, Algorithmic Geometry, Chap 9 "Convex Hulls" (1998)
Euclid, The Elements, Alexandria (300 BC)
Gail Kay Haines & 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 ©
2001-2006 softSurfer. All rights reserved. |
