Hi,to answer our original question. The extra intersection points are caused by the code which checks for intersection of endless lines. The lines extent to both sides into infinity. To get the right intersections you should check if the resulting points are in the "domains" of the input lines. I'm sure there is an easier way to do this, but see below how I did this.
def linesIntersection(A, B, C, D):
x1 = A[0]
y1 = A[1]
x2 = B[0]
y2 = B[1]
x3 = C[0]
y3 = C[1]
x4 = D[0]
y4 = D[1]
# print x1, y1, x2, y2, " ", x3, y3, x4, y4
# print x3, y3, x4, y4
denomenator = (((x1-x2)*(y3-y4)) - ((y1-y2)*(x3-x4)))
#print denomenator
if denomenator == 0:
return denomenator
else:
P1 = (((x1*y2 - y1*x2)*(x3-x4)) - ((x1-x2)*(x3*y4-y3*x4)))
Px = P1 / denomenator
P2 = (((x1*y2 - y1*x2)*(y3-y4)) - ((y1-y2)*(x3*y4-y3*x4)))
Py = P2 / denomenator
## print "Px: {0}, min(x)={1}, max(x)={2}".format(Px, min(x1, x2), max(x1, x2))
## print "Px: {0}, min(x)={1}, max(x)={2}".format(Px, min(x3, x4), max(x3, x4))
## print "Py: {0}, min(y)={1}, max(y)={2}".format(Py, min(y1, y2), max(y1, y2))
## print "Py: {0}, min(y)={1}, max(y)={2}".format(Py, min(y3, y4), max(y3, y4))
if Px >= min(x1, x2) and Px <= max(x1, x2):
if Px >= min(x3, x4) and Px <= max(x3, x4):
if Py >= min(y1, y2) and Py <= max(y1, y2):
if Py >= min(y3, y4) and Py <= max(y3, y4):
print " - The Intersection points are: ", Px, Py
polygon1 = [(1,0),(3,0),(3,2),(1,2),(1,0)]
polygon2 = [(0,1),(2,1),(2,3),(0,3),(0,1)]
poly1 = len(polygon1)
poly2 = len(polygon1)
# print poly1,poly2
for i in range(0, poly1-1):
A = polygon1
B = polygon1[i+1]
for j in range(0, poly2-1):
C = polygon2
D = polygon2[j+1]
linesIntersection(A, B, C, D)