@Stefano -thanks, that's an interesting general essay by Steve Mansour. @Henry -thanks for that bit of mathematical history. Long wanted to know.
@Bo - I forgot about the Winding Number. It does seem the neatest solution. And thanks for being polite enough not to remind me I'd asked this question on the programming list just over a year ago (and you'd answered me back then!)... http://www.jsoftware.com/pipermail/programming/2012-May/028135.html I'm going to build myself a list of links to forestall myself asking it again in a year's time :-) BTW the word "winding" allowed me to search Wikipedia, and I found the following articles, plus a reminder of terminology, eg PIP (Point-In-Polygon): http://en.wikipedia.org/wiki/Winding_number http://en.wikipedia.org/wiki/Computational_geometry http://en.wikipedia.org/wiki/Point_in_polygon On Thu, May 30, 2013 at 1:53 PM, Bo Jacoby <[email protected]> wrote: > Improvement: the nonzero condition ([:>&1|) can be written (1<|) , read > "one is less than the absolute value". > - Bo > > > > > > >________________________________ > > Fra: Bo Jacoby <[email protected]> > >Til: "[email protected]" <[email protected]> > >Sendt: 10:47 torsdag den 30. maj 2013 > >Emne: Re: [Jprogramming] Verifying a mouseclick is inside a rectangle > > > > > >Hi Ian > >The following solution was issued to the programming forum on may 14, > 2012. I believe it will solve your problem. > >- Bo > > > > > >The condition that the zero point is inside the polygon is that the > winding angle is nonzero. > > zero_inside_polygon =. [: nonzero winding > >The nonzero condition must be tolerant because rounding errors may make a > >theoretical zero look like nonzero. But nonzero winding angles are > >integer multiples of 0j2p1, so a robust condition is > > > > nonzero=.[:>&1| > >A simple winding angle algorithm is > > winding=.[:+/[:^.(%1&|.) > > > > plot(,{.)p2=.0.1++:p,+:+p=.0j1^i.4NB. p2 =. nonconvex test polygon > > zero_inside_polygon p2+3 > >1 > > zero_inside_polygon > >p2 > >0 zero_inside_polygon f. NB. final program (25 chars) > > > >[:([:>&1|)[:+/[:^.(%1&|.) > > > > > > > > > > > > > > > >>________________________________ > >> Fra: Ian Clark <[email protected]> > >>Til: Programming forum <[email protected]> > >>Sendt: 10:10 torsdag den 30. maj 2013 > >>Emne: [Jprogramming] Verifying a mouseclick is inside a rectangle > >> > >> > >>Reinventing The (Square) Wheel Department. > >> > >>Problem: given a rectangle ABCD defined by four points on the xy-plane, > >>detect whether a given point (a mouseclick) falls inside ABCD. Note that > >>side AB isn't necessarily parallel to the x or y axes. > >> > >>Currently I'm using a cumbersome algorithm based on deciding which side > of > >>a straight line the given point lies. The only thing in its favor is that > >>it generalizes to handle an irregular convex polygon. But that's not > needed > >>here. > >> > >>It would be nice to transform the rectangle to situate A at the origin, > >>then apply a simple range check on x and y. In practice it would only be > >>the mouseclick that got transformed (by the inverse matrix). I can't > >>believe someone hasn't already got a slick verb to do it. Games > programmers > >>must do it all the time! > >> > >>It would be nice too to see a solution using complex numbers instead of > >>2-by-2 matrices. I read somewhere that complex numbers were actually > >>developed before matrix theory, allegedly to handle coordinate geometry > on > >>the 2-plane. Can anyone verify or refute this? > >> > >>Displacement in the xy-plane can't normally be represented by a linear > >>transformation, but long ago I read of a way of introducing a third > virtual > >>z-axis, which did allow both rotation and displacement to be handled in > one > >>shot by a 3-by-3 matrix. Does anybody know of this technique? > >>---------------------------------------------------------------------- > >>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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
