I don't understand why generating a bounding box is much harder than determining whether a point lies inside a polygon, surely this is a simple matter, assuming the polygon is an N x 2 list of vertices, of finding the maximum and minimum points on each axis and then generating the bounding box from that? Which seems a worthwhile optimisation if the polygon has a high number of vertices
On 16 April 2010 16:18, Devon McCormick <[email protected]> wrote: > 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 > > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
