@Ian. Thanks for attributing to politeness what is actually a case of bad memory on my part. The winding number method has a reputation of being slow, but I think that the method is fast even if bad implementations ofthe method are slow. Consider an owllooking incessantly at a race car on a closed track. If the head of the owl has turned completely around when the car has completed a trip, then the owl is inside the track! - Bo
>________________________________ > Fra: Ian Clark <[email protected]> >Til: Programming forum <[email protected]> >Sendt: 19:47 torsdag den 30. maj 2013 >Emne: Re: [Jprogramming] Verifying a mouseclick is inside a rectangle > > >@Stefano -thanks, that's an interesting general essay by Steve Mansour. > >@Henry -thanks for that bit ofmathematical history. Longwanted to know. > >@Bo - I forgotabouttheWindingNumber. It doesseemtheneatest solution. >And thanks for beingpoliteenough not to remind meI'daskedthisquestion >onthe programming list just over a yearago (and you'dansweredme back >then!)... >http://www.jsoftware.com/pipermail/programming/2012-May/028135.html >I'mgoing to buildmyself a list oflinks to forestallmyselfasking it >again in a year's time :-) > >BTWtheword "winding" allowedme to searchWikipedia, and I foundthe >followingarticles, plus a reminder ofterminology, 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 > > > >OnThu, May 30, 2013 at 1:53 PM, Bo Jacoby <[email protected]> wrote: > >> Improvement: thenonzerocondition ([:>&1|) canbewritten (1<|) , read >> "one is lessthantheabsolutevalue". >> - 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 >> >Thefollowing solution wasissued to the programming forum onmay 14, >> 2012. I believe it willsolveyour problem. >> >- Bo >> > >> > >> >Theconditionthatthezero point is insidethe polygon is thatthe >> winding angle is nonzero. >> > zero_inside_polygon =. [: nonzerowinding >> >Thenonzerocondition must be tolerant becauseroundingerrorsmaymake a >> >theoreticalzero look likenonzero. But nonzerowinding angles are >> >integermultiplesof 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 >> >> >> >> >> >>ReinventingThe (Square) WheelDepartment. >> >> >> >>Problem: given a rectangleABCDdefined by four points onthexy-plane, >> >>detectwhether a given point (a mouseclick) fallsinsideABCD. Note that >> >>side AB isn'tnecessarily parallel to the x or y axes. >> >> >> >>CurrentlyI'musing a cumbersomealgorithmbasedondecidingwhich side >> of >> >>a straight line the given point lies.Theonlything in itsfavor is that >> >>it generalizes to handle an irregularconvex polygon. But that's not >> needed >> >>here. >> >> >> >>It wouldbenice to transformtherectangle to situate A at theorigin, >> >>thenapply a simple range check on x and y. In practice it wouldonlybe >> >>themouseclickthatgottransformed (by the inverse matrix). I can't >> >>believesomeonehasn'talreadygot a slickverb to do it. Games >> programmers >> >>must do it allthe time! >> >> >> >>It wouldbenicetoo to see a solution usingcomplexnumbersinsteadof >> >>2-by-2 matrices. I readsomewherethatcomplexnumberswereactually >> >>developedbefore matrix theory, allegedly to handle coordinategeometry >> on >> >>the 2-plane. Cananyoneverifyorrefutethis? >> >> >> >>Displacement in thexy-planecan'tnormallyberepresented by a linear >> >>transformation, but longago I readof a wayofintroducing a third >> virtual >> >>z-axis, which did allowboth rotation and displacement to behandled in >> one >> >>shot by a 3-by-3 matrix. Doesanybodyknowofthistechnique? >> >>---------------------------------------------------------------------- >> >>For information about J forums seehttp://www.jsoftware.com/forums.htm >> >> >> >> >> >> >> >---------------------------------------------------------------------- >> >For information about J forums seehttp://www.jsoftware.com/forums.htm >> > >> > >> ---------------------------------------------------------------------- >> For information about J forums seehttp://www.jsoftware.com/forums.htm >> >---------------------------------------------------------------------- >For information about J forums seehttp://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
