On 30 April 2010 23:03, R.E. Boss <[email protected]> wrote: > Searching the internet, I found an interesting and (IMO) fundamental > solution to the problem of point in polygon, see "Fast Winding Number > Inclusion of a Point in a Polygon" on > http://www.softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm .
Yes, this is what is known as optimizing the winding number method. Note that complex numbers, angle measurement, and division are thrown away altogether as inadequate and irrelevant to the problem being solved. But in fact, what is left is algorithmically equivalent to the cross number method: casting a ray and counting intersections. The only difference between the two is whether we pay attention to the orientation of the edges being crossed, or not. > ( http://www.softsurfer.com/algorithms.htm is a real treasure trove for > geometric algorithms.) This is one of the good places. You might also be interested to visit: http://www.ics.uci.edu/~eppstein/geom.html http://compgeom.cs.uiuc.edu/~jeffe/compgeom http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml http://geometryalgorithms.com > - So, for both geometric correctness and efficiency reasons, the wn > algorithm should always be preferred for determining the inclusion of a > point in a polygon. Efficiency, as I said, is just the same here as that of the cn method – they are essentially the same cross counting algorithm. So which one is preferred is a matter of what kind of result one wants. By ‘correctness’ in the above quote they mean that counting crossings according to the wn method tends to treat internal areas bounded by a self-crossing contour as points inside the polygon, while, under the cn method of counting, inside and outside are following in alternating manner. The authors seem to prefer the former to the latter, but in fact both are completely acceptable, the choice between them depending on what is needed in a specific context. Note that both methods of defining inside/outside w.r.t. a complex contour are used in popular graphical systems, such as X Window and PostScript. (See e.g. pp.195-196 of http://www.adobe.com/products/postscript/pdfs/PLRM.pdf.) > A standard convention is to say that a point on a left or bottom edge > is inside, and a point on a right or top edge is outside. Again, this depends on what the particular application requires. What is convenient in one situation can cause headache in another. > I don't think Bron will get a much more efficient solution. Since his polygons are convex, surely a more efficient solution would be to use the log n method. > Apart from that, it works for all polygons. Just as the cn method does. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
