How to test if a point is inside of a convex polygon in 2D integer coordinates?

Question

The polygon is given as a list of Vector2I objects (2 dimensional, integer coordinates). How can i test if a given point is inside? All implementations i found on the web fail for some trivial counter-example. It really seems to be hard to write a correct implementation. The language does not matter as i will port it myself.

Answer 1

If it is convex, a trivial way to check it is that the point is laying on the same side of all the segments (if traversed in the same order).

You can check that easily with the dot product (as it is proportional to the cosine of the angle formed between the segment and the point, if we calculate it with the normal of the edge, those with positive sign would lay on the right side and those with negative sign on the left side).

Here is the code in Python:

RIGHT = "RIGHT"
LEFT = "LEFT"

def inside_convex_polygon(point, vertices):
    previous_side = None
    n_vertices = len(vertices)
    for n in xrange(n_vertices):
        a, b = vertices[n], vertices[(n+1)%n_vertices]
        affine_segment = v_sub(b, a)
        affine_point = v_sub(point, a)
        current_side = get_side(affine_segment, affine_point)
        if current_side is None:
            return False #outside or over an edge
        elif previous_side is None: #first segment
            previous_side = current_side
        elif previous_side != current_side:
            return False
    return True

def get_side(a, b):
    x = cosine_sign(a, b)
    if x < 0:
        return LEFT
    elif x > 0: 
        return RIGHT
    else:
        return None

def v_sub(a, b):
    return (a[0]-b[0], a[1]-b[1])

def cosine_sign(a, b):
    return a[0]*b[1]-a[1]*b[0]

Answer 2

The Ray Casting or Winding methods are the most common for this problem. See the Wikipedia article for details.

Also, Check out this page for a well-documented solution in C.

Answer 3

If the polygon is convex, then in C#, the following implements the "test if always on same side" method, and runs at most at O(n of polygon points):

public static bool IsInConvexPolygon(Point testPoint, List<Point> polygon)
{
    //Check if a triangle or higher n-gon
    Debug.Assert(polygon.Length >= 3);

    //n>2 Keep track of cross product sign changes
    var pos = 0;
    var neg = 0;

    for (var i = 0; i < polygon.Count; i++)
    {
        //If point is in the polygon
        if (polygon[i] == testPoint)
            return true;

        //Form a segment between the i'th point
        var x1 = polygon[i].X;
        var y1 = polygon[i].Y;

        //And the i+1'th, or if i is the last, with the first point
        var i2 = (i+1)%polygon.Count;

        var x2 = polygon[i2].X;
        var y2 = polygon[i2].Y;

        var x = testPoint.X;
        var y = testPoint.Y;

        //Compute the cross product
        var d = (x - x1)*(y2 - y1) - (y - y1)*(x2 - x1);

        if (d > 0) pos++;
        if (d < 0) neg++;

        //If the sign changes, then point is outside
        if (pos > 0 && neg > 0)
            return false;
    }

    //If no change in direction, then on same side of all segments, and thus inside
    return true;
}

Answer 4

The pointPolygonTest function in openCV " determines whether the point is inside a contour, outside, or lies on an edge": http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

Answer 5

fortran's answer almost worked for me except I found I had to translate the polygon so that the point you're testing is the same as the origin. Here is the JavaScript that I wrote to make this work:

function Vec2(x, y) {
  return [x, y]
}
Vec2.nsub = function (v1, v2) {
  return Vec2(v1[0]-v2[0], v1[1]-v2[1])
}
// aka the "scalar cross product"
Vec2.perpdot = function (v1, v2) {
  return v1[0]*v2[1] - v1[1]*v2[0]
}

// Determine if a point is inside a polygon.
//
// point     - A Vec2 (2-element Array).
// polyVerts - Array of Vec2's (2-element Arrays). The vertices that make
//             up the polygon, in clockwise order around the polygon.
//
function coordsAreInside(point, polyVerts) {
  var i, len, v1, v2, edge, x
  // First translate the polygon so that `point` is the origin. Then, for each
  // edge, get the angle between two vectors: 1) the edge vector and 2) the
  // vector of the first vertex of the edge. If all of the angles are the same
  // sign (which is negative since they will be counter-clockwise) then the
  // point is inside the polygon; otherwise, the point is outside.
  for (i = 0, len = polyVerts.length; i < len; i++) {
    v1 = Vec2.nsub(polyVerts[i], point)
    v2 = Vec2.nsub(polyVerts[i+1 > len-1 ? 0 : i+1], point)
    edge = Vec2.nsub(v1, v2)
    // Note that we could also do this by using the normal + dot product
    x = Vec2.perpdot(edge, v1)
    // If the point lies directly on an edge then count it as in the polygon
    if (x < 0) { return false }
  }
  return true
}

Answer 6

the way i know is something like that.

you pick a point somewhere outside the polygon it may be far away from the geometry. then you draw a line from this point. i mean you create a line equation with these two points.

then for every line in this polygon, you check if they intersect.

them sum of number of intersected lines give you it is inside or not.

if it is odd : inside

if it is even : outside

Answer 7

You have to check that the point to test maintains it's orientation relative to all segments of the convex polygon. If so, it's inside. To do this for each segment check if the determinant of the segment vector say AB and the point's vector say AP preserves it's sign. If the determinant is zero than the point is on the segment.

To expose this in C# code,

public bool IsPointInConvexPolygon(...)
{
    Point pointToTest = new Point(...);
    Point pointA = new Point(...);
    //....

    var polygon = new List<Point> { pointA, pointB, pointC, pointD ... };
    double prevPosition = 0;
    // assuming polygon is convex.
    for (var i = 0; i < polygon.Count; i++)
    {
        var startPointSegment = polygon[i];
        // end point is first point if the start point is the last point in the list
        // (closing the polygon)
        var endPointSegment = polygon[i < polygon.Count - 1 ? i + 1 : 0];
        if (pointToTest.HasEqualCoordValues(startPointSegment) ||
              pointToTest.HasEqualCoordValues(endPointSegment))
            return true;

        var position = GetPositionRelativeToSegment(pointToTest, startPointSegment, endPointSegment);
        if (position == 0) // point position is zero so we are on the segment, we're on the polygon.
            return true;

        // after we checked the test point's position relative to the first segment, the position of the point 
        // relative to all other segments must be the same as the first position. If not it means the point 
        // is not inside the convex polygon.
        if (i > 0 && prevPosition != position)
            return false;

        prevPosition = position;
    }
    return true;
}

The determinant calculus,

public double GetPositionRelativeToSegment(Point pointToTest, Point segmentStart, Point segmentEnd)
{
    return Math.Sign((pointToTest.X - segmentStart.X) * (segmentEnd.Y - segmentStart.Y) -
        (pointToTest.Y - segmentStart.Y) * (segmentEnd.X - segmentStart.X));
}

Answer 8

Or from the man that wrote the book see - geometry page

Specifically this page, he discusses why winding rule is generally better than ray crossing.

edit - Sorry this isn't Jospeh O'Rourke who wrote the excellent book Computational Geometry in C, it's Paul Bourke but still a very very good source of geometry algorithms.

Answer 9

Here is the version I use in my project. It's very elegant and concise. Works for every kind of polygons.

http://www.eecs.umich.edu/courses/eecs380/HANDOUTS/PROJ2/InsidePoly.html

The following code is by Randolph Franklin, it returns 1 for interior points and 0 for exterior points.

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
  int i, j, c = 0;
  for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ||
         ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      c = !c;
  }
  return c;
}