查找两个椭圆的交点(Python) [英] Finding intersection points of two ellipses (Python)

问题描述

我正在用Python写一个基本的2D形状库(主要是用于处理SVG绘图)，而我对如何有效地计算两个椭圆的交点不知所措.

I'm writing a basic 2D shape library in Python (primarily for manipulating SVG drawings), and I'm at a loss for how to efficiently calculate the intersection points of two ellipses.

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

Each ellipse is defined by the following variables (all floats):

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个相交点(无相交，切线，部分重叠，部分重叠和内部切线以及完全重叠).

Ignoring when the ellipses are identical, there could be 0 through 4 intersection points (no intersection, tangent, partially overlapping, partially overlapping and internally tangent, and fully overlapping).

我找到了一些可能的解决方案:

I've found a few potential solutions:

• SymPy几何模块-此基本上只是将椭圆方程式插入SymPy的求解器中.我不确定在没有求解器的情况下这是否有意义. (顺便说一句，我本来会使用SymPy而不是自己动手，但在处理疯狂的浮动时效果却很糟糕)
• 如何检测椭圆是否与圆相交(碰撞)-这可能适用于两个椭圆，但是我对于如何将其转换为明智的代码有点模糊.
• 椭圆与椭圆的交点如何?-答案引用(CADEMIA)的库可能有很好的算法，但是我甚至无法弄清楚它是否是开源的.
• 维基百科:与两个圆锥形相交-我没有足够的了解线性代数以了解此解决方案.

• SymPy geometry module - This basically just plugs the ellipse equations into SymPy's solver. I'm not sure whether this makes sense without already having the solver. (Incidentally, I would have used SymPy instead of rolling my own, but it performs horribly when dealing with crazy floats)
• How to detect if an ellipse intersects(collides with) a circle - This could probably be adapted for two ellipses, but I'm a little fuzzy on how to turn it into sensible code.
• How Ellipse to Ellipse intersection? - The library the answer references (CADEMIA) might have a good algorithm, but I can't even figure out if it's open source.
• Wikipedia: Intersecting Two Conics - I don't have enough of a grasp of linear algebra to understand this solution.

关于如何计算交点的任何建议?速度(可能必须计算很多交叉点)和优雅是主要标准.代码会很棒，但是即使输入正确的方向也会有所帮助.

Any suggestions on how I should go about calculating the intersections? Speed (it might have to calculate a lot of intersections) and elegance are the primary criteria. Code would be fantastic, but even a good direction to go in would be helpful.

推荐答案

在数学中，您需要将椭圆表示为二元二次方程，然后对其进行求解.我发现了文件.所有的计算都在文档中，但是用Python实现可能要花一些时间.

In math, you need to express the ellipses as bivariate quadratic equations, and solve it. I found a doucument. All the calculations are in the document, but it may take a while to implement it in Python.

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

So another method is to approximate the ellipses as polylines, and use shapely to find the intersections, here is the code:

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])

和输出:

在我的PC上大约需要1.5毫秒.

It takes about 1.5ms on my PC.

这篇关于查找两个椭圆的交点(Python)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！