#!/usr/bin/env python3

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __add__(self, other):
        assert isinstance(other, Point)
        return Point(self.x + other.x, self.y + other.y)
    def __sub__(self, other):
        assert isinstance(other, Point)
        return Point(self.x - other.x, self.y - other.y)
    def __mul__(self, other):
        assert isinstance(other,int) or isinstance(other, float)
        return Point(self.x*other, self.y*other)
    def __str__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"
    def __repr__(self):
        return "Point" + str(self)
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    def __ne__(self, other):
        return not self.__eq__(other)

class Line:  # either a line, ray or line segment, depending on the context
    def __init__(self, p, q):
        self.p = p
        self.q = q
    def dist(self):
        return self.q - self.p
    def __str__(self):
        return str(self.p) + "-" + str(self.q)
    def __repr__(self):
        return "Line(" + repr(self.p) + "," + repr(self.q) + ")"
    def __eq__(self, other):
        return self.p == other.p and self.q == other.q
    def __ne__(self, other):
        return not self.__eq__(other)

def tri_area(p, q, r):
    'Returns twice the signed area of triangle p->q->r'
    return ( p.x * q.y - p.y * q.x +
             p.y * r.x - p.x * r.y +
             q.x * r.y - r.x * q.y )

def intersect(l, m):
    'Returns the intersection point of lines l and m.'
    dl = l.dist()
    dm = m.dist()
    det = dm.x*dl.y - dl.x*dm.y
    if det == 0: return None   # lines are parallel
    d = m.p - l.p
    f = (dm.x*d.y - dm.y*d.x)/det
    return l.p + dl*f

def clip(l, m):
    'Returns the line segment l clipped against the semiplane defined by m.'
    a = tri_area(m.p, m.q, l.p)
    b = tri_area(m.p, m.q, l.q)
    if a >= 0 and b >= 0: return l     # entirely on the semiplane
    if a <= 0 and b <= 0: return None  # entirely outside the semiplane
    i = intersect(l, m)  # l and m cannot be parallel here
    if a < 0: return Line(i, l.q)  # l.p is clipped away
    if b < 0: return Line(l.p, i)  # l.q is clipped away
    assert 0   # if I classified correctly, this can't happen!

def compress(a):
    'Compresses a polygon by removing duplicate edges.'
    return [ p for (i,p) in enumerate(a) if a[i-1] != p ]

def intersect_polygons(a, b):
    'Returns the intersection of two polygons, which must be convex!'
    for side in [ Line(b[i-1], b[i]) for i in range(len(b)) ]:
        # Find points in polygon a after clipping to side:
        c = []
        for i in range(len(a)):
            l = clip(Line(a[i-1], a[i]), side)
            if l: c += [l.p, l.q]
        # Remove duplicate endpoints:
        a = [ p for (i,p) in enumerate(c) if p != c[i-1] ]
    return a

a = [ Point(1,1), Point(5,3), Point(4,6) ]
b = [ Point(1,1), Point(7,3), Point(2,6) ]
c = intersect_polygons(a, b)
print(c)