Is a point inside a convex polygon?

A convex polygon is given as a list of points in 2D and edges between them. For a given point determine whether the point lies inside the polygon.

The algorithm:

Draw a half line starting from the given point in the direction of the x-axis.
Count the number of intersection of the half line with line segments of the polygon.
Return True if the number of intersections is



In [2]:

    
def intersects(p, a, b):
    """
    Return True if the half line starting from the point p
    in the direction of the x-axis intersects the line
    segment with endpoints a and b and False otherwise.
    """
    p = (p[0] + random.random()*0.000001, p[1] + random.random()*0.000001)
    a, b = sorted([a, b], key=lambda p: p[1])
    if a[1] < p[1] and p[1] < b[1]:
        # Check the orientation
        a = numpy.array([[1] + list(p),
                         [1] + list(a),
                         [1] + list(b)])
        return numpy.linalg.det(a) > 0
    return False



In [3]:

    
def count_intersections(point_coordines, lines, point):
    """
    Count the number of intersection of the half line starting in the point
    point in the direction of the x-axis with the lines in the list line.
    """
    intersections = 0
    for line in lines:
        a, b = point_coordinates[line[0]], point_coordinates[line[1]]
        if intersects(point, a, b):
            intersections += 1
    return intersections