Я проверил несколько связанных ответов, но ни один из них не отражает проблему, с которой я сталкиваюсь.
- Мне нужно триангулировать различные многогранники.
- Каждая многогранная грань закрыта.
- Лица обычно выпуклые, но не исключительно.
- Иногда лица могут быть самопересекающимися, но в этом случае они, вероятно, имеют радиальную симметрию (например, пентаграмму)
- Каждое лицо в основном плоское (я готовперенести последствия, если не так, как это технически ошибка)
Наблюдением кажется, что добавление новой вершины в центроиде и создание новой грани путем соединения каждого ребра с этой вершиной всегда успешно триангулирует грань.Тем не менее, он имеет низкую производительность и простая триангуляция вентиляторов также успешна в 95% случаев.Однако, когда это терпит неудачу, это терпит неудачу плохо.
Есть ли эффективный способ обнаружить самопересекающиеся и / или вогнутые грани, чтобы я мог вернуться к более медленному пути?Очевидно, что алгоритм обнаружения должен быть довольно эффективным, если стоимость проверки не должна превышать стоимость простого предположения наихудшего и использования триангуляции центроида во всех случаях.
Я действительно подозреваю, что мои энергии лучше тратить на оптимизациютриангуляция центроида, а не работа по обнаружению, если это действительно необходимо, но мне было интересно, что думает сообщество переполнения стека.