Как правильно растеризовать окружность без повторов и нарушения симметрии?

#алгоритм #lua

Я пытаюсь создать круг из объектов (ящиков) для мода из одной игры, используя этот код:

function circle(x,y,r)
local angle = 0

x = x + 0.5 - (x + 0.5) % 1
y = y + 0.5 - (x + 0.5) % 1
r =  r + 0.5 прибавляю 0.5 чтобы объект появлялся в центре клетки
    while angle < 2*math.pi do
    angle = angle + r/r^2

    local xs = (x  +   r * math.cos (angle))
    local ys = (y  +   r * math.sin (angle))
game.surfaces[1].create_entity{name = "wooden-chest", position= {xs,ys},force='player'}
--создание объекта с указанными координатами
end end 


Объекты могут размещаться только в середине клетки. то есть если координаты например
будут х=0.9 у=0.9, то объект разместиться на координатах х=0.5 у=0.5
Также и с отрицательными координатами х=-0.9 у=-0.9 ==> х=-0.5 у=-0.5.
Создаем окружность: circle(0,0,15)



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



Что нужно поправить в этой функции, чтобы окружность правильно проходила через середины
клеток? Возможно мне бы помог Алгоритм Брезенхе́ма или алгоритм окружности Midpoint,
но я не знаю как написать их на lua, так как еще довольно слаб в программировании. 
UPD: Я попробовал преобразовать этот код на C++ в Lua:

public static void BresenhamCircle(Graphics g, Color clr, int _x, int _y, int radius)
    {
        int x = 0, y = radius, gap = 0, delta = (2 - 2 * radius);
        while (y >= 0)
        {
            PutPixel(g, clr, _x + x, _y + y, 255);
            PutPixel(g, clr, _x + x, _y - y, 255);
            PutPixel(g, clr, _x - x, _y - y, 255);
            PutPixel(g, clr, _x - x, _y + y, 255);
            gap = 2 * (delta + y) - 1;
            if (delta < 0 && gap <= 0)
            {
                x++;
                delta += 2 * x + 1;
                continue;
            }
            if (delta > 0 && gap > 0)
            {
                y--;
                delta -= 2 * y + 1;
                continue;
            }
            x++;
            delta += 2 * (x - y);
            y--;
        }
    }
function bresenham_circle(X1,Y1,R)

       local  x = 0 local y = R local gap = 0 local delta = (2 - 2 * R)
        while (y >= 0) do 

        game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 + x,
Y1 + y},force='player'}
        game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 + x,
Y1 - y},force='player'}
        game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 - x,
Y1 + y},force='player'}
        game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 - x,
Y1 - y},force='player'}
            gap = 2 * (delta + y) - 1
            if (delta >= 0 and gap > 0) then 
            if (delta <= 0 and gap <= 0) then 
            y = y - 1
            x =x+1
            delta = delta +2 *(x-y)
            else y=y - 1  delta = delta-2*y+1
            end
            else     x=x+1 delta = delta+ 2 * x + 1
            end

        end
        end


Но я получаю Овал, на одну клетку смещенный от центра по обоим осям, а также имеющий
дубль-размещение в 4 местах
UPD2: Смещение решилось добавлением 0.5 к x и y

Сейчас мой код выглядит так:

function bresenham_circle(X1,Y1,R)
local R = R+0.5
local  x = 0.25 
local y = R 
local gap = 0 
local delta = (2 - 2 * R)
while (y >= 0) do 

    game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 + x, Y1 -
y},force='player'}
    game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 - x, Y1 -
y},force='player'}
    game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 - x, Y1 +
y},force='player'}
    game.surfaces[1].create_entity{name = "wooden-chest", position= {X1 + x, Y1 +
y},force='player'}        

    gap = 2 * (delta + y) - 1
    if (delta >= 0 and gap > 0) then 
        if (delta <= 0 and gap <= 0) then 
            y = y - 1
            x =x+1
            delta = delta +2 *((x)-(y))
            else   delta = delta-2*(y-1)+1 y=y - 1
        end
        else      delta = delta+ 2 * (x+1) + 1 x=x+1
    end
end end


Повторов нет с любым радиусом, но все еще нет симметрии. Любые подсказки?

    

Ответы

Ответ 1

Вот код алгоритма Брезенхема, написанный при помощи PascalABC, и работающий по "восьмушкам"
- внутри каждого квадранта точки ставятся в направлении от краев квадранта вовнутрь.
Изначально был недостаток - повторно ставятся точки на позициях 0,pi/2,pi,2pi/3. Это
можно поправить сравнением величин (y-y1)+y1 и -(y-y1)+y1, (x-x1)+x1 и -(x-x1)+x1.
Если среди них есть хоть одно равенство (от смены знака "дельты" (то есть (y-y1) или
(x-x1)) не изменилась координата), то не ставить точку. 

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

procedure brez;
var x,y,x1,y1,r:integer;
e:real;
begin
x1:=250;
y1:=250;
r:=200;
x:=x1;
y:=y1+r;
e:=3-2*(r);
while (x-x1)<(y-y1) do
begin
    putpixel((x-x1)+x1,(y-y1)+y1,clRed);
    putpixel((y-y1)+y1,-(x-x1)+x1,clRed);
    putpixel(-(x-x1)+x1,-(y-y1)+y1,clRed);
    putpixel(-(y-y1)+y1,(x-x1)+x1,clRed);
    if not( ( ((x-x1)+x1) = (-(x-x1)+x1) ) or ( ((y-y1)+y1)=(-(y-y1)+y1) ) ) then
    begin
        putpixel((y-y1)+y1,(x-x1)+x1,clRed);
        putpixel((x-x1)+x1,-(y-y1)+y1,clRed);
        putpixel(-(y-y1)+y1,-(x-x1)+x1,clRed);
        putpixel(-(x-x1)+x1,(y-y1)+y1,clRed)
    end;
if e<0 then
    e:=e+4*(x-x1)+6 
else
begin
    e:=e+4*(x-x1-y+y1)+10; 
    y:=y-1
end;
x:=x+1
end;
if x=y then
  begin
    putpixel((x-x1)+x1,(y-y1)+y1,clRed);
    putpixel((y-y1)+y1,(x-x1)+x1,clRed);
    putpixel((y-y1)+y1,-(x-x1)+x1,clRed);
    putpixel((x-x1)+x1,-(y-y1)+y1,clRed);
    putpixel(-(x-x1)+x1,-(y-y1)+y1,clRed);
    putpixel(-(y-y1)+y1,-(x-x1)+x1,clRed);
    putpixel(-(y-y1)+y1,(x-x1)+x1,clRed);
    putpixel(-(x-x1)+x1,(y-y1)+y1,clRed); 
  end
end;