Playing polygon games
in [DSP]
|
Prev: question about fftw3 in fortran, reuse plan, FFTW_MEASURE,
Next: can the bessel filter be directly designed in digital domain?
From: Rune Allnor on 12 Mar 2010 05:00 On 12 Mar, 02:34, Les Cargill <lcargil...(a)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
From: Clay on 12 Mar 2010 10:35 On Mar 12, 5:00 am, Rune Allnor <all...(a)tele.ntnu.no> wrote: > On 12 Mar, 02:34, Les Cargill <lcargil...(a)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
From: Clay on 12 Mar 2010 11:27
On Mar 12, 10:35 am, Clay <c...(a)claysturner.com> wrote: > On Mar 12, 5:00 am, Rune Allnor <all...(a)tele.ntnu.no> wrote: > > > > > > > On 12 Mar, 02:34, Les Cargill <lcargil...(a)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- Hide quoted text - > > - Show quoted text - Rune, if you allow for non convex polygons but want to know if in general the vertices go ccw or cw, then for the vertices just apply the surveyor's formula for area. One direction (ccw) will give you a positive area and the other way (cw) will give you a negative area (correct are in absolute sense). The surveyor's formula comes from using Green's thoerem for the plane to turn an area integral into a line integral and then simply pick an intgrand so the area integral just gives the area of the polygon. Thus the line integral becomes a sum of factors (one for each side). Then a little manipulation will put it into the surveyor's form. Clay I recall Green's result yields for each side of the polygon just accumulate the average "x" coordinate for the side multiplied by the change in "y" for the side. i.e. for a side defined by (x1,y1) and (x2,y2), the areal component is 0.5*(x1+x2)*(y2-y1). Do this for each side and add the results for each side together to get the area. |