geometry - 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]