同一区域内轨迹与圆的交点

Question

我是编码新手。现在我有一个问题。我有一个在矩形区域中不断移动的对象。而且我在这方面也有很多圈子。我想得到轨迹和所有圆之间的所有交点。由于物体是一步一步移动的，所以我想我可以计算出物体的位置与每个圆的所有圆心之间的距离，并将该距离与圆的半径进行比较。但我认为这会做很多计算，因为你需要计算每一步的距离。你有什么好的想法或参考。顺便说一句，我在 python 上醒来。谢谢你。由于我没有足够的声誉，我无法添加有关问题的图片

Answer 1

除非你的轨迹已经是一条直线，否则你可能想要计算它的分段线性近似值。然后，对于每个线段，您可以使用二次方程计算 line-circle intersections，并检查交点是否真实（而不是复杂的，如果线经过圆并且平方根下的项变为负数）以及是否它们在线段上（与线段超出端点的部分相对）。

假设你有一条线段从 (x1,y1) 到 (x2 ,y2) 并希望与以 (xc,yc) 为中心的圆相交，半径为r。那么你要解方程

((1 - t)*x1 + t*x2 - xc)² + ((1 - t)*y1 + t*y2 - yc)² = r²

如果您根据 t 的幂收集项，您将在 t 中得到以下二次方程：

                      ((x1 - x2)² + (y1 - y2)²)*t²
+ 2*((x1 - x2)*(xc - x1) + (y1 - y2)*(yc - y1))*t
+                ((xc - x1)² + (yc - y1)² - r²)    = 0

因此您可以在 Python 代码中编写如下（未经测试）：

def circleSegmentIntersections(x1, y1, x2, y2, xc, yc, r):
    dx = x1 - x2
    dy = y1 - y2
    rx = xc - x1
    ry = yc - y1
    a = dx*dx + dy*dy
    b = dx*rx + dy*ry
    c = rx*rx + ry*ry - r*r
    # Now solve a*t^2 + 2*b*t + c = 0
    d = b*b - a*c
    if d < 0.:
        # no real intersection
        return
    s = math.sqrt(d)
    t1 = (- b - s)/a
    t2 = (- b + s)/a
    if t1 >= 0. and t1 <= 1.:
        yield ((1 - t1)*x1 + t1*x2, (1 - t1)*y1 + t1*y2)
    if t2 >= 0. and t2 <= 1.:
        yield ((1 - t2)*x1 + t2*x2, (1 - t2)*y1 + t2*y2)

如果你的轨迹是弯曲的但有一些很好的数学描述，比如自由落体抛物线或贝塞尔曲线或类似的东西，那么你可以避免分段线性近似并尝试直接计算交点。但是这样做很可能需要找到一些高阶多项式的根，这只能通过数字来完成。

Answer 2

一般来说，我会建议先让你的算法工作，然后在需要时让它更快。您会惊讶于 Python 与一组精心挑选的库相结合的速度有多快。

所以对于你的问题，我会做以下事情：

1.) 安装一组让您的生活更轻松的库： - Matplotlib 用于矩形、圆形和 2D 绘图轨迹

2.) 用于通用数组操作的 Numpy

3.) 可选 Scipy 用于 KDTree 支持（最近邻搜索）

4.) 开始实施你的问题 a.) 创建一个矩形并使用 Matplotlib

将其可视化

b.) 创建一组圆圈并将它们绘制在4a

的矩形区域内

c.) 创建轨迹并绘制在矩形区域内

现在更困难的部分开始了。前进的道路在一定程度上取决于您的轨迹是如何定义的。例如，如果您的轨迹由线段组成，您可以通过分析计算圆和线段之间的交点。存在三种可能的解决方案，无交叉、1 个交叉（线接触圆）和 2 个交叉。如果你的轨迹更复杂，你可以通过沿着它生成许多点来离散化它，而不是计算这个点是否在其中一个圆的边缘。尽管如何识别 3 种可能的解决方案，但您必须有点聪明，因为轨迹上的点是有限的。

另一种选择是也将圆圈边缘的点离散化。这意味着问题在很大程度上减少了最近邻搜索，您可以使用 Scipy KDTree class。

Answer 3

设 a 是介于较大圆的半径和直径之间的某个数字（如果它们具有不同的半径）。

生成边长为a的正方形方块网格，因此grid(i,k)是从(i*a,k*a)到((i+1)*a, (k+1)*a)的正方形。

网格的每个图块都包含一个列表，其中包含指向圆的指针或圆数组的索引。

对于每个圆，将它与它相交的每个图块进行注册。应该小于 4.

现在测试圆相交轨迹的点(x,y)。包含在相应的磁盘中，你只需要根据 tile ((int)(x/a), (int)(y/a).

中的圆圈列表进行测试

同一区域内轨迹与圆的交点

The intersection between a trajectory and the circles in the same area

python

geometry

intersection