相关疑难解决方法(0)

如何检查2个段是否相交？

我有以下数据:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

我需要在python中编写一个小算法来检测2条线是否相交.

更新:

我找到了两种主要的方法来查看一个点是否属于多边形.一个是使用这里使用的光线跟踪方法,这是最推荐的答案,另一个是使用matplotlib path.contains_points(这对我来说似乎有点模糊).我将不得不连续检查很多点.有人知道这两个中的任何一个是否比另一个更值得推荐,或者是否有更好的第三选择？

更新:

我检查了两种方法,matplotlib看起来要快得多.

from time import time
import numpy as np
import matplotlib.path as mpltPath

# regular polygon for testing
lenpoly = 100
polygon = [[np.sin(x)+0.5,np.cos(x)+0.5] for x in np.linspace(0,2*np.pi,lenpoly)[:-1]]

# random points set of points to test 
N = 10000
points = zip(np.random.random(N),np.random.random(N))


# Ray tracing
def ray_tracing_method(x,y,poly):

    n = len(poly)
    inside = False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if …

我试图检测给定的点（x，y）是否在 n*2 数组的多边形中。但似乎多边形边界上的某些点返回它不包括在内。

def point_inside_polygon(x,y,poly):

    n = len(poly)
    inside =False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xinters = (y-p1y)*(p2x-p1x)/float((p2y-p1y))+p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x,p1y = p2x,p2y

    return inside