Алгоритмы рисования окружности

В интернете нашел несколько вариантов алгоритма отрисовки, но все они не подходят.
Есть такой код:

int x=500,y=500;
for(int r=0; r<100; r++)
  DrawCircle(x,y,r,clBlack);

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

Есть ли алгоритм, который для этого подходит?

Вот пример вывода закрашенной окружности

uses crt,DemoLib;
var
 FPS,FP:Word;  {Кадров в сикунду}
 CPS,CS:Word;
 i:Integer;
 ch:Char;
 Time,Time1:DWord;
 Fill:Boolean;
 
 XPos:array [0..Height-1,0..1] of Integer;
 
procedure SetPixel(x,y:Integer; Color:Byte);
begin
 if (x>=0) and (x<Width) and (y>=0) and (y<Height)
  then Buffer^[Word(y)*Width+x]:=Color;
end;
 
{Заполняем XPos граничными координатами}
procedure CircleEdge(xc,yc,r:Integer);
var y,x,d:Integer;
begin
 y:=r;
 x:=0;
 d:=3-2*r;
 while x<=y do
  begin
    if ((yc-y>=0) and (yc-y<Height)) then
        begin
            if ((xc-x)<0) then XPos[yc-y][0]:=0
             else if ((xc-x)>=Width)then XPos[yc-y][0]:=Width-1
              else XPos[yc-y][0]:=xc-x;
 
            if ((xc+x)<0) then XPos[yc-y][1]:=0
             else if ((xc+x)>=Width)then XPos[yc-y][1]:=Width-1
              else XPos[yc-y][1]:=xc+x;
        end;
    if ((yc+y>=0) and (yc+y<Height)) then
        begin
            if ((xc-x)<0)then XPos[yc+y][0]:=0
             else if ((xc-x)>=Width)then XPos[yc+y][0]:=Width-1
              else XPos[yc+y][0]:=xc-x;
 
            if ((xc+x)<0)then XPos[yc+y][1]:=0
             else if ((xc+x)>=Width)then XPos[yc+y][1]:=Width-1
              else XPos[yc+y][1]:=xc+x;
        end;
    if ((yc-x>=0) and (yc-x<Height)) then
        begin
            if ((xc-y)<0)then XPos[yc-x][0]:=0
             else if ((xc-y)>=Width)then XPos[yc-x][0]:=Width-1
              else XPos[yc-x][0]:=xc-y;
 
            if ((xc+y)<0)then XPos[yc-x][1]:=0
             else if ((xc+y)>=Width)then XPos[yc-x][1]:=Width-1
              else XPos[yc-x][1]:=xc+y;
        end;
    if ((yc+x>=0) and (yc+x<Height)) then
        begin
            if ((xc-y)<0) then XPos[yc+x][0]:=0
             else if ((xc-y)>=Width)then XPos[yc+x][0]:=Width-1
              else XPos[yc+x][0]:=xc-y;
 
            if ((xc+y)<0)then XPos[yc+x][1]:=0
             else if ((xc+y)>=Width)then XPos[yc+x][1]:=Width-1
              else XPos[yc+x][1]:=xc+y;
        end;
    if (d < 0) then d:= d + 4*x + 6
         else
          begin
          d:= d + 4*(x-y) + 10;
          Dec(y);
         end;            
    Inc(x);
  end;
end;
 
{Рисуем закрашенную окружность}
procedure FillCircle(xc, yc,r:Integer; Color:Byte);
var miny,maxy,y:Integer;
begin
    r:=r-1;
    if (((xc>=-r)and(xc<Width+r)and(yc>=-r)and(yc<Height+r))) then
     begin
        CircleEdge(xc,yc,r);
        if (xc<=0)then
            begin
            miny:=Round(yc-sqrt(Longint(r)*r-Longint(xc)*xc));
            maxy:=Round(yc+sqrt(Longint(r)*r-Longint(xc)*xc));
            end
         else if (xc>=Width) then
            begin
            miny:=Round(yc-sqrt(Longint(r)*r-Longint(Width-xc)*(Width-xc)));
            maxy:=Round(yc+sqrt(Longint(r)*r-Longint(Width-xc)*(Width-xc)));
            end
          else
            begin
              miny:=yc-r;
              maxy:=yc+r;
            end;
        if (miny<0)     then miny:=0;
        if (miny>=Height)then miny:=Height-1;
        if (maxy<0) then maxy:=0;
        if (maxy>=Height)then maxy:=Height-1;
        for y:=miny to maxy do
              HLine(XPos[y][0],XPos[y][1],y,Color);
     end;
