posdamer@wucs2.UUCP (Jeff Posdamer) (02/18/88)
Over the last year or two, there have been numerous inquiries and
discussions concerning topics in geometric algorithms and geometric
modeling. This raises two thoughts:
Are we ready for a computational geometry new group ? (Please, no flames!!)
Since a computational geometry course was mentioned in a recent note,
Washington University CS teaches CS506-Computational Geometry and
Geometric Modeling (every other year). I would be interested in any
comments or discussion on such courses.
(As a side note, geomtric algorithms are sneaking into some of our intro
courses and have proved of more interest and motivation to students than
some of the more traditional problems.)
Jeff Posdamer
--
Jeff Posdamershington University, St. Louis, MO, (314) 889-6147
UUCP: posdamer@wucs1.UUCP or ...!{ihnp4,seismo}!wucs1!posdamer
ARPANET: wucs1!posdamer@seismo.CSS.GOV (or .ARPA)
CSNET: wucs1!posdamer%seismo.CSS.GOV@csnet-relaymdoerr@incas.UUCP (Michael Doerr) (04/27/89)
Although I've followed nearly all of the Point-In-Polygon and similiar
geometry-related discussions on comp.graphics I've never seen the
following subject discussed before:
How does one determine _reliabely_ (!!!) the winding sense (clockwise
or counter-clockwise) of the sides of an arbitrary polygon?
By arbitrary polygon I mean the interior of a closed region of
the plane that is defined by a circular list of vertices that
are connected by straight line segments. The lines may touch or
(partially) overlap, but mutual intersections are not allowed.
Additionally one vertex may be shared by more than two line segments.
That is, polygons may be convex or concave, but not self-overlapping.
I've come up with the following algorithm and would like to know whether
it is correct:
1. Select an arbitrary vertex of the polgon.
Tranlate the polygon so that this vertex is placed into
the origin (0, 0).
Set SUM = 0.
2. FOR each pair of vertices along the sides of the polygon DO
a) Compute the ANGLE that is subtended by each side with
respect to the reference vertex (selected in step 1).
This usually involves an expensive arctan operation.
b) Compute SUM = SUM + ANGLE
3. IF SUM > 0 THEN winding sense of polygon boundary is CCW
IF SUM < 0 THEN winding sense of polygon boundary is CW
IF SUM == 0 THEN polygon is in some way degenerate (?????)
I hope someone can answer the following questions:
1. Does the above stated algorithm really compute
the correct winding sense?
2. If question 1 has to be answered with NO:
Please send me references, hints, programs, etc.
for a working algorithm.
3. If questions 1 can be answered with YES:
How could the algorithm be improved, so that less
expensive operations are required?
4. In which way is the polygon degenerate, if SUM == 0?
5. Can this algorithm also be applied or extended
to self-overlapping polygons?
Many thanks in advance, Michael.
Michael "The Turtle" Doerr %% /-------\ %%
CS Department (FB Informatik) % o o %
University of Kaiserslautern -{ o o o }==O
D-6750 Kaiserslautern (West Germany) % o o %
uucp: ...!uunet!unido!incas!mdoerr %% \-------/ %%rsb584@leah.Albany.Edu (Raymond S Brand) (04/30/89)
In article <5397@cs.utexas.edu>, atc@cs.utexas.edu (Alvin T. Campbell III) writes: > In article <2053@incas.UUCP> mdoerr@incas.UUCP (Michael Doerr) writes: > > > > How does one determine _reliabely_ (!!!) the winding sense (clockwise > > or counter-clockwise) of the sides of an arbitrary polygon? > > > > I recently had to solve the winding-sense problem myself. > I am glad to see other people have had to deal with it as well. > [ ... ] > > Now for the method. Assume that we have a polygon with n > vertices, numbered v1, v2, ..., vn. First, we find the vertex, > vtop, with the largest y-coordinate. The angle of the polygon > at this vertex is guaranteed to be convex. Now we take the > cross-product of the vectors (vaft, vtop) and (vtop, vbef), > where vaft is the vertex following vtop, and vbef is the vertex > preceding vtop. If the cross-product is negative, the vertices > are counter-clockwise. Otherwise, the vertices are clockwise. > [ ... ] > -- > A. T. Campbell, III > CS Department, University of Texas > atc@cs.utexas.edu I believe that a figure-8 is a permited shape in the original question, but that shape can lead to different answers from your method depending on the orientation of the figure-8. ------------------------------------------------------------------------- Raymond S. Brand rsbx@beowulf.uucp 3A Pinehurst Ave. rsb584@leah.albany.edu Albany NY 12203 FidoNet 1:7729/255 (518-489-8968) (518)-482-8798 BBS: (518)-489-8968 ------------------------------------------------------------------------- Raymond S. Brand rsbx@beowulf.uucp 3A Pinehurst Ave. rsb584@leah.albany.edu Albany NY 12203 FidoNet 1:7729/255 (518-489-8968) (518)-482-8798 BBS: (518)-489-8968 ------------------------------------------------------------------------- Raymond S. Brand rsbx@beowulf.uucp 3A Pinehurst Ave. rsb584@leah.albany.edu Albany NY 12203 FidoNet 1:7729/255 (518-489-8968) (518)-482-8798 BBS: (518)-489-8968
atc@cs.utexas.edu (Alvin T. Campbell III) (04/30/89)
In article <2053@incas.UUCP> mdoerr@incas.UUCP (Michael Doerr) writes: > > How does one determine _reliabely_ (!!!) the winding sense (clockwise > or counter-clockwise) of the sides of an arbitrary polygon? > >I've come up with the following algorithm and would like to know whether >it is correct: > [ALGORITHM DELETED FOR SPACE CONSIDERATIONS} I recently had to solve the winding-sense problem myself. I am glad to see other people have had to deal with it as well. Michael's algorithm looks as if it will work, but it will not be very fast. The method I devised is very simple and fast. I believe it to be robust. My solution is described below, along with source code in C. Now for the method. Assume that we have a polygon with n vertices, numbered v1, v2, ..., vn. First, we find the vertex, vtop, with the largest y-coordinate. The angle of the polygon at this vertex is guaranteed to be convex. Now we take the cross-product of the vectors (vaft, vtop) and (vtop, vbef), where vaft is the vertex following vtop, and vbef is the vertex preceding vtop. If the cross-product is negative, the vertices are counter-clockwise. Otherwise, the vertices are clockwise. /********************************CUT HERE *****************************/ /* file: clockwise.c description: determine if verts of a polygon are specified in clockwise order author: A. T. Campbell date: February 8, 1989 routines: clockwise() */ #include <math.h> #ifndef lint static char sccsid[] = "%W% %G%"; /* SCCS info */ #endif lint /******************************************************************************/ /* constants */ #define FALSE 0 #define TRUE 1 /******************************************************************************/ int clockwise(n, v) /* decide if vertices are clockwise */ int n; /* number of vertices */ float v[][2]; /* list of vertices */ { float *top; /* topmost point */ float *bef; /* point before topmost */ float *aft; /* point after topmost */ float topy; /* highest y coordinate */ float topaft[2]; /* vector from top vert to next */ float topbef[2]; /* vector from top vert to previous */ float prod; /* dot product */ int i; /* loop control */ int aftind; /* index of pnt after top */ int befind; /* index of pnt before top */ int topind; /* index of topmost pnt */ if (n < 3) return(TRUE); /* find topmost point */ topy = -MAXFLOAT; for (i = 0; i < n; i++) if (v[i][1] > topy) { topy = v[i][1]; topind = i; } /* find indices before and after */ befind = (topind > 0)? topind - 1 : n - 1; aftind = (topind < n-1)? topind + 1 : 0; top = &(v[topind][0]); bef = &(v[befind][0]); aft = &(v[aftind][0]); /* calculate vectors */ topaft[0] = aft[0] - top[0]; topaft[1] = aft[1] - top[1]; topbef[0] = bef[0] - top[0]; topbef[1] = bef[1] - top[1]; /* cross-multiply vectors */ prod = topbef[0] * topaft[1] - topbef[1] * topaft[0]; /* if cross-product is positive, then clockwise */ return((prod >= 0.)? TRUE: FALSE); } /******************************************************************************/ -- A. T. Campbell, III CS Department, University of Texas atc@cs.utexas.edu
ksbooth@watcgl.waterloo.edu (Kelly Booth) (04/30/89)
In article <5397@cs.utexas.edu> atc@cs.utexas.edu (Alvin T. Campbell III) writes: >Now for the method. Assume that we have a polygon with n >vertices, numbered v1, v2, ..., vn. First, we find the vertex, >vtop, with the largest y-coordinate. The angle of the polygon >at this vertex is guaranteed to be convex. No. This is a common mistake. The "top" vertex may be co-linear with the previous and next vertices. Then the cross product that this algorithm calculates becomes zero. If the original data had no co-linear vertices, floating-point operations used in the various transformations could result in co-linear vertices. Any transformation to integer-based coordinates runs this risk. For the application here (winding numbers) the algorithm can be fixed by just looking for a vertex of maximum y with a predecessor having a lower y value. But of course this presumes that all of the vertices have "correct" coordinates (i.e., that they have not been mangled by floating-point transformations). There have been many (too many to repeat) postings about this in this newsgroup. Computational geometry problems are deceptively simple to state. The solutions are often quite tricky, and extremely tricky if all of the vagaries of floating-point representation are taken into account. Aside: A similar algorithm is often presented for computing the normal to a polygon (this is in fact what the cross product gives). It fails for the cases above. Newell's formula (you can find it in one of the appendices of Newman & Sproull's text, second edition) gives a much more robust version of this technique. This is more a less a paraphrase of the version in N&S taken from a recent midterm exam. | Newell's formula for determining surface normals of a planar | | polygon is given by | | n | a= > (y -y )(z +z ) | k=0 k k+1 k k+1 | | n | b= > (z -z )(x +x ) | k=0 k k+1 k k+1 | | n | c= > (x -x )(y +y ) | k=0 k k+1 k k+1 | | In these equations, the planar polygon is defined by n vertices | | whose coordinates are (x ,y ,z ), with k ranging from 0 to n-1. | k k k | | The subscript k+1 is evaluted modulo n. The vector (a,b,c) is | | perpendicular to the surface. You can derive Newell's formula from the formula for a cross product and induction on n, the number of vertices (for n=3, Newell's formula IS the cross product). The advantage of Newell's formula is that it is relatively insensitive to perturbations in the coordinate values, since it effectively takes a weighted average of all the cross products you might have computed. The sign of c will give the orientation of the polygon (which is the application on the midterm question -- determining when to cull back-facing polygons). If a, b, and c are subsequently normalized, the true surface normal is obtained.
turk@Apple.COM (Ken "Turk" Turkowski) (05/01/89)
In article <9455@watcgl.waterloo.edu> ksbooth@watcgl.waterloo.edu (Kelly Booth) writes: >You can derive Newell's formula from the formula for a cross product >and induction on n, the number of vertices (for n=3, Newell's formula >IS the cross product). Newell's formula is also related to the area of the polygon projected onto each of the coordinate planes. -- Ken Turkowski @ Apple Computer, Inc., Cupertino, CA Internet: turk@apple.com Applelink: TURKOWSKI1 UUCP: sun!apple!turk
cnsy@vax5.CIT.CORNELL.EDU (05/01/89)
In article <2053@incas.UUCP> mdoerr@incas.UUCP (Michael Doerr) writes: [ ...much about the summation of angles test for calculating the winding number deleted...] > 3. If questions 1 can be answered with YES: > How could the algorithm be improved, so that less > expensive operations are required? Michael, Simply use the most popular inside outside test: move your test point to the origin (along with the polygon, of course), shoot a ray along the +X axis, and count the intersections of this ray with the polygon's line segments. One important case is to consider all vertices with a Y component of zero (after the transform to the origin) to be ABOVE the +X axis: this gets rid of all the special cases where the vertices are on the axis, and still gives the right answer. Comparing line segments is much faster than doing angle summations (are both of the y components of the line segment the same sign? If so, then we know that it won't cross the +X axis. Then, are both of the x components negative? If so, again it won't cross. If both these quick tests fail, then you have to do a little work to get the intersection). Now, about extending this to get the winding number. Marching along the vertex list we look at the sign of the Y component whenever we find that a segment crosses +X. Add this sign to a running total. At the end, if the sum is even, the test point is outside the polygon, else inside. However, the sum is also the winding number, and the sign tells the direction! For example, if you use the usually +X is pointing right, +Y pointing up, then a winding number of +3 would mean three winds in a clockwise direction. For a complete description, see my section in the "Introduction to Ray Tracing" course notes, SIGGRAPH '88, or wait until August for the book by Academic Press. Eric Haines