[Jprogramming] Polygon containment

[Mark Allen]

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 <devonmcc at gmail.com> 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 <j at bron.us> 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
>
>