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

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

Для меня совершенно нормально использовать триангуляцию Делоне, но я не хочу создавать случайные точки внутри многоугольника. Было бы намного лучше, если бы я мог создать как можно меньше точек внутри этого многоугольника.
Я хотел бы минимизировать количество используемых треугольников.

Как я могу это установить?

Комментарий: это больше не зависит от языка, мне нравится знать, как это реализовать самостоятельно.


algorithm geometry computational-geometry language-agnostic
person guerda    schedule 18.01.2011    source источник
comment
Итак, вы хотите минимизировать количество требуемых треугольников?   -  person moinudin    schedule 18.01.2011
comment
Да, точно! Я собираюсь добавить эту информацию.   -  person guerda    schedule 18.01.2011
comment
Я полагаю, это не выпуклый, триангуляция выпуклого многоугольника звучит слишком просто.   -  person biziclop    schedule 19.01.2011
comment
Он может быть разным: многоугольник может быть вогнутым или выпуклым.   -  person guerda    schedule 19.01.2011

Ответы (3)


arrow_upward
5
arrow_downward

Вы можете использовать обрезку ушей или монотонные многоугольники. Ни один из алгоритмов не принесет дополнительных очков.

(Если вы решите формировать монотонные многоугольники, монотонные многоугольники будут выпуклыми, и их можно сразу разбить на вееры треугольников.)

person Reed Copsey    schedule 18.01.2011

arrow_upward
2
arrow_downward

Я нашел очень полезную библиотеку Poly2Tri. Ветвь Java этой библиотеки делает именно то, что мне нужно.

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

person guerda    schedule 26.01.2011

arrow_upward
0
arrow_downward

Если многоугольник выпуклый, легко использовать границу и выполнять триангуляцию, используя точки вдоль границы. Если он невыпуклый, я бы сделал выпуклую границу и пометил бы вставленные точки как вставленные. Затем, когда закончите со всем остальным, удалите вставленные точки.

Вы также можете использовать алгоритм уточнения сетки, чтобы улучшить сетку, если вы получаете длинные и тонкие треугольники. Используя Делоне, вы можете просто проверить, является ли треугольник «тонким» по определению, и если он «тонкий», вставьте точку в центре описанной окружности этого треугольника. Таким образом, все, что вам нужно сделать, это использовать теорию Делоне.

person martiert    schedule 18.01.2011
comment
Я думаю, что для вогнутых многоугольников это изменит внешнюю форму, не так ли? - person guerda; 19.01.2011
comment
Я так не думаю, поскольку вы триангулируете его как выпуклость, а затем удаляете точки за пределами исходной границы. Конечно, вам также придется использовать все точки на исходной границе, и когда вы затем удалите точки за пределами границы, исходная граница будет новой границей, имеющей такую ​​же внешнюю форму. По крайней мере, я не думаю, что это изменит внешнюю форму. - person martiert; 19.01.2011