isConvex.py

'''
Adapted from http://stackoverflow.com/a/1881201/1956065 and http://stackoverflow.com/a/25304159/1956065
12 January 2017
John J Czaplewski
[email protected]
'''

def xProduct(v0, v1, v2):
    dx1 = v1[0] - v0[0]
    dy1 = v1[1] - v0[1]
    dx2 = v2[0] - v1[0]
    dy2 = v2[1] - v1[1]

    return (dx1 * dy2) - (dy1 * dx2)

# polygon - [ [x, y], [x, y], ... ]
def isConvex(polygon):
    sign = False
    for idx, vertex0 in enumerate(polygon):
        if idx + 2 > (len(polygon) - 1):
            break

        vertex1 = polygon[idx + 1]
        vertex2 = polygon[idx + 2]

        xproduct = xProduct(vertex0, vertex1, vertex2)

        if idx == 0:
            sign = xproduct > 0
        elif sign != (xproduct > 0):
            return False


    # Use the ends
    xproduct = xProduct(polygon[len(polygon) - 3], polygon[len(polygon) - 2],polygon[0])
    if sign != (xproduct > 0):
        return False

    xproduct = xProduct(polygon[len(polygon) - 2], polygon[0],polygon[1])
    if sign != (xproduct > 0):
        return False

    return True