Dan wrote: I need to check whether a point falls within an arbitrary polygon.
The winding number formula is: W=.9&o.@(%&0j2p1)@(+/)@:^.@(% _1&|.) . To test if (0,0) is within the square ((1,0),(0,1),(-1,0),(0,-1)), type W 1 0j1 _1 0j_1 and get the result 1, indicating YES. To test if (4,0) is within the square, type W 1 0j1 _1 0j_1 - 4 and get the result 0, indicating NO. (see http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Mathematics/2009_December_17#Easiest_way_to_decide_if_a_point_is_within_a_polygon.3F) -Bo --- Den fre 16/4/10 skrev Dan Bron <[email protected]>: Fra: Dan Bron <[email protected]> Emne: Re: [Jprogramming] Polygon containment Til: "'Programming forum'" <[email protected]> Dato: fredag 16. april 2010 19.11 Thanks Devon. I think generating the bounding rectangles will be pretty easy. Maxima of points for outside rect, minima for inside rect. Then maybe I'll do your odd-#-of-intersections for checking if the point is inside the rect when req'd. Though that should be a very rare event indeed (the vast majority of hits will be outside the outer rect, and of the remaining the vast majority should be inside the inner rect.) -Dan -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Devon McCormick Sent: Friday, April 16, 2010 12:51 PM To: Programming forum Subject: Re: [Jprogramming] Polygon containment Dan - you might want to look at this convex hull code which will give you a bounding polygon - http://www.jsoftware.com/jwiki/DevonMcCormick/convexHull. Also, I find a surrounding envelope here - http://www.jsoftware.com/jwiki/DevonMcCormick/DLA00/BuildingACloseNeighborhood- but this may not be suitable for your problem as it's based on sets of points rather than polygons. Regards, Devon On Fri, Apr 16, 2010 at 12:16 PM, David Vincent-Jones <[email protected]>wrote: > There is several well defined algorithms for 'polygon fill'. These work > on donuts and many other strange configurations of form. > > How about adapting one of these with an exit routine if your specific > point is found. > > David > > On Fri, 2010-04-16 at 11:01 -0400, Dan Bron wrote: > > Guys, > > > > I need to check whether a point falls within an arbitrary polygon. > > > > This is in the context of another tool, and J will be a > pre/post-processor. The other tool allows it to check whether a point falls > > within a given rectangle with great speed. However, it cannot efficient > determine containment for an arbitrary polygon. > > > > So I'm considering putting a bounding box (circumscribed rectangle) > around the polygon, and maybe another one inside the polygon > > (inscribed rectangle), using the tool to check those, and then, depending > on the results, using J to determine if the point is truly > > within the polygon. > > > > If I take that approach, I would need a few things: > > > > (1) A way to represent polygons in J (an Nx2 array > > of vertices?) > > > > (2) A verb whose input is a polygon and whose output is the > > minimum bounding rectangle around that polygon and/or > > the maximum inscribed rectangle in that polygon. > > The rectangle be represented like any other polygon, > > i.e. (1). > > > > (3) Some post-processing code that will be called when > > the fast utility determines if the point is in the > > outer rectangle rectangle and/or if the point is > > outside the inner rectangle. The inputs is the > > polygon and the points, and the output is a boolean > > per point, which indicates whether the point is > > "truly" in the polygon (because the outer rectangle > > could contain the point, yet the polygon not, and the > > inner rectangle could exclude the point, yet the > > polygon could still contain it). > > > > Can someone suggest some approaches? > > > > -Dan > > > > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Devon McCormick, CFA ^me^ at acm. org is my preferred e-mail ---------------------------------------------------------------------- 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
