首页 文章

点和椭圆(旋转)位置测试:算法

提问于
浏览
12

如何测试点P = [xp,yp]是否在由中心C = [x,y],a,b和phi(旋转角度)给出的某个旋转椭圆的内部/外部?

此时我正在使用以下解决方案:旋转椭圆并用角度-phi指向,然后对点的位置和“非旋转”椭圆进行常见测试 .

但是有很多测试点(数千),我觉得这个解决方案很慢 . 有没有直接和更有效的方法来获得旋转椭圆和点的位置?

我不需要代码而是算法 . 谢谢你的帮助 .

5 回答

  • 1

    另一种选择是将所有内容都放入2D旋转椭圆的等式中,并查看结果是否小于1 .

    因此,如果以下不等式为真,则在椭圆内部有一个点

    ellipse equation

    其中(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}]
    
  • 0

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

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

    如果您将椭圆视为单位圆(半径1),按(a,b)缩放,按phi旋转并由(x,y)变换,则生活变得更加容易 . 如果您有转换矩阵,则可以使用它来执行更容易的包含查询 . 如果将点变换为椭圆为单位圆的坐标系,则您所要做的就是点对点圆测试,这是一项微不足道的测试 . 如果“变换”是一个矩阵,如上所述将单位圆变换为椭圆,那么

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

    这是算法,我让你开发代码:

    • 确定椭圆中心和点之间的向量v1

    • 确定世界坐标中矢量v1和x轴之间的角度a1

    • 从a1中减去phi得到a2,我们在局部坐标系中的矢量角度

    • 在局部坐标中以角度a2确定椭圆上的点P2,而不是(x,y)偏移

    • 计算L1和L2,矢量长度为a1和a2

    评价:

    • 如果L1 <L2,则该点位于内部

    • 如果L1 = L2(加/减小公差),则该点位于椭圆上

    • 如果L2> L2,则该点在外面

    椭圆参数公式:

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

    在-pi和pi之间有效 . 将phi添加到u以旋转椭圆 .

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

    祝好运!

  • 23

    Matplotlib在补丁类中有一个Ellipse方法,它允许您询问一个点是在补丁内部还是外部的问题 . 检查here并查找方法contains_point() . 您将需要使用Ellipse类创建椭圆,然后就好像内部有一个点 . BTW,matplotlib是python的一个包 .

相关问题