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
