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
