I want to calculate the intersection point of two polygon, the polygons are illustrate in picture. The picture clearly show that there are two points

of intersections.

I have write some code, but there is problem init, it's calculate more than two intersection point. Blow is my code...

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

#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 "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(poly1-1):

A = polygon1[i]

B = polygon1[i+1]

for j in range(poly2-1):

C = polygon2[j]

D = polygon2[j+1]

linesIntersection(A, B, C, D)

I am using determinant for calculating the intersection of point. http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

There is a condition both lines should be similar planes, this is where problem begin, i don't know how to do it ? Pleas help me...

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[i]

B = polygon1[i+1]

for j in range(0, poly2-1):

C = polygon2[j]

D = polygon2[j+1]

linesIntersection(A, B, C, D)

Kind regards, Xander

edit: for some strange reason the code isn't formatting...