用多边形逼近椭圆

Question

我正在处理地理信息,最近我需要绘制一个椭圆.为了与OGC约定兼容,我不能原样使用椭圆; 相反,我使用多边形近似椭圆,通过采用椭圆包含的多边形并使用任意多个点.

我用于为给定数量的点N生成椭圆的过程如下(使用C#和虚构的Polygon类):

Polygon CreateEllipsePolygon(Coordinate center, double radiusX, double radiusY, int numberOfPoints)
{
    Polygon result = new Polygon();
    for (int i=0;i<numberOfPoints;i++)
    {
        double percentDone = ((double)i)/((double)numberOfPoints);
        double currentEllipseAngle = percentDone * 2 * Math.PI;
        Point newPoint = CalculatePointOnEllipseForAngle(currentEllipseAngle, center, radiusX, radiusY);
        result.Add(newPoint);
    }
    return result;
}

到目前为止,这对我很有帮助,但我注意到它有一个问题:如果我的椭圆是'矮胖',也就是说,radiusX比radiusY大得多,那么椭圆顶部的点数就是与椭圆左侧的点数相同.

这是浪费点的使用!在椭圆的上半部分添加一个点几乎不会影响多边形近似的精度,但在椭圆的左边部分添加一个点会产生重大影响.

我真正喜欢的是用多边形逼近椭圆的更好算法.我需要这个算法:

• 它必须接受点数作为参数; 可以接受每个象限中的点数(我可以在"有问题"的位置迭代地添加点,但我需要很好地控制我使用的点数)
• 它必须以椭圆为界
• 它必须包含正上方,正下方,直线向左,直线到椭圆中心右侧的点
• 它的面积应该尽可能接近椭圆的面积,当然优先考虑给定的点数(参见Jaan的答案 - 显然这个解决方案已经是最优的)
• 多边形中的最小内角是最大的

我想到的是找到一个多边形,其中每两条线之间的角度总是相同的 - 但不仅我不知道如何产生这样的多边形,我甚至不确定是否存在,甚至如果我删除限制!

有没有人知道如何找到这样的多边形？

Answer 1

finding a polygon in which the angle between every two lines is
always the same

对的,这是可能的.我们想要找到(第一个)椭圆象限的这些点,这些点中的切线角度形成等距(相同的角度差)序列.不难发现切线

x=a*Cos(fi)
y=b*Sin(Fi)

derivatives
dx=-a*Sin(Fi), dy=b*Cos(Fi)
y'=dy/dx=-b/a*Cos(Fi)/Sin(Fi)=-b/a*Ctg(Fi) 

导数y'描述切线,该切线具有角度系数

k=b/a*Cotangent(Fi)=Tg(Theta)
Fi = ArcCotangent(a/b*Tg(Theta)) = Pi/2-ArcTan(a/b*Tg(Theta)) 

由于互补角度的关系

其中Fi从0变化到Pi/2,而Theta - 从Pi/2变为0.
因此,每个象限找到N + 1个点(包括极值点)的代码可能看起来像(这是Delphi代码生成附图)

  for i := 0 to N - 1 do begin
    Theta := Pi/2 * i /  N;
    Fi :=  Pi/2 - ArcTan(Tan(Theta) * a/b);
    x := CenterX + Round(a * Cos(Fi));
    y := CenterY + Round(b * Sin(Fi));
  end;
  // I've removed Nth point calculation, that involves indefinite Tan(Pi/2) 
  // It would better to assign known value 0 to Fi in this point

完美角度多边形的草图:

Answer 2

我建议你切换到极坐标：

极坐标下的椭圆为：

x(t) = XRadius * cos(t)
y(t) = YRadius * sin(t)

为了0 <= t <= 2*pi

当 Xradius >> YRadius（或 Yradius >> Yradius）时会出现问题

您可以使用显然不完全相同的角度数组，而不是使用 numberOfPoints。angle = 2*pi*n / 36 radiants即，每个部分均分 36 个点并平分。当您在这两个值的“邻域”中得到 n = 0（或 36）或 n = 18 时，近似方法效果不佳，因为椭圆扇形与用于近似它的三角形显着不同。您可以减小该点周围的扇区大小，从而提高精度。不仅仅是增加点的数量，还会增加其他不需要的区域的段。角度的顺序应该类似于（以度为单位）：

angles_array = [5,10,10,10,10.....,5,5,....10,10,...5]

第一个 5 度。t = 0 时的序列是 t = pi 时的第二个序列，最后一个序列又约为 2*pi。