Date: Sun, 26 Oct 1997 16:43:53 +0200 (IST)
From: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
To: Guillermo Porras <guporras AT calvin DOT univalle DOT edu DOT co>
cc: djgpp AT delorie DOT com
Subject: Re: Polygon inside point detection
In-Reply-To: <Pine.GSO.3.96.971023145200.19770B-100000@calvin.univalle.edu.co>
Message-ID: <Pine.SUN.3.91.971026164330.17911B-100000@is>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk


On Thu, 23 Oct 1997, Guillermo Porras wrote:

> How can i know if a given point is inside a given 2d Polygon

You need to consult a good book on computational geometry (e.g.,
"Computational Geometry: An Introduction", by Preparata and Shamos).
For starters, here's the simplest algorithm I know of:

    To determine if a point is inside a polygon, draw a horizontal ray
    from the point to the right.  The point is inside the polygon if
    that ray crosses the sides of the polygon an odd number of times.

Here's a simple C implementation of this algorithm which also takes
into account the case where the point is on the border (it treats them
as if the point were inside).

Note that if you have a single polygon and a lot of points to test,
there are faster algorithms.

static int
cross (double px, double py, double x1, double y1, double x2, double y2)
{
  if ( ((y < y1) == (y < y2)) || (x >= x1 && x >= x2) )
    /* Side entirely above, below, or entirely to the left.  */
    return 0;
  else if (x < x1 && x < x2)
    /* Side to the right of point, but not entirely above or below.  */
    return 1;
  else if (x1 < x2)
    /* Side not entirely above or below point and not entirely
       to the left or right.  */
    return x < (x1 + (y - y1)*(x2 - x1)/(y2 - y1));
  else
    /* Same as above.  */
    return x < (x2 + (y - y2)*(x1 - x2)/(y1 - y2));
}

/* Given a point with coordinates [PX,PY], and a polygon 
   with N vertices {X[],Y[]}, return non-zero if the point
   is inside the polygon, zero if not.
   The vertices could be given in either the CW or the CCW order.  */

int
pnpoly (double px, double py, int n, double x[n], double y[n])
{
  int inside = 0;
  int i;

  for (i = 0; i < n - 1; i++)
    if (cross (px, py, x[i], y[i], x[i + 1], y[i + 1]))
      inside = !inside;

  if (cross (px, py, x[n], y[n], x[1], y[1]))
    inside = !inside;

  return inside;
}