> Van: [email protected] [mailto:programming-
> [email protected]] Namens Henry Rich
> Onderwerp: Re: [Jprogramming] Polygon containment
>
>
> > Since his polygons are convex, surely a more efficient solution would
> > be to use the log n method.
> >
>
> Dan said his polygons are convex, but did he really mean that? Convex
> polygons with lots of vertices would come about only from some sort of
> automatic approximation to a curve, methinks.
>
> A J implementation of the O(log n) method shouldn't be hard & I'll make
> a try at it if Dan confirms that he really does have many-sided convex
> polygons.
>
> Henry Rich
Since J is (often) rather insensitive for this theoretical considerations,
it would surprise me if the O(log n) method would be significantly faster
than the solution I presented.
I polished wn a bit.
wn=: 4 : 0 NB. x is polygon, y is points
XX=. |:(, {.)x [ Y=. |: y
in=. *./ Y ((>: {.) *. (<: {:))"1 (<./,>./)"1 XX
'A B'=: (}: ,: }.) XX <:/&{: Yin=: in #"1 Y
'p n'=. (A * -.B) ,: (-.A) * B
S=. |:(t0=. $A) #: s=. I., p +. n
R=. * (({.S) {"1 (}. - }:)"1 XX) ([: -/ (*|.)) (({:S) {"1 Yin) - ({.S) {"1
XX
t=. t0 $ R s} t=.0 #~ */t0
in=. (+/ (p * 0 < t) - n * 0 > t) (I.1=in)} in
)
For convex (and some other) polygons you could use the inner circle again.
wn_cnvx=: 4 : 0 NB. x is convex polygon, y is points
XX=. |:(, {.)x [ Y=. |: y
in=. *./ Y ((>: {.) *. (<: {:))"1 (<./,>./)"1 XX
in=. in + Y ([ (<<./)&:| 2( <.&:|/ (* 2 o. -:) 12 o.%/ )\ ])&(j./) XX
'A B'=. (}: ,: }.) XX <:/&{: Yin=. (1=in) #"1 Y
'p n'=. (A * -.B) ,: (-.A) * B
S=. |:(t0=. $A) #: s=. I., p +. n
R=. * (({.S) {"1 (}. - }:)"1 XX) ([: -/ (*|.)) (({:S) {"1 Yin) - ({.S) {"1
XX
t=. t0 $ R s} t=.0 #~ */t0
in=. (+/ (p * 0 < t) - n * 0 > t) (I.1=in)} 0<in
)
The gain is most in memory.
('wn';'wn_cnvx') dspl rnkng scores 'PLG wn PTS';'PLG wn_cnvx PTS'
+-------+----+-----+----+----+
|verb |rank|et*sz|time|size|
+-------+----+-----+----+----+
|wn | 1 |4.89 |1.22|4.02|
+-------+----+-----+----+----+
|wn_cnvx| 0 |1.00 |1.00|1.00|
+-------+----+-----+----+----+
(PLG wn PTS)-:PLG wn1 PTS
1
PLG ,&# PTS
1000 10000
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
