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

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]

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.

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;
}

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

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

Related

Recent Posts