15,998,003 members
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 ?
VB
polygon1 = [(1,0),(3,0),(3,2),(1,2),(1,0)]
polygon2 = [(0,1),(2,1),(2,3),(0,3),(0,1)]

Python
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
else:
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)
Posted
[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" ;-)
—SA
[no name] 25-Dec-14 6:45am
Thanks for the hint, I will do it.
Bruno

## Solution 1

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: http://en.wikipedia.org/wiki/Linear_algebra[^].

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 http://en.wikipedia.org/wiki/Numerical_stability#Stability_in_numerical_linear_algebra[^].

You can consider using some available mathematics library. You can start, for example, here:
http://en.wikipedia.org/wiki/Comparison_of_linear_algebra_libraries[^],
https://www.quantconnect.com/blog/top-numerical-libraries-for-c[^],
http://www.dotnumerics.com/NumericalLibraries/LinearAlgebra[^].

—SA

[no name] 24-Dec-14 11:20am
5++.

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).
Bruno
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.
—SA
[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.
Bruno
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...
—SA
[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 ..is 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 :)
Bruno

## Solution 2

Be familiar with elementary vector algebra helps a lot, so see solution #1 by SA.

An implementation you can find e.g. here: http://sourceforge.net/projects/polyclipping/[^]

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

Bruno

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

Top Experts
Last 24hrsThis month
 OriginalGriff 80 Wendelius 60 Richard Deeming 25 Pete O'Hanlon 25 Aggeliki Asimakopoulou 10
 OriginalGriff 511 Pete O'Hanlon 250 Richard Deeming 200 Dave Kreskowiak 133 CPallini 110

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