I want to calculate the intersection points of polygons ?

Question

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 24-Dec-14 2:07am

Ahsan Abbas

Add a Solution

Comments

[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

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Sergey Alexandrovich Kryukov · Accepted Answer · 2014-12-24T05:07:00

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

User 11060979 · Accepted Answer · 2014-12-25T00:44:00

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

Posted 25-Dec-14 0:44am

User 11060979

Comments

[no name] 17-Jan-15 7:38am

Thank you for accepting.
Bruno