Dan - I think one common approach is to see if a line from the point in question to a point known to be outside the polygon crosses an odd number of boundaries. How easy or hard depends on whether or not you already have the relevant sub-functions.
Regards, Devon On Fri, Apr 16, 2010 at 11:01 AM, Dan Bron <[email protected]> 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 > -- Devon McCormick, CFA ^me^ at acm. org is my preferred e-mail ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
