Point-Polygon-Collision.py

def infhorizline_line(a, b, count_overlap=True):
    """
    returns 0 for no intersection
    returns 1 for an intersection to the left of point a (if the point of intersection is on a, this is the default)
    returns 2 for an intersection to the right of point a
    """
    # Check if b is horizontal
    if b[0][1] == b[1][1]:
        if count_overlap:
            # Not perfect... not used so will do
            if b[0][1] == a[1]:
                if a[0] <= b[0][0]: return 1
                elif a[0] >= b[0][0]: return 2
        return 0

    # Edge case for polygonal collision so the intersection between two lines is only counted once unless it is a local minima or maxima
    # in which case it will be counted two or zero times
    if b[0][1] >= b[1][1]: highb = b[0]; lowb = b[1]
    else: highb = b[1]; lowb = b[0]
    if highb[1] == a[1]:
        if a[0] <= highb[0]: return 1
        else: return 2
    if lowb[1] == a[1]: return 0


    # Check if the points of b are on opposite sides of line a
    if (b[0][1] >= a[1] and b[1][1] <= a[1]) or (b[0][1] <= a[1] and b[1][1] >= a[1]):
        # Check if b is vertical
        if b[0][0] == b[1][0]:
            poi = b[0][0]
        else:
            slope = (b[1][1]-b[0][1]) / (b[1][0]-b[0][0])
            poi = (a[1]-b[0][1])/slope + b[0][0]
        if a[0] <= poi: return 1
        else: return 2
    return 0

def point_polygon(point, polygon):
    # Algorithm works by creating a horizontal line at the y-level of the point to intersect with the lines of the polygon.
    # If the number of intersections on the left (or right) of the polygon is odd, then the point lies within the polygon/
    # If the number of intersections on the left (or right) or the polygon is even, then the point lies outside of the polygon
    poly = polygon[:] + [polygon[0]]
    line_intersections = [0,0]
    for i in range(len(poly)-1):
        intersect = infhorizline_line(point, [poly[i],poly[i+1]], count_overlap=False)
        if intersect: line_intersections[intersect-1] += 1
    return line_intersections[0]%2 != 0