Thank you. I understanding that this optimization of the winding number algorithm performs well on almost regular polygons, while it doesn't perform substantially better on nonconvexe polygons like
+/\(k...@-.,1,k=.(*0j1&^)@>:&i.)50 Am I right? --- Den man 26/4/10 skrev R.E. Boss <[email protected]>: > Fra: R.E. Boss <[email protected]> > Emne: Re: [Jprogramming] Polygon containment > Til: "'Programming forum'" <[email protected]> > Dato: mandag 26. april 2010 18.41 > Well, the basic idea is rather > simple. You exclude the points that are > outside the circumscribed circle and include the points > that are inside the > inscribed circle and which are on a vertex. For the rest, > (0=t)#Y , in > between the 2 circles, you calculate the winding number. > > (X e.~ Y) checks whether a point is on a vertex > > Y (>>./)&:| X determines which points are > outside the circumscribed circle > > Y ([ (<<./)&:| 2( <.&:|/ (* 2 o. -:) 12 > o.%/ )\ ]) (,{.) X determines which > points are inside the inscribed circle > The inscribed circle does not exactly have radius equal to > 2( <.&:|/ (* 2 o. > -:) 12 o.%/ )\ (,{.) X, but it is easy to see it need not > be smaller. > > Hope this explanation is sufficient > > > R.E. Boss > > > > > -----Oorspronkelijk bericht----- > > Van: [email protected] > [mailto:programming- > > [email protected]] > Namens Bo Jacoby > > Verzonden: maandag 26 april 2010 17:12 > > Aan: Programming forum > > Onderwerp: Re: [Jprogramming] Polygon containment > > > > I am regrettably not fluent enough in reading J to > understand the code > > below by R.E.Boss. I would appreciate some further > explanation. > > -Bo > > > > --- Den man 26/4/10 skrev R.E. Boss <[email protected]>: > > > > > Fra: R.E. Boss <[email protected]> > > > Emne: Re: [Jprogramming] Polygon containment > > > Til: "'Programming forum'" <[email protected]> > > > Dato: mandag 26. april 2010 16.58 > > > > 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 > > > > > > > > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > __________________________________________________ Bruger du Yahoo!? Er du træt af spam? Yahoo!Mail har den bedste spambeskyttelse, der findes http://dk.mail.yahoo.com ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
