点和旋转椭圆位置测试：算法

Question

如何测试一个点P=[xp,yp]是否在以中心C=[x,y]、长轴a、短轴b和旋转角度phi表示的椭圆内/外？

目前，我使用以下解决方案：先将椭圆和点按角度-phi旋转，然后使用常规方法测试点的位置和“非旋转”椭圆。

但是由于需要测试大量的点（数千个），我发现这种方法速度较慢。有没有更快捷直接的方式来确定旋转椭圆和点的位置？

我不需要代码，只需要算法。感谢您的帮助。

- justik

---

展示一下你目前所做的工作，让我们看看有什么可以帮助你的。 - sjngm

Answer 1

另一种选择是将所有内容都放入二维旋转椭圆的方程中，然后查看结果是否小于1。

因此，如果以下不等式成立，则点位于椭圆内：

其中(xp,yp)为点坐标，(x0,y0)为椭圆中心。

我编写了一个小的Mathematica程序来演示这确实有效：

它的运行效果如下：

这是代码：

ellipse[x_, y_, a_, b_, \[Alpha]_, x0_: 0, y0_: 0] := 
     (((x - x0)*Cos[\[Alpha]] + (y - y0)*Sin[\[Alpha]])/a)^2
   + (((x - x0)*Sin[\[Alpha]] - (y - y0)*Cos[\[Alpha]])/b)^2;

Manipulate[
 RegionPlot[
  ellipse[x, y, a, b, \[Alpha] \[Degree], Sequence @@ pos] < 1, {x, -5, 5}, {y, -5, 5}, 
  PlotStyle -> If[ellipse[Sequence @@ p, a, b, \[Alpha] \[Degree], Sequence @@ pos] <= 1, Orange, LightBlue], 
  PlotPoints -> 25]
, {{a, 2}, 1, 5, Appearance -> "Labeled"}
, {{b, 4}, 2, 5, Appearance -> "Labeled"}
, {\[Alpha], 0, 180,  Appearance -> "Labeled"}
, {{p, {3, 1}}, Automatic, ControlType -> Locator}
, {{pos, {0, 0}}, Automatic, ControlType -> Locator}]

- Ajasja

Answer 2

你可以简单地将你的数据输入到上述公式中。这是我根据Ajasja的建议制作的Python实现：

def pointInEllipse(x,y,xp,yp,d,D,angle):
    #tests if a point[xp,yp] is within
    #boundaries defined by the ellipse
    #of center[x,y], diameter d D, and tilted at angle

    cosa=math.cos(angle)
    sina=math.sin(angle)
    dd=d/2*d/2
    DD=D/2*D/2

    a =math.pow(cosa*(xp-x)+sina*(yp-y),2)
    b =math.pow(sina*(xp-x)-cosa*(yp-y),2)
    ellipse=(a/dd)+(b/DD)

    if ellipse <= 1:
        return True
    else:
        return False

- Raoul

---

不要使用 math.pow(val, 2) 来计算平方。那样非常慢。（应先将其分配给一个变量，然后将该变量乘以自身）。 - Peter Cordes

math.sin和math.cos期望以弧度为单位的参数，因此请确保您传递的角度是以弧度为单位的。您可以使用math.radians函数将角度从度转换为弧度。 - Q2Learn

Answer 3

为了处理椭圆，我更倾向于将它们转换到另一个坐标系中，在这个坐标系中，椭圆是以原点为中心的单位圆。

如果你将椭圆看作一个单位圆（半径为1），通过(a,b)缩放、phi旋转和(x,y)变换，那么处理起来会更加容易。 如果你有这样的变换矩阵，你可以使用它来进行更简单的包含查询。如果将点转换到椭圆为单位圆的坐标系中，你只需要进行一个点在单位圆内的测试即可，这非常简单。 如果"transform"是一个将单位圆转换为描述你的椭圆的矩阵，那么：

transformedPoint = transform.Invert().Transform(point);
pointInEllipse = transformedPoint.DistanceTo(0,0) < 1.0;

- Anders Forsgren

Answer 4

这里是算法，我让你来开发代码：

1. 确定椭圆中心和你的点之间的向量v1
2. 在世界坐标系中确定向量v1与x轴之间的角度a1
3. 从a1中减去phi得到a2，我们在本地坐标系中的向量角度
4. 在本地坐标系中确定椭圆上角度为a2的点P2，不带偏移(x, y)
5. 计算L1和L2，即a1和a2的向量长度

评估：

1. 如果L1 < L2，则该点在内部
2. 如果L1 = L2（加/减小容差），则该点在椭圆上
3. 如果L2 > L2，则该点在外部

椭圆参数方程：

x = a*cos(u)
y = b*sin(u)

对于-u至+u之间的u有效。将phi添加到u以旋转您的椭圆。

上述算法可以从椭圆方程简化和优化。

祝你好运！

- rjobidon

Answer 5

Matplotlib在patches类中有一个椭圆方法，允许您询问一个点是否在补丁内或外。请查看这里并查找contains_point()方法。您需要使用Ellipse类创建椭圆，然后判断点是否在内部。 顺便说一下，matplotlib是Python的一个包。

- Jose Sergio Hleap