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

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 2

If it is convex, a trivial way to check it is that the point is to the same side of all the segments (if traversed in the same order). You can check that easily with the cross product.

Here is the code in Python:

#vertices is supposed a numpy.array,
#or any structure wich has the rest operator as an element by element operation
def inside_convex_polygon(point, vertices):
    sign = 0
    n_vertices = len(vertices)
    for n in xrange(n_vertices):
        segment = vertices[n], vertices[(n+1)%n_vertices]
        affine_segment = segment[1]-segment[0]
        affine_point = point-segment[0]
        k = x_product(affine_segment, affine_point)
        k = int(k / abs(k)) #normalized to 1 or -1
        if sign == 0: #the first case
            sign = k 
        elif k != sign:
             return False
    return True

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

I haven't tested it, but should work :-)

Edit: tested with a few trivial examples and seems to be working...

Answer 3

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 4

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