Boyko Bantchev wrote: "The winding number method ... is computationally awful and for this reason not much used."
Nobody really knows how much it is used, I guess. I find the winding number formula W=.(%&0j2p1)@(+/)@:^.@(% _1&|.) short and simple and computationally quite OK. It is, (divided by 2 pi i), the sum of the logarithm of the quotients between each corner and its predecessor. Try the test polygon P=.(,+@(0.5&*))_1^2*(%~i.)6 Close it and plot it: plot ($~(>:@$))P Test an outside point (0,0) W P 0j_1.41358e_16 Minute floating point errors disguise the fact that winding numbers are exact integers. So round the real part of the computed winding number. R=.<:@(0.5&+)@(9&o.) Test the outside point r...@w P 0 Test also the inside point (_0.8,0) r...@w 0.8+P 1 Take the path backward r...@w 0.8+|.P _1 or twice r...@w 0.8+P,P 2 The winding number is zero if (0,0) is inside the polygon, and nonzero if (0,0) is outside the polygon, but undefined if (0,0) is exactly on the border. -Bo --- Den ons 21/4/10 skrev Boyko Bantchev <[email protected]>: Fra: Boyko Bantchev <[email protected]> Emne: Re: [Jprogramming] Polygon containment Til: "Programming forum" <[email protected]> Dato: onsdag 21. april 2010 19.59 On 21 April 2010 12:56, R.E. Boss <[email protected]> wrote: > > The basic idea of winding number is brilliant ......... The winding number method does have certain beauty in the abstract mathematical sense but is computationally awful and for this reason not much used. Due to the complicated nature of the involved operations (angular computations) and the resulting computational inaccuracies, it is much less stable than the even/odd intersection counting method. > I estimate that this solution performs better than others. Better than what? Measured on what? I find your statement doubtful in view of the complexity of the above mentioned numeric operations that it is based upon (apart from them making the method less stable). Note also that, by its nature, the even/odd intersection counting method can work with only integer arithmetic, provided that all given coordinates are integers. This should both ensure maximum accuracy and improve performance. The winding number method does not have this feature. > Apart from that it works for a large(r) collection of polygons. ‘Works’ would depend on how you would want to treat islands – polygons entirely within polygons, and islands' islands etc. Are they holes (and holes within holes) or are they just internal areas – preferences vary. Similar for intersecting polygons. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
