Click here to Skip to main content
15,669,526 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
There is problem in it, it's calcuate more than two intersection point, but actually its has two, if you could draw the points two polygon would form. Please help me what is wrong in code ?
polygon1 = [(1,0),(3,0),(3,2),(1,2),(1,0)]
polygon2 = [(0,1),(2,1),(2,3),(0,3),(0,1)]

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)))
    if denomenator != 0:
        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
        return None
    if Px == Py:
        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)
[no name] 24-Dec-14 8:18am    
I suggest to use vector geometries ;)

like this[^]
Sergey Alexandrovich Kryukov 25-Dec-14 1:39am    
Why no posting it as a formal answer? If you look at the recent OP's comment to my answer, you will find that he is looking for a "quick solution" ;-)
[no name] 25-Dec-14 6:45am    
Thanks for the hint, I will do it.

You need to know elementary vector algebra to do it. This is not so simple problem as it may seem, due to two reasons: 1) the presence of of special (or "pathological") cases, when two straight lines are parallel or are the same, 2) due to approximate character of calculations.

The basic algorithm is this: each side of a polygon is defined by the coordinate of the two points of the vertices. You can take each pair of sides of two polygons and examine it. Formally, you represent each side as an equation of the straight line; for another side of another polygon, you have another straight line equation; and then you solve to pair of algebraic equations to find if there is an intersection, which is the point when x and y of two sides are equal. In case you find the intersection, you need to perform an additional check: the location of this point should belong to the line segment of each of the two sides. This is not always the case. You can have the intersection, but it could be found on the "continuation" of one of both segments. You have to do this check for each pair of sides of both shapes.

If you need to learn the related mathematics, you can try to find some publicly accessible material referenced, for example, on this page:[^].

But this is not all. You will need to address two difficulties I mentioned in my first paragraph above. What happens when some two segments are "almost parallel" and intersect at some point in the close vicinity of the point sets represented by each of the side? In such cases, the presence of intersection is surprisingly difficult to detect.

To get a general idea, please see[^].

You can consider using some available mathematics library. You can start, for example, here:[^],[^],[^].

Share this answer
[no name] 24-Dec-14 11:20am    

Quote: "You need to know elementary vector algebra to do it":
I agree totally, that is the thing. More or less a thing easy to learn (I had the luck to have a teacher, who was able to convey it in an easy way).
Sergey Alexandrovich Kryukov 24-Dec-14 11:26am    
Thank you, Bruno.
You are right, this is a pretty easy branch of mathematics. But mathematics becomes enormously more complicated when it comes to approximate numeric calculations.
[no name] 24-Dec-14 11:40am    
Yes so it is. Just remember my problems with convex hulls. Intersections of polygons sound a lot more easier ...on a first glance... on a second not. I need to dive into it by myself.
Sergey Alexandrovich Kryukov 24-Dec-14 11:54am    
If fact, I'm pretty much sure that convex hull is much easier in this aspect... :-)
Picture this "almost parallel" straight lines and imaging what happens. The angle between two almost parallel straight lines could be made closer and closer to zero, so the loss of precision can be as big as possible, far beyond the accuracy of any thinkable floating-point type...
[no name] 24-Dec-14 12:15pm    
"In fact" I suppose you mean.
And yes, these "parallel straight lines" bother me in a similar way with Singular Value Decomposition and Amoeba to get the solution of the equations which I have to solve day by day ;) Always the same question: Is it now a solution it the best solution? When I can stop to search for a better solution....Numerical precision ...I like to have the perfect computer with no limit on precision :)
Be familiar with elementary vector algebra helps a lot, so see solution #1 by SA.

An implementation you can find e.g. here:[^]

A lot of polygon intersection algorithms works only with convex polygons, so take care about the description of it (if available).

Share this answer
[no name] 17-Jan-15 7:38am    
Thank you for accepting.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900