找到两个椭圆的交点(Python)

Question

我正在用Python编写一个基本的2D形状库(主要用于操作SVG绘图),我对如何有效地计算两个椭圆的交点感到茫然.

每个椭圆由以下变量(所有浮点数)定义:

c: center point (x, y)
hradius: "horizontal" radius
vradius: "vertical" radius
phi: rotation from coordinate system's x-axis to ellipse's horizontal axis

忽略椭圆相同时,可能有0到4个交点(没有交点,切线,部分重叠,部分重叠和内部切线,并且完全重叠).

我发现了一些潜在的解决方案:

• SymPy几何模块 - 这基本上只是将椭圆方程插入SymPy的求解器中.如果没有解算器,我不确定这是否有意义.(顺便说一句,我会使用SymPy而不是自己动手,但是在处理疯狂浮动时它会表现得非常糟糕)
• 如何检测椭圆是否与圆相交(碰撞) - 这可能适用于两个椭圆,但我对如何将其变成合理的代码有点模糊.
• 椭圆到椭圆的交点如何？ - 答案引用的库(CADEMIA)可能有一个很好的算法,但我甚至无法弄清楚它是否是开源的.
• 维基百科:相交两个圆锥曲线 - 我没有足够的线性代数来理解这个解决方案.

关于如何计算交叉点的任何建议？速度(它可能需要计算很多交叉点)和优雅是主要标准.代码会很棒,但即使是一个好的方向也会有所帮助.

Answer 1

在数学中,你需要将椭圆表示为二元二次方程,并求解.我找到了一个doucument.所有计算都在文档中,但在Python中实现它可能需要一段时间.

所以另一种方法是将椭圆近似为折线,并使用形状来找到交点,这里是代码:

import numpy as np
from shapely.geometry.polygon import LinearRing

def ellipse_polyline(ellipses, n=100):
    t = linspace(0, 2*np.pi, n, endpoint=False)
    st = np.sin(t)
    ct = np.cos(t)
    result = []
    for x0, y0, a, b, angle in ellipses:
        angle = np.deg2rad(angle)
        sa = np.sin(angle)
        ca = np.cos(angle)
        p = np.empty((n, 2))
        p[:, 0] = x0 + a * ca * ct - b * sa * st
        p[:, 1] = y0 + a * sa * ct + b * ca * st
        result.append(p)
    return result

def intersections(a, b):
    ea = LinearRing(a)
    eb = LinearRing(b)
    mp = ea.intersection(eb)

    x = [p.x for p in mp]
    y = [p.y for p in mp]
    return x, y

ellipses = [(1, 1, 2, 1, 45), (2, 0.5, 5, 1.5, -30)]
a, b = ellipse_polyline(ellipses)
x, y = intersections(a, b)
plot(x, y, "o")
plot(a[:,0], a[:,1])
plot(b[:,0], b[:,1])

和输出:

我的电脑需要大约1.5毫秒.