Kivy Polygon Intersection

collide.py

class Polygon(EventDispatcher):
    abs_vertices = ListProperty([])
    x = NumericProperty(0)
    y = NumericProperty(0)
    scale = NumericProperty(1)

    def __init__(self, **kwargs):
        super(Polygon, self).__init__(**kwargs)
        self.abs_vertices = []

    def _get_rel_vertices(self):
        return [(x*self.scale+self.x, y*self.scale+self.y) for x, y in self.abs_vertices]

    vertices = AliasProperty(_get_rel_vertices, lambda *a: None, bind=("x", "y", "abs_vertices"))

    def collide_point(self, x, y):
        # This strangely happens. IDK
        if len(self.abs_vertices) == 0:
            warnings.warn("Polygon has no vertices: {0}".format(str(self)), RuntimeWarning, stacklevel=2)
            return False

        # If the point is a vertex, it's in the polygon
        if (x, y) in (tuple(i) for i in self.vertices):
            return True

        xs = [i[0] for i in self.vertices]
        ys = [i[1] for i in self.vertices]

        # if the point is outside of the polygon's bounding
        # box, it's not in the polygon
        if (x > max(*xs) or x < min(*xs)) or \
           (y > max(*ys) or y < min(*ys)):
            return False

        xp1, yp1 = self.vertices[-1]  # Start with first and last vertices
        count = 0
        for xp2, yp2 in self.vertices:
            # Check if point is between lines y=yp1 and y=yp2
            if y <= max(yp1, yp2) and y >= min(yp1, yp2):
                # Get the intersection with the line that passes
                # through p1 and p2
                x_inters = float(xp2-xp1)*float(y-yp1)/float(yp2-yp1)+xp1

                # If x is less than or equal to x_inters,
                # we have an intersection
                if x <= x_inters:
                    count += 1
            
            xp1, yp1 = xp2, yp2

        # If the intersections are even, the point is outside of
        # the polygon.
        return count % 2 != 0

    def collide_polygon(self, polygon):
        # Check for same polygon
        if self == polygon or self.vertices == polygon.vertices:
            return True

        # Sort by vertex number to reduce the number of iterations
        polys = sorted([self, polygon], key=lambda x: len(x.vertices))
        rpolys = tuple(reversed(polys))

        # Check for common vertices
        vs = (tuple(i) for i in polys[1].vertices)
        for x, y in polys[0].vertices:
            if (x, y) in vs:
                return True

        # Collide each point with the other polygon
        for p in rpolys:
            for x, y in p.vertices:
                if polys[rpolys.index(p)].collide_point(x, y):
                    return True

        return False

    def collide_widget(self, wid):
        if isinstance(wid, Polygon):
            p = wid
        else:
            p = Polygon(vertices=[(0, 0),                  # bottom left
                                  (wid.width, 0),          # bottom right
                                  (wid.width, wid.height), # top right
                                  (0, wid.height)],        # top left
                        x=wid.x, y=wid.y)

        return self.collide_polygon(p)

class MultiShapePolygon(Polygon):
    shape = NumericProperty(0)
    shapes = ListProperty([])
    _shapes = []

    def __init__(self, **kwargs):
        super(MultiShapePolygon, self).__init__(**kwargs)
        self.shapes = self._shapes
        self.bind(shape=self.update_vertices)
        self.update_vertices()

    def random_shape(self, *args):
        self.shape = random.randint(0, len(self.shapes) - 1)

    def update_vertices(self, *args):
        self.abs_vertices = self.shapes[self.shape]["vertices"]