@Toshegg

Как разбить произвольную форму на выпуклые многоугольники?

Всем здравствуйте!
На вход подается множество координат (x,y), каждая из которых обозначает точку на плоскости. На выходе нужно получить массив разбиения данной формы на примитивы.
Вообще, может, есть более простой алгоритм для моей задачи. Моя задача состоит в следующем:
есть картинка с контуром, например:
77bf0069d5.jpg
В контуре есть дырки.
Цель: получить на выходе расстановку цифер в контуре таким образом, чтобы в достаточно большом контуре было 2-3 цифры, а в маленьком только одна (если поместится). То есть:
e41bad6369.jpg
"Достаточно большой" и "маленький" - понятия относительные, по этому достаточно большой - это количество пикселей в контуре >N, а маленький - < M.
Надо сказать, что координаты контура я нахожу алгоритмом поиска в ширину и записываю их в массив, так что можно получить доступ ко всем координатам контура.
Было несколько идей, в числе которых вписание контура в прямоугольник и постановка цифры в центр, но :
1) Цифра может находиться в дырке
2) Цифра может находиться вообще вне контура
Далее, можно сделать триангуляцию и поставить в центр каждого треугольника цифру, но проблема в том, что судя по тем алгоритмам, которые я гуглил, триангуляция работает в основном для выпуклых полигонов, да и треугольников может получиться очень много, а соответственно и цифр.
Так что, последняя идея, на которой я остановился - разбиение данной формы на выпуклые многоугольники и постановка числа в их центры.
Собственно, вопрос: мне нужна либо идея, как это можно сделать проще, либо код на Java, который делает данное разбиение, либо наиболее полное описание алгоритма разбиения.
Заранее большое спасибо за ответ!
  • Вопрос задан
  • 2750 просмотров
Пригласить эксперта
Ответы на вопрос 1
Lerg
@Lerg
Defold, Corona, Lua, GameDev
1. Написать функцию, которая бы определяла находится ли произвольная точка в контуре. Можно встать в левый верхний угол, пойти по-пиксельно последовательно и записывать значения true/false в карту "входимости" оперируя границами контура - как только перешли через контур, сменить записываемое значение на противоположное (false -> true). Floodfil тоже может пригодиться.
2. Построить карту удалённости до границ. Для каждого пикселя вывести значение минимального расстояния до какой-либо границы, если точка находится внутри контура.
3. Найти локальные максимумы.
4. Расставить числа в локальные максимумы, можно автоматически подстраивать размер шрифта, оперируя полученным расстоянием до границы.

Карта удалённости будет напоминать следующую картину (приближённо, сделал в фотошопе)
5d2c8cfc9c3545029f3472be245a891f.png

Звучит сложно, но должно сработать.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bell Integrator Ульяновск
До 400 000 ₽
Bell Integrator Ижевск
До 400 000 ₽
Bell Integrator Хабаровск
До 400 000 ₽
28 мар. 2024, в 12:05
2000 руб./за проект
28 мар. 2024, в 11:24
5000 руб./за проект