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
