Всем здравствуйте!
На вход подается множество координат (x,y), каждая из которых обозначает точку на плоскости. На выходе нужно получить массив разбиения данной формы на примитивы.
Вообще, может, есть более простой алгоритм для моей задачи. Моя задача состоит в следующем:
есть картинка с контуром, например:
В контуре есть дырки.
Цель: получить на выходе расстановку цифер в контуре таким образом, чтобы в достаточно большом контуре было 2-3 цифры, а в маленьком только одна (если поместится). То есть:
"Достаточно большой" и "маленький" - понятия относительные, по этому достаточно большой - это количество пикселей в контуре >N, а маленький - < M.
Надо сказать, что координаты контура я нахожу алгоритмом поиска в ширину и записываю их в массив, так что можно получить доступ ко всем координатам контура.
Было несколько идей, в числе которых вписание контура в прямоугольник и постановка цифры в центр, но :
1) Цифра может находиться в дырке
2) Цифра может находиться вообще вне контура
Далее, можно сделать триангуляцию и поставить в центр каждого треугольника цифру, но проблема в том, что судя по тем алгоритмам, которые я гуглил, триангуляция работает в основном для выпуклых полигонов, да и треугольников может получиться очень много, а соответственно и цифр.
Так что, последняя идея, на которой я остановился - разбиение данной формы на выпуклые многоугольники и постановка числа в их центры.
Собственно, вопрос: мне нужна либо идея, как это можно сделать проще, либо код на Java, который делает данное разбиение, либо наиболее полное описание алгоритма разбиения.
Заранее большое спасибо за ответ!
Средний