end;
 
{Рисуем окружность}
procedure Circle(xc, yc,r:Integer; Color:Byte);
var y,x,d:Integer;
begin
x:=0;
y:=r;
d:=3-2*r;
while x <= y do
 begin
   SetPixel(xc+x, yc+y, Color);
   SetPixel(xc+y, yc+x, Color);
   SetPixel(xc+y, yc-x, Color);
   SetPixel(xc+x, yc-y, Color);
   SetPixel(xc-x, yc-y, Color);
   SetPixel(xc-y, yc-x, Color);
   SetPixel(xc-y, yc+x, Color);
   SetPixel(xc-x, yc+y, Color);
 if (d < 0) then
  begin
  d:= d + 4*x + 6
  end
  else begin
       d:= d + 4*(x-y) + 10;
       dec(y);
       end;
 inc(x);
 end;
end;
 
begin
clrscr; {очищаем экран}
SetMode13h; {устанавливаем графический режим}
Randomize;  {Для того чтобы числа были случайными}
Time:=TickCount;
Time1:=TickCount;
repeat
{Рисуем круги и огружности}
if Fill then FillCircle(random(100)+50,random(100)+50,random(10),Random(15))
 else  Circle(random(100)+50,random(100)+50,random(10),Random(15));
inc(CS); {Много кругов}
 
if TickCount-Time >1000 then
 begin
 FPS:=FP;
 FP:=0;
 CPS:=CS;
 CS:=0;
 Time:=TickCount;
 end;
 
if  (port[$3da] and 8)<> 0 then {Ждем обратного хода луча и выводим что успели нарисовать}
 begin                          {У меня ввиндоус переодически забирает контроль подвисает вывод}
 WriteText(10,10,'FPS:'+IntToStr(FPS),15);
 WriteText(10,18,'CPS:'+IntToStr(CPS),15); {Сравните циферку со стандартным выводом}
 Flip;
 inc(FP);
 Time1:=TickCount;
 end;
if keypressed then
 begin
 ch:=ReadKey;
 case ch of
 ' ':Fill:=Not Fill;
 end;
 end;
until ch=#27; {ESC выходим}
SetMode03h; {устанавливаем текстовый режим}
 
end.

Добавлено 02.05.11, 19:48

Цитата Sviat @ 02.05.11, 19:31

Есть ли алгоритм, который для этого подходит?

Если рисовать окружности в цикле то ничего не получится.
Есть алгоритм By. Но он только отчасти спасет тебя.
Можно взять разрешение картинки в 2 или 4 раза больше. Нарисовать свои круги в цикле. А потом усреднить, будет по лучше.

Прикреплённый файл3D.rar (67,82 Кбайт, скачиваний: 326)

Сообщение отредактировано: Pavia - 02.05.11, 19:53

А что, надо попиксельно рисовать?

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

Лучше расскажи о реальной задаче

Задача такова: есть друмерный массив, каждый элемент которого может быть 0 или 1. Для каждого нулевого элемента, нужно найти ближайший, по декартовому расстоянию, единичный элемент. Для этого я от каждого 0го прохожу вышеизложенным образом массив, до тех пор, пока не встретится 1ный элемент. А для этого нужно посетить ВСЕ элементы в некоем радиусе от исходного, что обычные алгоритмы не позволяют.

Sviat
Гугли на фразы "Euclidean distance maps" "Дистанционная карта" "дистанционное преобразование"


http://www.bsu.by/sm.aspx?guid=218873
http://www.cs.auckland.ac.nz/~rklette/TeachAuckland.html/mm/MI30slides.pdf

