> Van: [email protected] [mailto:programming-
> [email protected]] Namens Bo Jacoby
> Onderwerp: Re: [Jprogramming] Polygon containment
>
> Well done mr. Boss!
> I supposed you ment to write
> PTS=: _1 + 2 * pts 3
> such that the area covered is _1<x<1, _1<y<1 rather than 0<x<1, 0<y<1 .
> -Bo
>
Further improvement is possible if some preprocessing is done.
rou=: [:^ 0j2p1&% * i.
plg=: 3 :'+. rou 10^y'
pts=: 3 :'0 ?...@$~ 2 ,~ 10^y'
PLG=: (3 : '(plg y)*1+1%~(10^y)?...@$0') 2 NB. starshaped
polygon
PTS=: _1 + 2 * pts 4
W2=: 4 : 0
'X Y'=. x ;&(j./&.|:) y
t=. (X e.~ Y) -~ Y ((>>./)&:| - [ (<<./)&:| 2( <.&:|/ (* 2 o. -:) 12 o.%/
)\ ]) (,{.) X
t=. (<.@(0.5&+)@(9&o.) %&0j2p1@(+/)@:^.@(% _1&|.) X -/(0=t)#Y) (I.0=t)} 0>t
)
('W';'W2') dspl rnkng scores 'r...@w PLG -/&:(j./"1) PTS';'PLG W2 PTS'
+----+----+-----+----+----+
|verb|rank|et*sz|time|size|
+----+----+-----+----+----+
|W | 1 |18.36|4.72|3.89|
+----+----+-----+----+----+
|W2 | 0 | 1.00|1.00|1.00|
+----+----+-----+----+----+
(r...@w PLG -/&:(j./"1) PTS)-:PLG W2 PTS
1
Some remarks
1. if 0 0 is not in the polygon, subtract (+/ % #)PLG from PLG and PTS
2. on the edge (or, with W2, on the vertex) is reckoned to be inside the
polygon
3. since Bron already does preprocessing with in- and circumscribed
rectangles, the improvement in his case(s) will be less.
4. no problems with W2 on vertices:
PLG W2 PLG
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ....
Some investigation has to be done whether W2 also works for more uncommon
polygons, like with intersections. Perhaps a good definition of in- and
outside should be appropriate then, at least for me.
I'm curious to know if this result can be beaten.
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
