Hi folks. I have an application where I need to process a polygon. The polygon is given as a list of points that tracks the boundary of the polygon. There are two tests that must be done befoe I can do my processing: 1) Ensure that the polygon is simple 2) Ensure that the points track the outline in the counter clockwise direction. A naive test for question 1) would be to test the line segments for intersections. If no intersections are found, the polygon is simple. (If somebody knows of a simpler test, please let me know.) But what about question 2)? Any suggestions? Rune
Playing polygon games
Started by ●March 11, 2010
Reply by ●March 11, 20102010-03-11
Rune Allnor wrote:> Hi folks. > > I have an application where I need to process a polygon. > The polygon is given as a list of points that tracks the > boundary of the polygon. There are two tests that must > be done befoe I can do my processing: > > 1) Ensure that the polygon is simple > 2) Ensure that the points track the outline in the counter > clockwise direction. > > A naive test for question 1) would be to test the line segments > for intersections. If no intersections are found, the polygon is > simple. > (If somebody knows of a simpler test, please let me know.) > > But what about question 2)? Any suggestions?May the polygon be reentrant? Is there a point known to be inside the polygon? Think line integrals. Jerry -- Physics is like sex: sure, it may give some practical results, but that's not why we do it. -- Richard P. Feynman (Nobel Prize, Physics) ������������������������������������������������������������������������
Reply by ●March 11, 20102010-03-11
On 11 Mar, 11:38, Jerry Avins <j...@ieee.org> wrote:> Physics is like sex: sure, it may give some practical results, but > that's not why we do it. � -- Richard P. Feynman (Nobel Prize, Physics)Where do you get these quotes from? Rune
Reply by ●March 11, 20102010-03-11
On 11/03/2010 3:25 AM, Rune Allnor wrote:> Hi folks. > > I have an application where I need to process a polygon. > The polygon is given as a list of points that tracks the > boundary of the polygon. There are two tests that must > be done befoe I can do my processing: > > 1) Ensure that the polygon is simple > 2) Ensure that the points track the outline in the counter > clockwise direction. >Perhaps the CGAL library would be of use for your application? http://www.cgal.org Checking if the polygon is simple: http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Polygon/Chapter_main.html HTH, Nicholas
Reply by ●March 11, 20102010-03-11
Rune Allnor wrote:> On 11 Mar, 11:38, Jerry Avins <j...@ieee.org> wrote: > >> Physics is like sex: sure, it may give some practical results, but >> that's not why we do it. -- Richard P. Feynman (Nobel Prize, Physics) > > Where do you get these quotes from? > > RuneWhen I come across a quote I like, I write it down. Some, like the one below, I made up. I read "I view the progress of science as being the slow erosion of the tendency to dichotomize" in a printed interview and got Prof. Smuts' permission to quote her. (She is a remarkable researcher*. Google will confirm that.) Ask a simple question; learn more than you wanted to know! Jerry ______________________________ * She once followed a troop of wild gorillas around to study their social organization. Once, when they stopped for the usual mid-day siesta, she fell asleep and woke to find that the troop had departed. She didn't know the way back. It turned out that an adolescent male had remained behind, and he led her to the rest of the troop. -- Why am I in a handbasket? Where are we going? �����������������������������������������������������������������������
Reply by ●March 11, 20102010-03-11
On Mar 11, 4:25�am, Rune Allnor <all...@tele.ntnu.no> wrote:> Hi folks. > > I have an application where I need to process a polygon. > The polygon is given as a list of points that tracks the > boundary of the polygon. There are two tests that must > be done befoe I can do my processing: > > 1) Ensure that the polygon is simple > 2) Ensure that the points track the outline in the counter > � �clockwise direction. > > A naive test for question 1) would be to test the line segments > for intersections. If no intersections are found, the polygon is > simple. > (If somebody knows of a simpler test, please let me know.) > > But what about question 2)? Any suggestions? > > RuneHello Rune, Think of your points as being on an x-y plane and then looking at 3 consecutive points (p1,p2,p3) at a time (yes I'm thinking in terms of vectors). 1st decide if they describe a straight line - i.e., p3-p2 = k*(p2-p1) where k is a scalar and if not a straight line then calculate the z component of the cross product of (p3-p2) and (p2-p1) and the sign will tell you which way the bend is: ccw or cw. For example: p1 = (1,0) p2 = (2,0) p3 = (3,3) So 1st looking for colinearity we have the 2 eqns (3-2) = k*(2-1) -> k=1 and (3-0) = k*(0-0) -> k has no unique solution and the"k" values for these 2 relationships by being different from each other show the points are not colinear. If the k values are consistant, watch out for negative k which means the line back treacks on top of itself. Then let's find the z component of the curl So extending the 3 popints to 3 dimensions (set z ==0) p1=1,0,0 p2=2,0,0 p3=3,3,0 p3-p2=1,3,0 p2-p1=1,0,0 The z component of the cross product of (p3-p2) cross (p2-p1) = -3 The sign is negative, thus the bend is ccw. This will be quite easy to implement in c++, have fun. Instead of the colinearity test you can go directly to the curl test, but then you can't tell 0 degree bends from 180 deg bends as they will both result in 0 for the z component of the cross product. IHTH, Clay
Reply by ●March 11, 20102010-03-11
Rune Allnor wrote:> A naive test for question 1) would be to test the line segments > for intersections. If no intersections are found, the polygon is > simple. > (If somebody knows of a simpler test, please let me know.)That's the way to go. Do a Bentley-Ottmann planesweep test. Relative easy to implement and fast O(n log n). It becomes much more complex if you start to modify the geometry on the fly, but if you just want a simple yes/no answer it's the algorithm of choice.> > But what about question 2)? Any suggestions?Take the topmost, leftmost vertex. This is your anchor. Search for the next and previous vertices until you find three vertices that form a triangle with a non-zero area (e.g. skip repeated vertices and those that are just in the middle of a straight line). The signed area of the triangle will tell you the winding of the entire polygon (caveat: Only if it is simple). Area calculation is just a cross-product. Btw: You get the topmost, leftmost vertex as a side-effect of the bentley-ottmann scan since you have to do a lexicographical sort of the points at the first place. Cheers, Nils
Reply by ●March 11, 20102010-03-11
Rune Allnor wrote:> Hi folks. > > I have an application where I need to process a polygon. > The polygon is given as a list of points that tracks the > boundary of the polygon. There are two tests that must > be done befoe I can do my processing: > > 1) Ensure that the polygon is simple > 2) Ensure that the points track the outline in the counter > clockwise direction. > > A naive test for question 1) would be to test the line segments > for intersections. If no intersections are found, the polygon is > simple. > (If somebody knows of a simpler test, please let me know.) > > But what about question 2)? Any suggestions? > > RuneDoes 2) mean the representation of the line segments are ordered ... somehow? If so, then ensure that 1) the figure is closed and 2) that the figure is ordered counterclockwise. Example: { 0 , 0 } , { 0 , 1 } { 0 , 1 } , { 1 , 1 } { 1 , 1 } , { 1 , 0 } { 1 , 0 } , { 0 , 0 } is a closed square, ordered so that it's counterclockwise ( assuming 0,0 is the upper left hand corner, and the coordinates used are like computer screen graphics coordinates) So to move counterclockwise, you'd visit { 0, 0}, { 0, 1 } , { 1 , 1 } , { 1 , 0 } It's something like a Gray Code, isn't it? -- Les Cargill
Reply by ●March 12, 20102010-03-12
On 12 Mar, 02:34, Les Cargill <lcargil...@comcast.net> wrote:> Rune Allnor wrote: > > Hi folks. > > > I have an application where I need to process a polygon. > > The polygon is given as a list of points that tracks the > > boundary of the polygon. There are two tests that must > > be done befoe I can do my processing: > > > 1) Ensure that the polygon is simple > > 2) Ensure that the points track the outline in the counter > > � �clockwise direction. > > > A naive test for question 1) would be to test the line segments > > for intersections. If no intersections are found, the polygon is > > simple. > > (If somebody knows of a simpler test, please let me know.) > > > But what about question 2)? Any suggestions? > > > Rune > > Does 2) mean the representation of the line segments are > ordered ... somehow?The nodes of the polygon that prior to the test has been classified as 'simple' are ordered around the boundary as either CW or CCW, but I don't know which. The purpose of the test is to find out which it is. Trying to decode the various replies here, I suppose something like a line integral around the border might help. If the computed integral is positive, the orientation is one way. If it is negative, the orientation is the other. Rune
Reply by ●March 12, 20102010-03-12
On Mar 12, 5:00�am, Rune Allnor <all...@tele.ntnu.no> wrote:> On 12 Mar, 02:34, Les Cargill <lcargil...@comcast.net> wrote: > > > > > > > Rune Allnor wrote: > > > Hi folks. > > > > I have an application where I need to process a polygon. > > > The polygon is given as a list of points that tracks the > > > boundary of the polygon. There are two tests that must > > > be done befoe I can do my processing: > > > > 1) Ensure that the polygon is simple > > > 2) Ensure that the points track the outline in the counter > > > � �clockwise direction. > > > > A naive test for question 1) would be to test the line segments > > > for intersections. If no intersections are found, the polygon is > > > simple. > > > (If somebody knows of a simpler test, please let me know.) > > > > But what about question 2)? Any suggestions? > > > > Rune > > > Does 2) mean the representation of the line segments are > > ordered ... somehow? > > The nodes of the polygon that prior to the test > has been classified as 'simple' are ordered > around the boundary as either CW or CCW, but > I don't know which. The purpose of the test > is to find out which it is. > > Trying to decode the various replies here, I > suppose something like a line integral around > the border might help. If the computed integral > is positive, the orientation is one way. If it > is negative, the orientation is the other. > > Rune- Hide quoted text - > > - Show quoted text -Hello Rune, The method I gave will have all of the cross products have the same sign for the z component iff your polygon is convex and your vertices are in order (cw or ccw). Clay