Сообщение отредактировано: Pavia - 03.05.11, 15:32

Цитата

В теории, после его работы должен получится круг, радиуса r, залитый черным цветом.

В какой такой теории? Заполненный круг может получиться, только если точки окружности сильно связаны (у каждой точки 2 соседа по вертикали и/или горизонтали, такой алгоритм использовал, например, старый добрый Autodesk Animator). В обычных же алгоритмах точки окружности слабо связаны (у каждой точки 2 соседа по вертикали, горизонтали и/или диагонали). С ними закрашенный круг таким способом не получить. Если задаться целью рисовать слабо связанные контуры, способные сложиться в закрашенную фигуру, то в итоге получится квадрат (или ромб).

Pavia, ты показал простой и красивый алгоритм Брезенхэма рисования окружности (Circle). Почему же процедура рисования круга такая громоздкая и уродливая? Что помешало вместо 8 точек нарисовать 4 горизонтальные линии?

P. S. Извиняюсь за офтопик :)

Если единичных точек немного, то диаграмма Вороного поможет

Цитата AVA12 @ 03.05.11, 16:59

В какой такой теории?

Логично предположить, что если на некоем абстрактном пространстве рисовать окружности, с радиусом отличающимся на 1, то будут покрыты все точки пространства. На прямоугольной сетке, конечно, погрешности возникают.

Цитата Pavia @ 03.05.11, 15:31

Гугли на фразы "Euclidean distance maps" "Дистанционная карта" "дистанционное преобразование"

Спасибо, обязательно почитаю.

Цитата MBo @ 03.05.11, 17:34

Если единичных точек немного, то диаграмма Вороного поможет

Диаграмма Вороного не подходит, т.к. алгоритм её построения не распараллеливается (по крайней мере то, что я видел).

Сообщение отредактировано: Sviat - 03.05.11, 18:29

Самый быстрый способ рисования закрашенного круга - модифицированный алгоритм Брезенхэма (классический алгоритм местами несколько притормаживает, но кроме него существует еще несколько похожих) с рисованием вместо точек целых отрезков.

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

Память есть в наличии?
Если да, то простой алгоритм обхода всех точек в круге, начиная из центра, может быть таким - генерируем все суммы квадратов Q = a^2 + b^2 такие, что b<=a и Q <=r^2, складываем тройки (a, b, Q) в в очередь по приоритетам по ключу Q.

Затем извлекаем каждую тройку из очереди, выводим восемь (или 4, если b = 0 или b = a, или 1, если a = 0) симметричных точек в разных квадрантах.

Сообщение отредактировано: MBo - 04.05.11, 03:38

Цитата amk @ 03.05.11, 19:32

А если единичных точек много, наверно неплохо должны работать иерархические структуры, квадродерево, к примеру

Вроде квадродерево, бесполезно для объектов еденичной площади.

Цитата MBo @ 04.05.11, 03:36

Если да, то простой алгоритм обхода всех точек в круге, начиная из центра, может быть таким - генерируем все суммы квадратов Q = a^2 + b^2 такие, что b<=a и Q <=r^2, складываем тройки (a, b, Q) в в очередь по приоритетам по ключу Q.

Затем извлекаем каждую тройку из очереди, выводим восемь (или 4, если b = 0 или b = a, или 1, если a = 0) симметричных точек в разных квадрантах.

Не очень понял идею. Очередь надо строить для каждого круга? или достаточно одного, на все возможные?
Вот допустим надо пройтись по окружности с центром (5,5) и r = 3;
Очередь получилась такая:
(0,0,0) 1 точка
(1,0,1) 4 точки
(1,1,2) 4 точки
(2,0,4) 4 точки
(2,1,5) 8 точек
(2,2,8) 4 точки
(3,0,9) 4 точки
По какому принципу координаты проверяемых точек получить?

Ещё не могу прикинуть сколько максимально памяти потребуется (с комбинаторикой всегда проблемы были), если учесть что максимально возможный радиус 2048? Думаю нереально много...

