我正在用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个交点(无交点、相切、部分重叠、部分重叠和内部相切以及完全重叠)。
我发现了一些潜在的解决方案:
关于如何计算交叉口有什么建议吗?速度(可能需要计算很多交叉口)和优雅是主要标准。代码将是美妙的,但即使是一个好的方向去将是有益的。
您可以使用此处显示的方法:https://math.stackexchange.com/questions/864070/how-to-determine-if-two-ellipse-have-at-least-one-intersection-point/864186#864186
首先,您应该能够在一个方向上重新缩放椭圆。为此,需要将椭圆的系数计算为二次曲线,重新缩放,然后恢复椭圆的新几何参数:中心、轴、角度。
然后你的问题减少到找到从椭圆到原点的距离。要解决最后一个问题,你需要一些迭代。这里有一个可能的独立实现。。。
在数学中,需要将椭圆表示为二元二次方程,然后求解它。我找到一个doucument。所有计算都在文档中,但用Python实现可能需要一段时间。
因此,另一种方法是将椭圆近似为多段线,并使用shapely查找交点,下面是代码:
以及输出:
在我的电脑上大约需要1.5毫秒
看着sympy我觉得它有你需要的一切。 (我试图向您提供示例代码;不幸的是,我未能使用gmpy2安装sympy,而不是无用的python内置数学)
你有:
从他们的例子来看,我认为绝对有可能相交于两个椭圆:
编辑:由于sympy不支持一般椭圆(ax^2+bx+cy^2+dy+exy+f)
你应该自己建立方程并转换它们,然后用它们的解算器来寻找交点。
相关问题 更多 >
编程相关推荐