Очередной алгоритмический вопрос. :: Создание игр :: Форум

Доброго времени суток, коллеги.

Есть очередной вопрос алгоритмического плана.
У меня используются алгоритмы Брезенхема для получения прямых, окружностей и эллипсов. Сейчас речь про окружности. Функция, которая генерит окружность, выдаёт массив (одномерный) с набором точек целевой окружности. Точки в массив набросаны как попало, потому как алгоритм генерит дугу для одного квадранта, и зеркалит их в оставшиеся три.
Что мне требуется - какой-то вариант, который бы позволил из выбранной точки, сделать несколько шагов по окружности (по часовой или против часовой стрелке). Т.е. я беру произвольную точку из массива и хочу обойти всю окружность из точки в точку.
Как это можно сделать? Как-то отсортировать массив? Но как? Как-то хитро его запонять? Опять же - как?

Для наглядности, есть окружность, координаты точек которой навалены в массив:

. . # # # . .

 . # . . . # . 

 # . . . . . #

 # . . . . . #

 # . . . . . #

 . # . . . # .

 . . # # # . .

Хочется, начав с произвольной точки А

. . # # # . .

. # . . . А .

# . . . . . #

# . . . . . #

# . . . . . #

. # . . . # .

. . # # # . .

иметь возможность обойти окружность по шагам

. . # # 1 . .

. # . . . А .

# . . . . . #

# . . . . . #

# . . . . . #

. # . . . # .

. . # # # . .

. . # 2 1 . .

. # . . . А .

# . . . . . #

# . . . . . #

# . . . . . #

. # . . . # .

. . # # # . .

. . 3 2 1 . .

. # . . . А .

# . . . . . #

# . . . . . #

# . . . . . #

. # . . . # .

. . # # # . .

и т.д. Окружность произвольного радиуса. Точка старта, направление и количество шагов тоже может быть произвольными.

редакция от Shirson, 11.10.2012 02:09

Опубликовано 11.10.2012 04:39 (12 лет назад) #

а в массив не проще запихать сгенеренную окружность
типа Circle:array[...] of Tpoint; ?

и потом хоть рандомом хоть чем - выбирай оттуда точку и вперед или назад двигай по индексу

либо извратно каждому элементу(точке окружности) в твоем одномерном массиве присвоить уникальный символ (только возникнет косяк сиволов то 256)
потом сканируешь свой получившийся бокс на наличие определенного символа и получаешь его координаты

........0123......
......E........4....
.....D..........5...
.....C...........6..
.......B.......7....
..........A98......
......................

редакция от Gambit_oz, 11.10.2012 04:48

Опубликовано 11.10.2012 06:05 (12 лет назад) #

ну э... брезенхем вроде для каждой 1/8 (или 1/4, смотря что за реализация) части окружности генерит точки подряд по обходу.
только обычно полученную точку сразу зеркалят в 8 (или 4), поэтому порядок получается хер знает какой.
если же эти 1/8-окружностей генерить последовательно (а не параллельно), то получим что надо.
только тут может чуток медленнее получиться (в константу раз).
еще можно оставить и параллельную генерацию, только для каждой новой точки вычислять ее позицию в массиве
и писать именно туда.

если надо более конкретно - реализацию в студию)

Опубликовано 11.10.2012 06:44 (12 лет назад) #

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

https://dl.dropbox.com/u/44239143/ellipsesteps.png

редакция от 0nni, 11.10.2012 06:45

Опубликовано 11.10.2012 08:17 (12 лет назад) #

Брезенхем генерит 4 или 8 упорядоченных последовательностей. Достаточно их разместить в правильном порядке и собрать в одну цепочку. Возможно последовательности отзеркалить надо будет (4 из для 8-кратного Брезенхема).

Опубликовано 11.10.2012 08:43 (12 лет назад) #

Короче. Если надо отсортировать массив - могу подсказать. Но можешь прислушаться к людям и сразу генерить упорядоченный массив. А если отсортировать, то вот:

1) берем квиксорт
2) на вход квиксорта, как известно, передается функция сравнения (мы ее сами пишем)
3) функция сравнения должна сравнить atan2(y,x) двух точек (то есть их углы относительно оси x)
4) профит!

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

редакция от RichDad, 11.10.2012 08:45

Опубликовано 11.10.2012 09:29 (12 лет назад) #

Я так понимаю что нужно написать некий итератор (http://ru.wikipedia.org/wiki/%D0%98%D1%82%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80) который при каждом запросе выдает следующую точку.
- Запоминаешь в нем начальные условия: центр окружности, радиус, точку с которой двигаться;
- Определяешь квадрант точки, направление (по часовой или против);
- Запускаешь вхолостую брезенхемовский алготрим до тех пор пока не достигаешь нужной точки (или если хватит смекалки - выводишь параметры ошибки и всего такого для точки математически);
- При каждом вызове делаешь шаг а алгоритме Брезенхема чтоб получить следующую координату, если выходишь за границы квадранта - запускаешь его заново для следующего квадранта.

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

Опубликовано 11.10.2012 15:21 (12 лет назад) #

Gambit_oz написал:
а в массив не проще запихать сгенеренную окружность
типа Circle:array[...] of Tpoint; ?

Shirson:
Функция, которая генерит окружность, выдаёт массив (одномерный) с набором точек целевой окружности.

и потом хоть рандомом хоть чем - выбирай оттуда точку и вперед или назад двигай по индексу

Проблема в том, что точки в массиве не по порядку идут. Брезенхем генерит часть окружности и остальное зеркалит 4 раза.

RichDad написал:
Короче. Если надо отсортировать массив - могу подсказать.
...
3) функция сравнения должна сравнить atan2(y,x)

Не имеет смысла сортировать Березенхем тригонометрической функцией :) Это как в ассемблер вставлять скриптовую часть.

0nni написал:
Мне кажется что зная координаты центра и имея 8 прилегающих клеток (две из которых являются частью окружности) можно вычислить какая будет соответствовать движению по часовой, а какая против.

Дело в том, что у меня не битмап, а одномерный массив с координатами точек.

rip написал:
ну э... брезенхем вроде для каждой 1/8 (или 1/4, смотря что за реализация) части окружности генерит точки подряд по обходу.
только обычно полученную точку сразу зеркалят в 8 (или 4), поэтому порядок получается хер знает какой.
если же эти 1/8-окружностей генерить последовательно (а не параллельно), то получим что надо.
только тут может чуток медленнее получиться (в константу раз).
еще можно оставить и параллельную генерацию, только для каждой новой точки вычислять ее позицию в массиве
и писать именно туда.

bsivko написал:
Брезенхем генерит 4 или 8 упорядоченных последовательностей. Достаточно их разместить в правильном порядке и собрать в одну цепочку. Возможно последовательности отзеркалить надо будет (4 из для 8-кратного Брезенхема).

Похоже это и надо будет сделать. Спасибо.

Опубликовано 11.10.2012 15:23 (12 лет назад) #

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

Жуть какая. Но жуть правильная, как мне кажется. Это тоже попробую (это даже больше подходит к тому, что мне надо)

Опубликовано 11.10.2012 18:52 (12 лет назад) #

картинку, что предложил Onni, можно использовать как иллюстрацию того, что предложил Zer0.

Перейти на форум:

Конкурсы

Открытые конкурсы:

Активных нет

Недавние конкурсы:

№181 - Pixel Craft 128

Все конкурсы

Случайная игра

Мини-чат

Вам необходимо залогиниться.

Архив чата