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.