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 11 Mar 2010 04:25 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
From: Nicholas Kinar on 11 Mar 2010 09:22 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
From: Clay on 11 Mar 2010 11:30 On Mar 11, 4:25 am, Rune Allnor <all...(a)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? > > Rune Hello 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
From: Nils on 11 Mar 2010 17:24 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
From: Les Cargill on 11 Mar 2010 20:34
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? 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 |