#algorithm #triangulation
#алгоритм #триангуляция
Вопрос:
Я использую poly2tri в проекте САПР для триангуляции сложных полигонов с отверстиями. В большинстве случаев это работает нормально. К сожалению, в некоторых редких случаях мои полигоны могут иметь самопересечения (обычно это пересечение контура полигона и контура отверстия из-за приближения дуги). В этом случае poly2tri либо выходит из строя, либо выдает неверный результат. Самопересечение может быть исправлено путем разделения на более мелкие части, но проверка самопересечения (алгоритм Шамоса-Хоуи или аналогичный ) имеет ту же сложность, что и сама тесселяция. Кто-нибудь пытался решить эту проблему в poly2tri (возвращаемая ошибка вместо сбоя/неправильной формы) или в другой библиотеке тесселяции?