我想计算多边形的交点？ [英] I want to calculate the intersection points of polygons ?

问题描述

它有问题，它计算超过两个交点，但实际上它有两个，如果你可以绘制两个多边形将形成的点。请帮我解决代码中出了什么问题？

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
    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)

推荐答案

你需要知道基本向量代数才能做到这一点。由于两个原因，这不是一个简单的问题：1）特殊（或病理）情况的存在，当两条直线平行或相同时，2）由于计算的近似特征。



基本算法是这样的：多边形的每一边都是由顶点的两个点的坐标定义的。您可以拍摄两个多边形的每一边并检查它。在形式上，你将每一边都表示为直线的方程;对于另一个多边形的另一边，你有另一个直线方程;然后你解决了一对代数方程，找出是否有一个交点，这是两边的x和y相等的点。如果找到交叉点，则需要执行额外检查：此点的位置应属于双方各自的线段。这并非总是如此。您可以拥有交集，但可以在两个段之一的延续中找到它。你必须检查两种形状的每一对。



如果你需要学习相关的数学，你可以尝试找一些可公开访问的材料例如，在此页面上： http://en.wikipedia.org/wiki/Linear_algebra [ ^ ]。



但这不是全部。你需要解决我在上面第一段中提到的两个困难。当两个部分几乎平行并且在每个边所代表的点集附近的某个点处相交时会发生什么？在这种情况下，交叉点的存在令人惊讶地难以检测。



要获得一般概念，请参阅 http://en.wikipedia.org/wiki/Numerical_stability#Stability_in_numerical_linear_algebra [ ^ ]。



您可以考虑使用一些可用的数学库。例如，你可以在这里开始：

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

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

熟悉基本向量代数有很多帮助，所以请参阅SA的解决方案＃



您可以找到的实施例如：这里： http://sourceforge.net/projects/polyclipping/ [ ^ ]



注：

很多多边形交叉算法只适用于凸多边形，所以要注意它的描述（如果有的话）。



Bruno

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

这篇关于我想计算多边形的交点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！