> 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
