Всех приветствую. Возник такой вопрос, который наполовину связан с игрой и наполовину с программированием. В ходе разработки функций отрисовки нестандартных форм для областей (круги), возникла проблема: нужен алгоритм для размещения клеток-квадратов по точкам с координатами (это все будущие ячейки регионов, которые в сумме дадут круг). Нашел алгоритм Брезенхэма, который помог отрисовать окружности, но этого недостаточно, так как нужно круг затушевать. Как это реализовать?
P.S.: на скриншоте привожу пример, как в игре будут располагаться ячейки региона (отрисованы круги с радиусами 1 и 2 в точке (0;0), при наложении остаются пробелы; смещение координат там не учитывалось (при добавлении ячейки региона в точке образуется она выше и правее от указанной точки со стороной 32).

Принятый ответ

Я бы определял принадлежность центров квадрата некой окружности. Не так интуитивно-однозначно как проверка принадлежности всех точек квадрата окружности, но гораздо удобнее с точки зрения реализации. Далее для каждой строки поочередно прогоняем алгоритм заливки(в случае, если заливка подразумевает заливку текстурой почвы - стоит учитывать что каждый квадрат почвы имеет размеры 32/32 и центры мелких квадратиков имеют смещение в 16.), закрашивая почву в пределах новоопределенных ректов. Поочередно построчно, т.к. возможно у вас возникнет ситуация черное-белое-черное-белое и вторая строка (если весь массив прогонять подряд, а не построчно) начнется с черного квадрата. Не вижу каких-либо вытекающих неудобств при разработке..
`
ОЖИДАНИЕ РЕКЛАМЫ...
2
13
6 лет назад
Отредактирован Пушистый
2
Сам код алгоритма для нахождения координат точек окружности, в которых нужно создать квадрат (функция для добавления круга в регион на стадии разработки, поэтому аргумент регион в ней отсутствует).
void plot_circle(int x, int y, int x_center, int  y_center)
{
    BJDebugMsg(I2S(x_center+x)+"..."+I2S(y_center+y));
    BJDebugMsg(I2S(x_center+x)+"..."+I2S(y_center-y));
    BJDebugMsg(I2S(x_center-x)+"..."+I2S(y_center+y));
    BJDebugMsg(I2S(x_center-x)+"..."+I2S(y_center-y));
}

/* Вычерчивание окружности с использованием алгоритма Брезенхэма */
void RegionAddCircle(int x_center, int y_center, int radius)
{
    int x,y,delta;
    x = 0;
    y = radius;
    delta=3-2*radius;
    while(x<y) {
        plot_circle(x,y,x_center,y_center);
        plot_circle(y,x,x_center,y_center);
        if (delta<0)
            delta+=4*x+6;
        else {
            delta+=4*(x-y)+10;
            y--;
        }
        x++;
    }

    if(x==y) {
        plot_circle(x,y,x_center,y_center);
    }
}
0
17
6 лет назад
0
Попробуй сделать шаблон под 1 квадрат, и используя конкретные х/у, заполнить область:
0 = квадрата нет, 1= он есть
0|1|1|1|0
1|0|1|0|1
1|1|x|1|1
1|0|1|0|1
0|1|1|1|0
Х - это центр, где нет квадрата
возьмём 2 за единицу меры, на основе от неё уже будем считать
т.е. допустим 0:0 - это сам центр твоего круга
квадраты сторонами 2х2
имея это, получаем точки центров квадратов: x:y
-4:4 | -2:4 | 0:4 | 2:4 | 4:4
-4:2 | -2:2 | 0:2 | 2:2 | 4:2
-4:0 | -2:0 | 0:0 | 2:0 | 4:0
-4:-2 | -2:-2 | 0:-2 | 2:-2 | 2:-2
-4:-4 | -2:-4 | 0:-4 | 2:-4 | 4:-4
Берём эти координаты, умножаем единицу например на 20, и получаем круг с квадратами 40х40, и общей площадью 200х200
Дальше лупом расставляешь центры квадратов и создаёшь их. Можешь пронумеровать, типо 1-16, а 17-25 закрасить
В идеале, можешь сделать круги:
1й круг - 1 клетка 1х1
2й круг - 9 клеток 3х3
3й круг - 25 клеток 5х5
4й круг - 49 клеток 7х7
5й круг - 81 клетка 9х9
6й круг - 121 клетка 11х11
7й круг - 169 клеток 13х13
8й круг - 225 клеток 15х15
9й круг - 289 клеток 17х17
10й круг - 361 клетка 19х19
МБ легче будет написать алгоритм центров для этих кругов
например
-38:38| ... | 38:38
...........................
-38:-38| ... | 38:-38
и уже нарисовав один раз полный "круг" из необходимого кол-ва квадратов, уже будет понятно, какие квадраты зашриховывать, а какие нет
Загруженные файлы
4
28
6 лет назад
4
Пушистый, тебе нужно создать квадраты внутри окружности в шахматном порядке?
это делается через относительные координаты с проверкой на чётность нечётность
если нужно заполнить всё содержимое окружности квадратами то это заливка
0
13
6 лет назад
0
nvc123, нужен плотный круг без промежутков (его размер зависит от аргумента - радиуса).
0
28
6 лет назад
0
Пушистый, тогда заливка
ссылку скинул
0
13
6 лет назад
0
Есть идея сделать такую заливку круга через квадрат (проходиться циклом по ширине с шагом в ширину маленького квадрата, т. е. 32). Этот цикл сделать как составляющую цикла по высоте. Сама основа цикла - сравнение расстояний к центру окружности (если оно больше, чем радиус, точку удалять как основу для пикселя-ячейки региона и ее там не создавать). Вариант громоздкий + не известно, что из этого получится. Может, найдется алгоритм попроще.
0
20
6 лет назад
0
Перечитывал-перечитывал, но так и не понял что вы хотите получить в игре и с какими проблемами вы столкнулись. Возможно всё описанное логично, но, имхо, оно требует переформулировки.
0
13
6 лет назад
0
Diaboliko, возможно. Попробую иначе. Если изложить суть попроще: представим координатную плоскость (x,y). Нужен алгоритм отрисовки пиксельного круга на данной плоскости (в игре пикселями будут ячейки региона - cell'ы).
2
20
6 лет назад
2
Пушистый, чем вас не устраивает формула окружности?
2
20
6 лет назад
2
Я бы определял принадлежность центров квадрата некой окружности. Не так интуитивно-однозначно как проверка принадлежности всех точек квадрата окружности, но гораздо удобнее с точки зрения реализации. Далее для каждой строки поочередно прогоняем алгоритм заливки(в случае, если заливка подразумевает заливку текстурой почвы - стоит учитывать что каждый квадрат почвы имеет размеры 32/32 и центры мелких квадратиков имеют смещение в 16.), закрашивая почву в пределах новоопределенных ректов. Поочередно построчно, т.к. возможно у вас возникнет ситуация черное-белое-черное-белое и вторая строка (если весь массив прогонять подряд, а не построчно) начнется с черного квадрата. Не вижу каких-либо вытекающих неудобств при разработке..
Принятый ответ
0
13
6 лет назад
Отредактирован Пушистый
0
Diaboliko, просто когда вчера нашел алгоритм самого контура подумал, что наверное уже был изобретен костыль для всей фигуры)
DemonoiD, которая (x-a)^2+(y-b)^2=R^2? Да, это даже лучше, чем проверять расстояния.
По тестам получилось нечто похожее на круг (этот регион был сложен из кусочков - маленьких ячеек). Благодаря регистрации входа/выхода удалось зафиксировать результат. Нужно посмотреть, что произойдет с большими окружностями (пока что делюсь первыми результатами).
Круг с бОльшими размерами. Чем больше размер, тем точнее получается фигура. Замысел воплотить удалось, всем спасибо за помощь.
Загруженные файлы
0
20
6 лет назад
0
Пушистый, давай, удачи. В следующий раз, прежде чем морочить голову старикам с хгм, гугли матан :)
Чтобы оставить комментарий, пожалуйста, войдите на сайт.