在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++实现那样快。