Алгоритм заполнения круга Брезенхема

Question

Я реализовал алгоритм «Брезенхема» (средняя точка) для построения кругов, и все прошло хорошо (C ++ и OpenGL).

Мне интересно, можно ли использовать тот же алгоритм для заполнениякруги?

Возьмем, к примеру, следующие несколько кругов: http://imgur.com/S0Qy6, которые построены по следующему алгоритму:

void circle(Point p, int r) {
int x = 0;
int y = r;
int f = 1-r;

// plot vert/horiz points indepedently

while (x<y) {
    x++;

    if (f<0) {
        f += 2*x+1;
    } else {
        y--;
        f += 2*(x-y+1);
    }

    glRecti(p.x+x, p.y+y, p.x+x+1, p.y+y+1);
    // plot other points using 8 way symmetry

    // attempt to fill the circle - didn't go well
    plotLine(Point(p.x, p.y+x), Point(p.x+x, p.y+x));

}

}

Я считаю лучшимместо для добавления бита заполнения будет в моем основном цикле, так как я хочу по существу заполнить каждый квадрант снова с помощью 8-сторонней симметрии.Поэтому я добавил свой вызов plotLine, но вместо этого получился странно закрашенный круг: http://imgur.com/jQW7B

Если я затем покрасил круги по-другому, я получу горизонтальные полосатые полосы, а не настоящие закрашенные круги -мой подход явно неправильный, но я не уверен, как это исправить.

Answer 1

Я не уверен, но, щурясь на ваш алгоритм, я ожидал, что последняя строка будет больше похожа на

plotLine(Point(p.x+x, p.y+x), Point(p.x+x, p.y+y));

(то есть начните с северо-восточной линии 45 градусов от р.х, затем поднимитесь до точки на круге, который вы только что нарисовали).

Answer 2

Насколько я помню, обычное дело это заполнять, используя либо горизонтальные, либо вертикальные линии.

То есть для каждой итерации, которую вы строите от квадранта I до квадранта II и от квадранта III до квадранта IV (где я выбрал горизонтальные линии).Обратите внимание, что вы получаете в общей сложности четыре строки из каждой итерации.

( p.x+x, p.y+y ) to ( p.x-x, p.y+y )
( p.x+y, p.y+x ) to ( p.x-y, p.y+x )
( p.x+x, p.y-y ) to ( p.x-x, p.y-y )
( p.x+y, p.y-x ) to ( p.x-y, p.y-x )

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

---

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