javascript - 以通用方式从 ARC 中提取顶点

Question

我想从 ARC 中获取所有顶点。我拥有将用于绘制弧线的所有数据(例如:起点、终点、起点 Angular 、终点 Angular 、半径)，但我的需要是我必须从弧线数据生成所有顶点。

我已经尝试过一种或两种算法，但未能从弧数据中获取确切的顶点。

我使用了 Bresenham 的算法，但失败了。

现在我正在使用下面的代码，但它不起作用..

            double theta = 2 * 3.1415926 / 100; 
            double c = Math.cos(theta);
            double s = Math.sin(theta);
            double t;

            double x = ((ArcTo) element).getRadius();//we start at angle = 0 
            double y = 0; 

            for(int ii = 0; ii < 100; ii++) { 
              coordinates.add(new Coordinate(x + element.getCenterPoint().getX(), y + element.getCenterPoint().getY()));//output vertex 

              //apply the rotation matrix
              t = x;
              x = c * x - s * y;
              y = s * t + c * y;
            }

请帮帮我。谢谢。

Answer 1

1. 首先做一些说明

   我假设顶点是指像素，ARC是标准的2D圆弧(不是椭圆弧!!! ) 并且您的输入数据是:

   int (x0,y0),(x1,y1) // star/end points on curve !!!
   float a0,a1         // start end angles [rad]
   int (xc,yc)         // center of circle
   int r               // radius
   

2. 不要使用 Bresenham

   因为您需要从零 Angular 开始并计算所有像素，直到达到起点。然后翻转绘图标志，这样你就可以从那个点开始填充像素并在终点命中时停止。此外，您还需要处理绕组以匹配 ARC 方向。

3. 可以用圆参数方程

   // just some arc data to test with
   float r=25.0;
   float a0= 45.0*M_PI/180.0;
   float a1=270.0*M_PI/180.0;
   int xc=100,x0=xc+floor(r*cos(a0)),x1=xc+floor(r*cos(a1));
   int yc=100,y0=yc+floor(r*sin(a0)),y1=yc+floor(r*sin(a1));
   // arc rasterize code
   int x,y;
   float a,da;
   // here draw pixels x0,y0 and x1,y1 to avoid rounding holes ...
   if (r) da=0.75/float(r); else da=0.1; // step slightly less then pixel to avoid holes
   for (a=a0;;a+=da)
    {
    x=xc+int(floor(r*cos(a)));
    y=yc+int(floor(r*sin(a)));
    // here draw pixel x,y
    if ((x==x1)&&(y==y1)) // stop if endpoint reach
     if (fabs(a-a1)<da)   // but ignore stop if not at end angle (full or empty circle arc)
      break;
    }
   

   可能是 round而不是 floor将有较少的像素位置误差。如果您的端点不匹配，那么这将无限循环。如果你稍微调整一下结束条件，你甚至可以避免这种情况或重新计算 x1,y1来自 a1因为我有...

4. 您可以使用等式 (x-xc)^2+(y-yc)^2=r^2

   您需要将 ARC 划分为象限，并将每个象限作为单独的弧循环处理 x或 y并计算另一个坐标。循环变化较大的坐标

   

   所以在蓝色区域循环y在红色环路中 x .例如红色区号可以是这样的:

   int x,y;
   for (x=_x0;;x++)
    {
    y=sqrt((r*r)-((x-xc)*(x-xc)));
    // here draw pixel x,y
    if (x==_x1) // stop if endpoint reach
     break;
    }
   

   你需要计算(_x0,_y0),(_x1,_y1)在象限内开始 ARC 切割部分的终点并制作 _x0<=_x1 .

   
   _x 的值循环的起点/终点坐标将为 xc +/- sqrt(r)或 x0或 x1
_y的值循环的起点/终点坐标将为 yc +/- sqrt(r)或 y0或 y1

   蓝色部分以类比方式完成(只需交换/替换 x 和 y )。由于切割，这种方法有点复杂，但可以仅在整数上完成。 sqrt可以通过LUT(限制最大半径)和^2来加速还可以进一步优化。

[注释]

因此，如果我概括一下，参数方程是最容易实现但最慢的。然后是sqrt可以像 Bresenham 一样快地完成的方法(使用 LUT 可能更快)但需要代码将 ARC 切割到需要很少的象限 if s 在渲染之前。

所有代码都在 C++ 中，可以进一步改进，比如避免一些 int/float转换，在循环之前预先计算一些值，等等......

最后去 Bresenham，但你需要改变里面的一些东西，当你不知道自己在做什么时，你很容易迷路。它还需要切割成八分圆，因此变化的复杂性远大于 sqrt。方法