Как нарисовать эллиптический сектор с помощью алгоритма Брезенхэма?

Как я могу нарисовать заполненный эллиптический сектор, используя алгоритм Брезенхема и растровый объект с помощью метода DrawPixel?

Я написал метод рисования эллипса, но этот метод использует симметрию и пропускает только первый квадрант. Этот алгоритм не подходит для секторов. Я, конечно, могу написать 8 тактов, но думаю, что это не самое элегантное решение задачи.


math geometry graphics ellipse bresenham
person Nikolai Paukov    schedule 24.09.2018    source источник
comment
Вы должны указать, как параметризован ваш сектор. Сравните, например. java.awt.geom.Arc.Double с Эллиптическая дуга SVG, чтобы получить представление о различных параметризациях.   -  person MvG    schedule 25.09.2018
comment
Bresenham не подходит для этого (если вы не ограничены целочисленной математикой)   -  person Spektre    schedule 26.09.2018
comment
Мой сектор параметризован как java.awt.geom.Arc.Double. И я привязан к целочисленной математике.   -  person Nikolai Paukov    schedule 26.09.2018
comment
@NikolaiPaukov такая параметризация включает плавающую или фиксированную точку для углов .... Целочисленный стиль обычно использует линии разреза, как в GDI ... так что эллипс выровнен по оси? с известным центром, a, b и 2 углами? И углы являются числами с плавающей запятой или целыми числами и в каких единицах?   -  person Spektre    schedule 26.09.2018
comment
Да, эллипс выровнен по оси, а углы - целые числа в градусах.   -  person Nikolai Paukov    schedule 26.09.2018
comment
@NikolaiPaukov, как вы вычисляете cos и sin для целых чисел (используйте для этого числа с плавающей запятой, используйте LUT с целочисленной фиксированной точкой и в каком диапазоне или другое ...)? И какие это углы (в масштабе окружности или реального угла)?   -  person Spektre    schedule 27.09.2018

Ответы (1)


arrow_upward
0
arrow_downward

В целочисленной математике обычная параметризация заключается в использовании ограничивающих линий (в направлении по часовой стрелке или против часовой стрелки) вместо ваших углов. Итак, если вы можете преобразовать эти углы в такие (вам нужно sin,cos для этого, но только один раз), то вы можете использовать для этого рендеринг на основе целочисленной математики. Как я уже упоминал в комментарии, брезенхем не является хорошим подходом для сектора эллипса, так как вам нужно будет вычислить состояние внутренних итераторов и счетчиков для начальной точки интерполяции, а также он даст вам только точки окружности вместо заполненной формы.

Для этого есть много подходов, вот простой:

  1. преобразовать эллипс в круг

    просто путем изменения масштаба оси меньшего радиуса

  2. перебрать блок такого круга

    простые 2 вложенные for петли, охватывающие вписанный квадрат в нашу окружность

  3. проверить, находится ли точка внутри круга

    просто проверьте, есть ли x^2 + y^2 <= r^2, когда круг находится в центре (0,0)

  4. проверить, лежит ли точка между линиями края

    поэтому он должен быть по часовой стрелке с одним краем и против часовой стрелки с другим. Вы можете использовать для этого перекрестное произведение (его полярность координаты z скажет вам, находится ли точка по часовой стрелке или против часовой стрелки относительно тестируемой линии края)

    но это будет работать только до 180-градусных срезов, поэтому вам также нужно добавить некоторую проверку квадрантов, чтобы избежать ложных отрицательных результатов. Но это всего лишь несколько «если».

  5. если все условия соблюдены, преобразуйте точку обратно в эллипс и визуализируйте

Вот небольшой пример C++:

void elliptic_arc(int x0,int y0,int rx,int ry,int a0,int a1,DWORD c)    
    {
    // variables
    int  x, y, r,
        xx,yy,rr,
        xa,ya,xb,yb,                // a0,a1 edge points with radius r
        mx,my,cx,cy,sx,sy,i,a;
    // my Pixel access (you can ignore it and use your style of gfx access)
    int **Pixels=Main->pyx;         // Pixels[y][x]
    int   xs=Main->xs;              // resolution
    int   ys=Main->ys;
    // init variables
    r=rx; if (r<ry) r=ry; rr=r*r;   // r=max(rx,ry)
    mx=(rx<<10)/r;                  // scale from circle to ellipse (fixed point)
    my=(ry<<10)/r;
    xa=+double(r)*cos(double(a0)*M_PI/180.0);
    ya=+double(r)*sin(double(a0)*M_PI/180.0);
    xb=+double(r)*cos(double(a1)*M_PI/180.0);
    yb=+double(r)*sin(double(a1)*M_PI/180.0);
    // render
    for (y=-r,yy=y*y,cy=(y*my)>>10,sy=y0+cy;y<=+r;y++,yy=y*y,cy=(y*my)>>10,sy=y0+cy) if ((sy>=0)&&(sy<ys))
     for (x=-r,xx=x*x,cx=(x*mx)>>10,sx=x0+cx;x<=+r;x++,xx=x*x,cx=(x*mx)>>10,sx=x0+cx) if ((sx>=0)&&(sx<xs))
      if (xx+yy<=rr)                // inside circle
        {
        if ((cx>=0)&&(cy>=0)) a=  0;// actual quadrant
        if ((cx< 0)&&(cy>=0)) a= 90;
        if ((cx>=0)&&(cy< 0)) a=270;
        if ((cx< 0)&&(cy< 0)) a=180;
        if ((a   >=a0)||((cx*ya)-(cy*xa)<=0))           // x,y is above a0 in clockwise direction
         if ((a+90<=a1)||((cx*yb)-(cy*xb)>=0))
          Pixels[sy][sx]=c;
        }
    }

будьте осторожны, оба угла должны быть в диапазоне <0,360>. На моем экране y указывает вниз, поэтому, если a0<a1, это будет направление по часовой стрелке, которое соответствует маршруту. Если вы используете a1<a0, то диапазон будет пропущен, а вместо него будет отображаться остальная часть эллипса.

Этот подход использует a0,a1 как реальные углы!!!

Чтобы избежать делений внутри цикла, вместо этого я использовал 10-битные шкалы с фиксированной точкой.

Вы можете просто разделить это на 4 квадранта, чтобы избежать 4 внутренних циклов для повышения производительности.


x,y — точка на круговой шкале с центром в (0,0)
cx,cy — точка на эллиптической шкале с центром в (0,0)
sx,sy — точка на эллиптической шкале, переведенная в положение центра эллипса

Осторожно, мой доступ к пикселю Pixels[y][x], но большинство API используют Pixels[x][y], поэтому не забудьте изменить его на свой API, чтобы избежать нарушений прав доступа или поворота результата на 90 градусов...

person Spektre    schedule 27.09.2018