Добавлено 04.05.11, 12:50
Хотя, если матрицу 4096х4096 разбить на сетку по 21*21 то максимальный радиус - 96

Сообщение отредактировано: Sviat - 04.05.11, 12:50

>Очередь получилась такая:
Да, всё верно
Пример для точки (2,1,5)
Точку (2,1) отражаем в остальные 7 октантов коорд. плоскости
(2,1) (2,-1) (-2,1) (-2,-1) (1,2) (1,-2) (-1,2) (-1,-2)
это смещения, которые надо прибавлять к координатам центра

Памяти потребуется примерно на r^2/2 + 10 троек (на самом деле порядка восьмушки площади круга - Pi*r^2/8 + 2*r, а 10 - запас для маленьких кругов)

>максимально возможный радиус 2048?
примерно 25 мегабайт

Цитата Sviat @ 04.05.11, 12:42

Вроде квадродерево, бесполезно для объектов еденичной площади.

Может это называется и не квадродерево. Просто эта задача напоминает мне задачу "для данной точки найти ближайшую из заданного набора". А эта задача часто эффективно решается посредством двумерного хэширования - пространство накрывается сеткой ячеек, точки набора разносятся по ячейкам, для проверяемой точки вычисляется ее ячейка и ближайшая точка определяется простым перебором точек этой ячейки и соседних. Это, если точки распределены более-менее равномерно. При неравномерном выгоднее иерархическое деление (по-моему оно называется Q-дерево)

>Очередь надо строить для каждого круга? или достаточно одного, на все возможные?
Сразу не заметил этого вопроса.
Поскольку тебе нужно найти ближайшую точку, не обязательно генерировать все точки в круге сразу, а можно кольцами возрастающкго радиуса.
Это сэкономит память и время, но навскидку не скажу, удобно ли будет организовать генерацию точек в кольце (т.е. каковы будут излишние накладные расходы)

Цитата amk @ 04.05.11, 16:09

Может это называется и не квадродерево. Просто эта задача напоминает мне задачу "для данной точки найти ближайшую из заданного набора". А эта задача часто эффективно решается посредством двумерного хэширования - пространство накрывается сеткой ячеек, точки набора разносятся по ячейкам, для проверяемой точки вычисляется ее ячейка и ближайшая точка определяется простым перебором точек этой ячейки и соседних. Это, если точки распределены более-менее равномерно. При неравномерном выгоднее иерархическое деление (по-моему оно называется Q-дерево)

В принципе именно это я и делаю. Для того чтоб обойти соседние ячейки, содержащие точки, нужен алгоритм построения окружности, не пропускающий ни одной ячейки. К квадродереву (q-дереву) это не имеет ни какого отношения.

Mbo, спасибо большое, завтра попробую сделать такую штуку.

Если тебе надо найти одну ближайшую точку, то алгоритм построения окружности тебе мало поможет. Проще обходить последовательные вложенные квадраты (начинать лучше с середин сторон). Обход квадратов завершается, когда расстояние от точки до границы ячейки окажется больше расстояния до ближайшей найденной точки. По тому же условию заканчивается обход сторон. Получается обход в таком порядке (в порядке возрастания цифр, одинаковые цифры просматриваемые в любом порядке)

6 5 4 5 6
5 3 2 3 5
4 2 1 2 4
5 3 2 3 5
6 5 4 5 6

Ячейки должны содержать в среднем 2-8 точек. Если в стартовой ячейке есть хотя бы одна из искомых точек, осмотр прервется уже на ячейках помеченных 4, или даже раньше.
Такой порядок имеет то преимущество перед обходом окружностей, что он прост, и при поиске обычно просматривается не больше ячеек, чем при планируемом тобой (а часто и меньше).

Придумал, как всё в памяти не держать.

P.S. Поправил код, избавился от ненужного поля в TTriple

