在python中，找到直线和圆的交点的最有效方法是什么？

Question

我有一个由许多点组成的多边形。我想找到多边形和圆的交集。提供[x0，y0]的圆心和r0的半径，我写了一个粗函数来简单求解圆和直线的二次方程。但是，一个接一个地找到多边形的每个线段的交集的效率如何呢？有更有效的方法吗？

我知道sympy已经提供了获取不同几何体交点的功能。但是如果我想处理大量的多边形，那么与用我自己的函数计算相比，sympy这样的外部库的效率如何？

def LineIntersectCircle(p,lsp,lep):
# p is the circle parameter, lsp and lep is the two end of the line
  x0,y0,r0 = p
  x1,y1 = lsp
  x2,y2 = esp
  if x1 == x2:
    if abs(r0) >= abs(x1 - x0):
        p1 = x1, y0 - sqrt(r0**2 - (x1-x0)**2)
        p2 = x1, y0 + sqrt(r0**2 - (x1-x0)**2)
        inp = [p1,p2]
        # select the points lie on the line segment
        inp = [p for p in inp if p[1]>=min(y1,y2) and p[1]<=max(y1,y2)]
    else:
        inp = []
  else:
    k = (y1 - y2)/(x1 - x2)
    b0 = y1 - k*x1
    a = k**2 + 1
    b = 2*k*(b0 - y0) - 2*x0
    c = (b0 - y0)**2 + x0**2 - r0**2
    delta = b**2 - 4*a*c
    if delta >= 0:
        p1x = (-b - sqrt(delta))/(2*a)
        p2x = (-b + sqrt(delta))/(2*a)
        p1y = k*x1 + b0
        p2y = k*x2 + b0
        inp = [[p1x,p1y],[p2x,p2y]]
        # select the points lie on the line segment
        inp = [p for p in inp if p[0]>=min(x1,x2) and p[0]<=max(x1,x2)]
    else:
        inp = []
  return inp

Answer 1

我想也许你的问题是理论上如何以最快的方式来做这件事。但是如果你想快速地做这件事，你应该使用C/C++编写的东西。

我已经习惯了Shapely，所以我将提供一个如何使用这个库的示例。python有许多几何库。我将在这个答案的末尾列出它们。

from shapely.geometry import LineString
from shapely.geometry import Point

p = Point(5,5)
c = p.buffer(3).boundary
l = LineString([(0,0), (10, 10)])
i = c.intersection(l)

print i.geoms[0].coords[0]
(2.8786796564403576, 2.8786796564403576)

print i.geoms[1].coords[0]
(7.121320343559642, 7.121320343559642)

在Shapely中有点反直觉的是，圆是具有缓冲区的点的边界。这就是我为什么要p.buffer(3).boundry

交集i也是一个几何图形列表，在本例中这两个图形都是点，这就是为什么我必须从i.geoms[]中获取这两个图形

这里有another Stackoverflow question为感兴趣的人详细介绍了这些库。

• SymPy
• CGAL Python bindings
• PyEuclid
• PythonOCC
• Geometry-simple

编辑，因为注释：

Shaffy是基于GEOS（Trac.OsGeo.org/GeOS）的，它是用C++构建的，比在Python中自己编写的任何东西都快得多。SymPy似乎是基于mpmath（mpmath.org）的，它看起来也是python，但是似乎集成了很多非常复杂的数学。实现自己可能需要大量的工作，并且可能不会像GeOS C++实现那样快。

Answer 2

一个低成本的空间分隔可能是把飞机分成9块

这是一张糟糕的图表。想象一下，如果你愿意的话，这些线只是接触到圆圈。

  | |
__|_|__
__|O|__
  | |
  | |

我们感兴趣的区域中有8个围绕着这个圆圈。中间的正方形对于一个便宜的测试来说用处不大，但是你可以在圆内放置一个r/sqrt(2)的正方形，所以它的角只是接触圆。

允许标记区域

A |B| C
__|_|__
D_|O|_E
  | |
F |G| H

中心的r/sqrt(2)的平方我们称之为J

我们将调用图中所示的中心正方形中不在J，Z中的点集

用它的字母代码标记多边形的每个顶点。

现在我们可以很快看到

AA => Outside
AB => Outside
AC => Outside
...
AJ => Intersects
BJ => Intersects
...
JJ => Inside

这可以变成一个查找表

因此，根据您的数据集，您可能已经为自己节省了大量工作。但是，任何端点位于Z中的内容都需要进行测试。

Answer 3

我认为你用来计算两个交点坐标的公式不能再优化了。唯一的改进（在数值上是重要的）是区分这两种情况：|x_2-x_1| >= |y_2-y_1|和|x_2-x1| < |y_2-y1|，这样k的数量总是在-1和1之间（在计算中，如果| x|2-x|1|非常小，则可以得到非常高的数值误差）。您可以交换x-s和y-s以将一种情况减少到另一种情况。

您还可以实现初步检查：如果两个端点都在圆的内部，则没有交点。通过计算点到圆中心的平方距离，这就变成了一个不使用平方根函数的简单公式。另一个检查：“行是否在圆之外”已经在代码中实现，并且对应于delta<；0。如果你有很多小段，这两个检查应该给出一个捷径答案（没有交叉点）在大多数情况下。