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