Размер очереди для r = 2000 не превышает 587 (грубо 0.3 * r для r такого порядка)

  TTriple = record
    a, b, Q: Integer;
  end;
 
  функция Triple создаёт структуру из a, b, вычисляя Q
 
  r := 6;
  r2 := r * r;
  MaxSize := 0;
  PQ:= TPriorityQueue.Create;
  t.a := 0;
  t.b := 0;
  t.Q := 0;
 
  PQ.Put(t);
  while True do begin
    t := PQ.Get;
    if t.Q > r2 then
      Break;
    if (t.Q < r2) and (t.b = 0) then
      PQ.Put(Triple(t.a + 1, 0));
    if (t.b < t.a) then
      PQ.Put(Triple(t.a, t.b + 1));
 
    if PQ.Count > MaxSize then //это просто контроль размера очереди
      MaxSize := PQ.Count;
    Memo1.Lines.Add(Format('%d %d  %d',[t.a, t.b, t.Q]));
  end;
  Memo1.Lines.Add(Format('Max Queue Size %d',[MaxSize]));
  PQ.Free;
 
даёт:
0 0  0
1 0  1
1 1  2
2 0  4
2 1  5
2 2  8
3 0  9
3 1  10
3 2  13
4 0  16
4 1  17
3 3  18
4 2  20
5 0  25
4 3  25
5 1  26
5 2  29
4 4  32
5 3  34
6 0  36
Max Queue Size 3

Сообщение отредактировано: MBo - 04.05.11, 19:56

Набросал вчера такой код:

struct Tri
{
 int a,b,Q;
 Tri(int A, int B, int q): a(A),b(B),Q(q) {}
};
list<Tri> dec;
int R = 100*100 // квадрат радиуса
dec.clear();
 for(int a=0,Q=0; Q<=R; a++)
   {
    for(int b=0; (b<=a)&&(Q<=R); b++)
      {
       Q = a*a+b*b;
       dec.push_back(Tri(a,b,Q));
      }
   }
 dec.erase(--dec.end());

Потом получаю из очереди точки:

 int x = 150;
 int y = 150;
 for(list<Tri>::iterator i=dec.begin(); i!=dec.end(); ++i)
   {
    Tri tri = *i;
    int a = tri.a,b = tri.b,Q = tri.Q;
    if(a == 0)
      {
       cnv->Pixels[x][y] = clBlack;
      }
    else if(b==0 || b==a)
      {
       cnv->Pixels[x+a][y+b] = clBlack;
       cnv->Pixels[x-a][y-b] = clBlack;
       cnv->Pixels[x-a][y+b] = clBlack;
       cnv->Pixels[x+a][y-b] = clBlack;
      }
    else
      {
       cnv->Pixels[x+a][y+b] = clBlack;
       cnv->Pixels[x+a][y-b] = clBlack;
       cnv->Pixels[x-a][y+b] = clBlack;
       cnv->Pixels[x-a][y-b] = clBlack;
 
       cnv->Pixels[x+b][y+a] = clBlack;
       cnv->Pixels[x+b][y-a] = clBlack;
       cnv->Pixels[x-b][y+a] = clBlack;
       cnv->Pixels[x-b][y-a] = clBlack;
      }
   }

На выходе получаю квадрат с слегка скруглёнными углами. Где я ошибся?

Добавлено 05.05.11, 12:56

Цитата amk @ 04.05.11, 18:23

Проще обходить последовательные вложенные квадраты (начинать лучше с середин сторон)

Это получится практически прямоугольный обход. Такое я уже делал, получалось оч плохо. Нужно именно по окружности обходить

>Где я ошибся?
Q надо сбрасывать в 0 после внутреннего цикла.


Код из Сообщ. #19 не требует держать в памяти все точки круга, а генерирует их практически по мере надобности.

Цитата MBo @ 05.05.11, 14:30

Q надо сбрасывать в 0 после внутреннего цикла.

Нет, очередь получается правильная. Ошибка либо в алгоритме либо в ф-и отрисовки.
Сейчас переписал ваш код на си, в результате тот же скруглённый квадрат.

неправильно переписал, значит
я твой код из #20 воспроизводил - действительно получался квадрат. Не сразу заметил, что Q во внутреннем цикле зашкаливает, и внешний цикл стопорится, поэтому получается квадрат, вписанный в искомый круг