MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Interior of a polygon

Would this work?

1) find the bounding box of the polygon, and hence the bounding rectangles
on the coordinate planes.
2) from each integer-coordinate point on one of the coordinate planes, say
the x-y plance, cast lines into the third dimension, say z, i.e. if the
points are on the x,y plane, cast lines into z.
3) test each line for intersection with the plane of the polygon
4) if the z-coordinate of the intersection point is integer (within some
tolerance) add it to a list of candidates
5) test all candidates, hopefully a small subset of the brute force method,
to see if they are within the polygon.

I haven't tested this, I'm just guessing that it would eliminate most points
from the more costly consideration.



"Andrzej Kozlowski" <andrzej at> wrote in message
news:A1EH6.3277$JY6.7063 at
> on 01.5.1 0:02 AM, David Terr at dterr at wrote:
> > Andrzej Kozlowski wrote:
> >
> >> Well, yes but we all know this. This was discussed on this list in
> >> last year, and exactly the same method was described by a number of
> >> different people. But this was not the point of the question this time.
> >> point was to find all the points which have integer coordinates which
> >> inside. Your suggestion simply gives the most obvious and probably
> >> inefficient method which I referred to as "brute force" and which
> >> Jankowski (who asked the original question) had known about already
> >> he sent his message to the mathgroup.
> >>
> >> Andrzej
> >>
> >> on 01.4.28 8:47 AM, DennisW555 at dennisw555 at wrote:
> >>
> >>> To find if a point is inside a polygon simply start at one vertex and
> >>> accumulate the angles from the point to each sucessive vertex, all the
> >>> around to that starting vertex.  Keep track of the sense, as some will
> >>> negative angles and some positive.  If the magnitude of the sum of
angles is
> >>> 2
> >>> Pi the point is inside.  If the sum is zero the point is outside.  I
set the
> >>> decision threshold at Pi for simplicity.  With this method the polygon
> >>> not
> >>> need to be convex.  I pretend the polygon points are in the xy plane
> >>> take
> >>> cross products between successive vectors from the point to the
> >>> Then
> >>> the magnitude of the sum of the z components of the cross products is
> >>> quantity to test. To do this a vertex at coordinates {x,y} becomes
> >>> likewise for the point.
> >>>
> >>> I hope this helps,
> >>>
> >>> Dennis Wangsness
> >>>
> >>
> >> --
> >> Andrzej Kozlowski
> >> Toyama International University
> >> JAPAN
> >>
> >>
> >>
> >
> > To find the set of all points inside a polygon or any region is no easy
matter> > since there are infintely many. How would you represent the collection
of all
> > such
> > points? The simplest way to do this is to return the interior of the
> > itself, but since you're starting with the polygon, this begs the
> > Thus I
> > don't think there's any simple answer to your question.
> >
> > David
> >
> >
> We are assuming that the polygon is compact (of course!). The problem is
> to find the set of all points inside the polygon, which would be
> but only to find the points which have integer coordinates. THere are only
> finitely many  such points. To do so is actually "a simple matter", the
> difficulty is to do so in an efficient tmanner.
> --
> Andrzej Kozlowski
> Toyama International University


  • Prev by Date: Re: Interior of a polygon
  • Next by Date: Properly Formatted Pascal's Triangle?
  • Previous by thread: Re: Interior of a polygon
  • Next by thread: Re: Interior of a polygon