Как лучше всего провести триангуляцию 5-точечного звездного многоугольника?

Question

Я реализовал метод триангуляции "расщепления ушей" для простых полигонов.При тестировании я вижу, что он падает на тестовом примере симметричной 5-точечной звезды.Я думаю, я понимаю, почему этот многоугольник "хитрый" - потому что он содержит ребра, которые являются коллинеарными .... диагональю для бритья ушей, которую алгоритм выбирает, основываясь на начале с выпуклой вершиной (одной из 5 точек), затем проверяядиагональ для пересечения ребер без «X» и для вершин, не входящих в треугольник уха) будет слепо назначать диагональ, коллинеарную с двумя существующими ребрами.После удаления внешней вершины уха оставшийся многоугольник больше не будет «простым» - у него будут вершины, имеющие прямой угол (180 градусов), что является нарушением контракта простого многоугольника.

I'mогорчен тем, что я доказал, что колющее ухо сталкивается с этим случаем неудачи.Из литературы я подумал, что это был метод общего назначения (применимый ко всем простым полигонам).Эти "индуктивные доказательства", которые вы находите, повторяются повсюду, завышены?

Кто-нибудь успешно модифицировал метод триангуляции с расщеплением ушей для обработки 5-балльной звезды?

Answer 1

Случайное возмущение конечных точек коллинеарного ребра

Алгоритм "расщепления ушей" страдает от поломки в случае многоугольников, у которых ребра коллинеарны.Как вы можете видеть в 5-точечной звезде, все ребра имеют эту проблему.

Простой «патч» может спасти алгоритм триангуляции «расщепления ушей»:

1) Перед началом триангуляции проверьте список ребер полигона (в виде LineSegs) на наличие любой пары ребер, которыеиспользовать одну и ту же 2D расширенную линию.Примените небольшое случайное возмущение к обоим конечным точкам любого такого ребра (например, в диапазоне -0,001 .. + 0,001.) Сохраните исходные местоположения этих вершин, чтобы они могли быть восстановлены после триангуляции.

2) Теперь вы можете запустить триангуляцию с разделением ушей, удалив плохо обусловленную ситуацию коллинеарных ребер.

3) Отменить возмущения, которые вы применили к вершинам.

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