Изобретаю алгоритм генерации мира из многоугольников, подумалось, а может это велосипед и уже есть такие?
Задача такая. Есть плоскость, есть начало координат, всё измеряется в неких условных единицах. Для простоты плоскость можно представить экраном монитора, точка отчёта вверху слева.
Необходимо случайным образом разместить на этой плоскости заданное количество выпуклых многоугольников, соприкасающихся рёбрами друг с другом. И получить списки координат их вершин. Соприкасающиеся рёбра имеют одинаковые координаты вершин для двух (или нескольких) многоугольников.
Критерии задаваемы: размер плоскости, количество многоугольников, площадь одного многоугольника (одинаковая или диапазон [А..Б]), количество рёбер (динаковое, диапазон), количество соприкосновений с другими многоугольниками и с окружающей бесконечностью, др.
Пример.
Ещё пример можно увидеть на флешках, отображающих результаты голосований по регионам России при выборах, например, Президента. Есть на сайте избиркома.
Можно, конечно, разбить плоскость на клетки единичного размера, сгенерировать клеточные области, потом преобразовать их во многоугольники, но хотелось бы обойтись без этих промежуточных вычислений.
Также понятно, что на задачу можно посмотреть не как на сборку пятнашек, а как на разборку-разбиение. Т.е. генерируем описывающий многоугольник по внешним границам, а потом начинаем разбивать на составляющие...
Но может кто встречал в Сети подобные алгоритмы? Или подходы к решению таких задач...
... << RSDN@Home 1.1.4 beta 3 rev. 189 Тишь да гладь, да Божья благодать >>
Здравствуйте, akasoft, Вы писали:
A>Можно, конечно, разбить плоскость на клетки единичного размера, сгенерировать клеточные области, потом преобразовать их во многоугольники, но хотелось бы обойтись без этих промежуточных вычислений.
Вряд ли без промежуточных вычислений выйдет. Работать с маленькими областями гораздо проще, чем с большими прямоугольниками. Просто потому, что они описываются меньшим сильно числом параметров.
A>Также понятно, что на задачу можно посмотреть не как на сборку пятнашек, а как на разборку-разбиение. Т.е. генерируем описывающий многоугольник по внешним границам, а потом начинаем разбивать на составляющие... A>Но может кто встречал в Сети подобные алгоритмы? Или подходы к решению таких задач...
По автоматической разбивке произвольных областей на подобласти не одна диссертация защищена. Это важная составная часть в расчетах методом конечных элеметнов (finite elements method — FEM) — можешь попробовать поискать это слово, вруг кто добрый выложил свою реализацию в public domain. (всторону: эх, помню пришлось мне в свое время писать такой курсовой проект, только посложнее — для трехмерного случая ).
Но я тебе советую не тратить время на поиски, а сделать всё по-простому, как ты сам придумал — разбить сцену на мелкие "клеточки" (лучше треугольные — естественнее вглядеть будет), а потом их объединить в нужное число секторов.
Здравствуйте, akasoft, Вы писали:
Я бы строил как строители реальные ! Все "кирпичиками" ! -)
A>Изобретаю алгоритм генерации мира из многоугольников, подумалось, а может это велосипед и уже есть такие?
A>Задача такая. Есть плоскость, есть начало координат, всё измеряется в неких условных единицах. Для простоты плоскость можно представить экраном монитора, точка отчёта вверху слева.
A>Необходимо случайным образом разместить на этой плоскости заданное количество выпуклых многоугольников, соприкасающихся рёбрами друг с другом. И получить списки координат их вершин. Соприкасающиеся рёбра имеют одинаковые координаты вершин для двух (или нескольких) многоугольников.
A>Критерии задаваемы: размер плоскости, количество многоугольников, площадь одного многоугольника (одинаковая или диапазон [А..Б]), количество рёбер (динаковое, диапазон), количество соприкосновений с другими многоугольниками и с окружающей бесконечностью, др.
A>Пример. A>
A>Ещё пример можно увидеть на флешках, отображающих результаты голосований по регионам России при выборах, например, Президента. Есть на сайте избиркома.
A>Можно, конечно, разбить плоскость на клетки единичного размера, сгенерировать клеточные области, потом преобразовать их во многоугольники, но хотелось бы обойтись без этих промежуточных вычислений.
A>Также понятно, что на задачу можно посмотреть не как на сборку пятнашек, а как на разборку-разбиение. Т.е. генерируем описывающий многоугольник по внешним границам, а потом начинаем разбивать на составляющие...
A>Но может кто встречал в Сети подобные алгоритмы? Или подходы к решению таких задач...
With best regards, roma_k.
Re[2]: Алгоритм генерации миров из многоугольников
Здравствуйте, roma_k, Вы писали:
_>Я бы строил как строители реальные ! Все "кирпичиками" ! -)
Кирпичиками (т.е. по клеточкам) у меня есть, только как их не апроксимируй, всё равно угловатые многоугольники. Хотелось бы кривых конструкций и рандомных.
... << RSDN@Home 1.1.4 beta 3 rev. 189 Тишь да гладь, да Божья благодать >>
Re[2]: Алгоритм генерации миров из многоугольников
Здравствуйте, eugals, Вы писали:
E>Вряд ли без промежуточных вычислений выйдет. Работать с маленькими областями гораздо проще, чем с большими прямоугольниками. Просто потому, что они описываются меньшим сильно числом параметров.
Согласен, согласен.
E>По автоматической разбивке произвольных областей на подобласти не одна диссертация защищена.
Да уж точно, триангуляция одна чего стоит. Это я так, качнулся в другую сторону, думал, может проще посмотреть через забор. Оказалось, что нет.
E>Но я тебе советую не тратить время на поиски, а сделать всё по-простому, как ты сам придумал — разбить сцену на мелкие "клеточки" (лучше треугольные — естественнее вглядеть будет), а потом их объединить в нужное число секторов.
Да я вот тоже о треугольниках думал. Квадратики надоели бо.
Сейчас реализую алгоритм, когда на плоскость типа наложена сетка квадратная с некой стороной квадрата, и в этом квадрате помещаются треугольнички, аккурат два штуки, с делением по диагонали либо слева направо, либо справа налево. Итого 4 вида треугольников.
Ну и дальше, для заданного количества областей ставятся по по одному треугольнику, а затем в цикле достраиваются прилегающие к ребрам получившейся фигуры. До заполнения.
Хотел было разнообразить треугольники по размерам, но больно сложная мозаика получается...
... << RSDN@Home 1.1.4 beta 3 rev. 189 Тишь да гладь, да Божья благодать >>
Здравствуйте, akasoft, Вы писали:
A>Кирпичиками (т.е. по клеточкам) у меня есть, только как их не апроксимируй, всё равно угловатые многоугольники.
Конечно угловатые, но их ведь можно выровнять
После формирования фигур, пройтись по вершинам границы и посчитать углы. Для острых углов можно:
разбить помельче
передвинуть точку
"подарить" этот треугольник соседней фигуре...
Здравствуйте, akasoft, Вы писали:
A>Изобретаю алгоритм генерации мира из многоугольников, подумалось, а может это велосипед и уже есть такие?
Я бы разбивал исходную область квадратами некоторого размера. Причем следующим образом:
1. Сгенерировал координаты искходных точек(точка — квадратный полигон некоего минимального размера) на области — к примеру исходные центры 10 областей
2. Генерировал бы постепенный рост каждой области по всем направлениям.
3. Повторял бы п.2 до полного заполнения области
4. Проходя по границам всех получившихся областей сгладил бы квадратные границы
Балуясь настройками п.2 можно получать довольно случайные области — генерируя, например, для каждой области приоритеты направления роста, величину прироста и пр.
Можно несколько изменить генерацию. К примеру, на подобной основе сгенерировать сначала одну произвольную область пунктами 1-3.
Затем на границе этой области начать рост новой.
По истечении генерации заданных областей (те же 10 шт) достроить пустые места на заданном пространстве
Сгладить границы пунктом 4.
Re[2]: Алгоритм генерации миров из многоугольников
Здравствуйте, _Dreamer, Вы писали:
_D>А если некий исходный многоугольник разбить на несколько областей отрезками
Дело в том, что исходного многоугольника нет. Его ещё надо нарисовать. Т.е. сгенерировать. Конечно, можно забить некий массив координат, и потом его слегка крючить с рандомом, чтобы получилось что-то разнообразное. Конечно, можно забить несколько массивов, выбирать их в цикле с тем же рандомом. Да и просто стартовать с неких начальных условий не у единичный многоугольник, а уже в какую-то фигуру, и потом доращивать их до соприкосновения.
Что я хочу сказать — начальные условия могут быть разными, и могут определять вид многоугольников и быстроту их генерации.
Сейчас я просто беру некий квадрат, накладываю сеточку и заполняю полностью. Хочется же некоего неквадратного по внешней форме мира, окантованного ломаной окружающей средой. Что-то напоминающее политическую карту, что ли.
_D> а затем с помощью фрактализации "изломать" границы ?
А это как? До сих пор считал, что фракталы — это из области туманной для меня графики и рисования.
... << RSDN@Home 1.1.4 beta 3 rev. 189 Тишь да гладь, да Божья благодать >>
Re[3]: Алгоритм генерации миров из многоугольников
Здравствуйте, akasoft, Вы писали:
A>До сих пор считал, что фракталы — это из области туманной для меня графики и рисования.
Я не думаю, что генерация исходного многоугольника представляет особую сложность.
Например, можно просто сгенерить набор случайных координат, построить по этим точкам триангуляцию, а затем сгруппировать треугольники в несколько областей. А затем уже фракталы сделают контуры достаточно изломанными.
Мандельброт называл фракталами различные формы самоподобных кривых — то есть при приближенном рассмотрении часть кривой напоминала саму кривую, и так до бесконечности. Береговая линия как раз такая — при увеличении масштаба карты
контуры не вырождаются в прямые отрезки. Поэтому независимо от того как будет строиться твой мир, я бы посоветовал
применить фрактализацию. Просто для более реальной картины.
С триангуляцией могу помочь — есть рабочий алгоритм. Если заинтересовался — пиши на мыло, указано в инфе. Или в аську — 240830896.
Re[4]: Алгоритм генерации миров из многоугольников
Здравствуйте, _Dreamer, Вы писали:
_D>Я не думаю, что генерация исходного многоугольника представляет особую сложность.
Да не очень представляет, куда сложнее найти на это толику времени.
_D>Например, можно просто сгенерить набор случайных координат, построить по этим точкам триангуляцию, а затем сгруппировать треугольники в несколько областей.
Очень интересно. Координаты действительно могут быть самыми случаными? Или всё-таки д.б. правила парности координат, чтобы можно было построить триангуляцию? Сразу скажу, триангулирующих алгоритмов ещё не делал, только читал смотрел картинки. Но если можно затриангулировать набор случайных координат за небольшое (пусть 10-30 сек.) время, то это уже альтернатива. Понятно, что время зависит от количества координат.
_D> А затем уже фракталы сделают контуры достаточно изломанными.
Интересно, как это делается... Я вот пока дошёл до того, что есть координаты игрового мира, и они абсолютные, на них происходит расчёт игровых событий. А для отображения на экране в пикселях используется преобразование, зависящее от масштаба. В этом случае выше определённо детализации не прыгнешь, да и нужно ли оно.
_D>Береговая линия как раз такая — при увеличении масштаба карты контуры не вырождаются в прямые отрезки.
Тем не менее, по моему, это зависит от точки зрения, т.е. от масштаба. Если он будет уменьшающим (1 : N), то получаем сглаживание, если увеличивающим (N : 1), то получим угловатость. Тут достаточно по моему просто не делать увеличений больше, чем нужно.
_D>С триангуляцией могу помочь — есть рабочий алгоритм.
Инетересуюсь... Реализация на C++?
... << RSDN@Home 1.1.4 beta 3 rev. 189 Тишь да гладь, да Божья благодать >>
Можно попробовать поэкспериментировать с нормалями
(я сталкивался с этим только в теории)
Алгоритм посроения поверхности
(Нормаль — перпендикуляр к плоскости треугольника. что то вроде этого то есть если изменить координаты нормали, то изменится и ориентациия треугольника в пространстве)
Для каждого треугольник определяете к нему нормаль в трехмерном пространстве,
генерим случайно нормали (можно с примерно заданным углом) в опорных точках,
а потом опять-таки интерполируем их значения для промежуточных нормалей (для
обеспечения плавности поверхности) результат — двухмерный массив нормалей,
значения которых плавно перетекают друг в друга.
После цикла генерации нормалей остается только связать треугольники:
первый способ:
вершины треугольника находятся в "сетке", то есть каждая вершина привязана к
конкретной координате (типа клетки тетради, но разбитая на два треугольника)
в этом случае используются прямоугольные треугольники.
второй способ:
связывать их по сторонам, алгоритм не простой, но более корректный.
к примеру можно к 1-ой нормали привязывать 3 вершины, расчитанные случайно или св язанные с заданным размером, а остальные треугольники создавать добавлением к пре дыдущему треугольнику одной вершины и связывания этой вершины с ребрами нового
треугольника. (если хотите, то могу и поподробнее)
Re[5]: Алгоритм генерации миров из многоугольников
Здравствуйте, akasoft, Вы писали:
A>Но если можно затриангулировать набор случайных координат за небольшое (пусть 10-30 сек.) время, то это уже A>альтернатива. Понятно, что время зависит от количества координат.
А сколько точек предполагается генерировать ? На каких мощностях это все должно работать ? 10 сек — это очень много, меньше 0.5 секунды — наверняка (конечно, зависит от кол- ва точек и машины, но не 386 же это будет).
На точки ограничений не накладывается. (Хотя если они все на одной прямой лежать будут, то ничего хорошнго не получится )
A>Инетересуюсь... Реализация на C++?
Да. Там правда выкинуть надо будет много чего, да и оптимизнуть не мешало бы...
Re[2]: Алгоритм генерации миров из многоугольников
Здравствуйте, akasoft, Вы писали:
A>Здравствуйте, MadCoder_61, Вы писали:
MC_>>Можно попробовать поэкспериментировать с нормалями
A>Я так понимаю, что это в пространстве. А мне надо на плоскости, в обычном 2D...
Ну, так просто прировнять третью координату к нулю и все.
Длина нормали равна площади треугольника
).
