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
