Yes, quoting http://erich.realtimerendering.com/ptinpoly/ about the 'Angle Summation Test':
-- "The problem with this scheme is that it involves a square root, arc-cosine, division, dot and cross product for each edge tested" The author Eric Haines [email protected] does not seem to be familiar with complex analysis, which enables us to use just one division and one logarithm for each edge tested. Nor is he aware of the advantage of the array processing capability of J. So he managed to convince himself: -- "In fairness, the angle algorithm can be sped up in various ways but it will still always be faster to use any other algorithm in this Gem". -- "The statistics vary depending on the machine and implementation but the general trends seem to hold". -- "Avoid the angle summation test like the plague" My primary guidelines are beauty and simplicity and generality rather than speed, but of course I don't mind winning the speed competition as well, humbly remembering that the statistics vary depending on the machine and implementation and of the test cases chosen. --- Den fre 23/4/10 skrev Devon McCormick <[email protected]>: > Fra: Devon McCormick <[email protected]> > Emne: Re: [Jprogramming] Polygon containment > Til: "Programming forum" <[email protected]> > Dato: fredag 23. april 2010 21.46 > This result is interesting, > especially considering if I had looked at this > nice comparison - http://erich.realtimerendering.com/ptinpoly/ - I would > have opted for a grid method as it looks not too complex > and has good > performance characteristics. The winding method is > the huge performance > loser according to the statistics given here. > > On Fri, Apr 23, 2010 at 5:41 AM, R.E. Boss <[email protected]> > wrote: > > > > Van: [email protected] > [mailto:programming- > > > [email protected]] > Namens Devon McCormick > > > Onderwerp: Re: [Jprogramming] Polygon > containment > > > > > > All these good theoretical considerations aside, > it will be interesting > > to > > > see how the winding number algorithm performs on > actual data. > > > > > > -- > > > Devon McCormick, CFA > > > > > > > > What I have collected so far: > > > > pip=: 4 : 0 > NB. Boss > > NB. point in (convex) polygon, x is point > > NB. y is polygon with 2 -: {:$y, such that > 2[\(,{.)y are edges > > NB. 1 if in polygon, 0 if on edge or vertex, _1 > if outside > > E=. _1 ,.~ (%."(2) 2[\(,{.)y) +/ . * 1 1 > > s=. * E +/ . *"(1) _2|.y ,. 1 > > t=. * E +/ . *"(1) x , 1 > > <: (+: s -: t) + (0 e. t) > > ) > > > > pinp=: 4 : 0 NB. Bantchev > > s=. 2&(]\)@(],{.) > > o=. ]/:/:@:({:"1) > > ps=. o"2...@s y > > as=. *-/ .* x,"1 2 ps > > vs=. x -"1 ps > > if. +/ (as=0) *. 0>:+/"1*/"2 vs do. > > 0 > > else. > > > <:+:~:/(as>0)*.([:(0&<@{.*.1&>@{:)[:{.[:|.|:)"2 > vs > > end. > > ) > > > > W=:%&0j2p1@(+/)@:^.@(% _1&|.) NB. Winding > number program; Jacoby > > R=:<.@(0.5&+)@(9&o.) NB. Rounding a complex > number into an integer > > > > wn=: 4 : 0 > NB. Boss > > NB. x is polygon with 2 -: > {:$x, such that 2[\(,{.)x are edges > > NB. y are points with 2 -: > {:$y > > NB. 1 if in > polygon, 0 if on edge or vertex, _1 if outside > > y=. ,:^:((2 > #...@$)`]) y > > ov=. y e. x NB. on vertex > > dv=. (,{.) j./"1 x -"1/ y > NB. difference vectors > > oe=. +./ 1e_14 ((<|)*]) (}. (= -) }:) > dv NB. on edge > > dv1=. dv #"1~ t=. -. ov +. oe > > in=. t #^:_1 [0 ~: 1e_14 ((< |) * ]) (2*pi) > %~ +/ {:"1 *. (}. % }:) dv1 > > <: (+: in) + ov +. oe > > ) > > > > rou=: [:^ 0j2p1&% * i. > NB. regular polygon > > plg=: 3 :'(,{.) +. rou 10^y' NB. regular > polygon with 10^y points > > pts=: 3 :'0 ?...@$~ 2 ,~ 10^y' > NB. 10^y arbitrary points in the unit > > square > > > > PLG=: plg 1 > > PTS=: 2 * pts 3 > > > > ts' PTS pip"1 _ }:PLG' > > 0.19810665 12288 > > > > ts' PTS pip"1 _ }:PLG' > > 0.20095689 12288 > > > > ts'PTS pinp"1 _ PLG' > > 0.20642736 15808 > > > > ts' r...@w PLG -/&:(j./"1) PTS ' > > 0.010154403 821760 > > > > ts'PLG wn PTS' > > 0.031857189 2021632 > > > > It is obvious that (in J) the winding number is the > winner. > > However, some results diverge. > > > > (PTS pip"1 _ }:PLG) -: PTS pinp"1 _ > PLG > > 0 > > > > (PTS pip"1 _ }:PLG) -: r...@w PLG > -/&:(j./"1)PTS > > 0 > > > > (PTS pip"1 _ }:PLG) -: PLG wn PTS > > 1 > > > > > > R.E. Boss > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > > -- > Devon McCormick, CFA > ^me^ at acm. > org is my > preferred e-mail > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
