如何找到两个线段的交点？

Question

假设我们有两个有限的线段,每个线段由两个点(在两个空间中)定义.我想找到一种方法来获得这两条线的交点.最后,我想将其扩展到一组连接的线段.

我在这里找到了一个很好的解决方案:Python - matplotlib:找到线图的交集.然而,这依赖于scipy,我相信它需要BLAS,这是出于各种原因我想避免.

matplotlib有一个名为Path的模块,它有一个intersects_path()函数(http://matplotlib.org/api/path_api.html#matplotlib.path.Path.intersects_path),它对于交集的存在返回true或false,但是不是我要求的具体位置.

有谁知道这个干净的方法？

我想出的任何解决方案都很冗长,如果解决方案已经存在,我真的不想重新发明轮子.

谢谢!

Answer 1

为了完成,我想我会发布我使用的最终解决方案.

使用Shapely(https://pypi.python.org/pypi/Shapely)代码看起来就像这样简单:

from shapely.geometry import LineString

line1 = LineString([(0,0), (1,0), (1,1)])
line2 = LineString([(0,1), (1,1)])

print(line1.intersection(line2))

返回:

POINT (1 1)

关于这一点的好处是它将无缝地处理单点交叉和段的交叉,并且相同的技术可以应用于更复杂的对象.