当前位置：文江博客话题详情

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

发布于 2024-12-12 21:05:29 字数 218 浏览 0 评论 0原文

如何测试点 P = [xp,yp] 是否位于由中心 C=[x,y]、a、b 和 phi（旋转角度）给出的某个旋转椭圆内部/外部？

此时我正在使用以下解决方案：将椭圆和点旋转角度 -phi，然后对点和“非旋转”椭圆的位置进行常见测试。

但有很多测试点（数千个），我发现这个解决方案很慢。有没有直接且更有效的方法来获取旋转椭圆和点的位置？

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

缱倦旧时光 2024-12-19 21:05:31

为了处理椭圆，我更喜欢将它们转换到另一个坐标系，其中椭圆是以原点为中心的单位圆。

如果您将椭圆视为单位圆（半径为 1），按 (a,b) 缩放，按 phi 旋转并按 (x,y) 变换，那么生活就会变得容易多了。
如果您有该变换矩阵，您可以使用它来进行更简单的包含查询。如果将点变换到椭圆是单位圆的坐标系中，那么您所要做的就是进行单位圆内的点测试，这很简单。
如果“变换”是一个将单位圆变换为椭圆的矩阵，那么

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

To deal with ellipses I prefer to transform them to another coordinate system where the ellipse is a unit circle centered at the origin.

If you see the ellipse as a unit circle (radius 1), scaled by (a,b), rotated by phi and transformed by (x,y), then life becomes a lot easier.
If you have that transform matrix you can use it to do an easier containment query. If you transform the point to be in the coordinate system where the ellipse is a unit circle, all you have to do is a point-in-unit circle test which is trivial.
If "transform" is a matrix that transforms a unit circle into your ellipse as described, then

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

回复收藏 0 原文

↘紸啶 2024-12-19 21:05:31

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

确定椭圆中心和你的点之间的向量 v1
确定向量 v1 和世界坐标中的 x 轴之间的角度 a1
从 a1 中减去 phi 得到 a2，即本地坐标中的向量角度
确定椭圆上局部坐标系中角度 a2 处的点 P2，不偏移 (x, y)
计算 L1 和 L2，即 a1 和 a2 的向量长度

评估：

如果 L1 < L2 点在椭圆内部
如果 L1 = L2（加/减小公差），则点在椭圆上
如果 L2 > L2 L2 该点在

椭圆之外参数公式：

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

对于 -pi 和 +pi 之间的 u 有效。将 phi 添加到 u 来旋转椭圆。

上述算法可以由椭圆方程进行简化和优化。

祝你好运！

回复收藏 0 原文

不寐倦长更 2024-12-19 21:05:31

Matplotlib 在 patch 类中有一个 Ellipse 方法，它允许您询问一个点是否在 patch 内部或外部。检查此处并查找方法 contains_point()。您需要使用 Ellipse 类创建椭圆，然后就好像内部有一个点一样。
顺便说一句，matplotlib 是 python 的一个包。

回复收藏 0 原文

只是在用心讲痛 2024-12-19 21:05:30

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

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

ellipseequation

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

我实现了一个小型 Mathematica 程序，证明这确实有效：
Manipulate screen shot

这是实际操作：

Animation

这是代码：

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

Another option is just to throw everything into the equation for a 2D rotated ellipse and see if the result is less than one.

So a point is inside the ellipse if the following inequality is true

ellipse equation

Where (xp,yp) are the point coordinates and (x0, y0) is the center of the ellipse.

I implemented a small Mathematica program demonstrating that this indeed works:
Manipulate screen shot

Here it is in action:

Animation

And here is the code:

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

回复收藏 0 原文

情深如许 2024-12-19 21:05:30

您只需将数据输入上述公式即可。这是我根据 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

You can simply feed your data into the formula stated above. Here is a python implementation I made on Ajasja's recommendations:

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

回复收藏 0 原文

~没有更多了~