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
