Как проверить, создают ли набор плоских многоугольников водонепроницаемые многогранники?
В настоящее время я задаюсь вопросом, существует ли общий алгоритм проверки того, образуют ли плоские многоугольники, а не обязательно треугольники, водонепроницаемые многогранники. Каждый многоугольник имеет ориентацию (нормальный вектор). Простым решением было бы просто сказать да или нет. Более продвинутой версией будет указание на ребра, где многогранник "открыт". Меня не очень интересует, как закрыть многогранник.
Я хотел бы отметить, что мои "дыры" не обязательно маленькие, например, одна грань куба может отсутствовать. Таким образом, алгоритмы "коррекции недостаточной выборки" не кажутся правильным подходом. Кроме того, я говорю о 100 - 1000, а не 1000000 полигонах, поэтому время вычислений не должно быть проблемой.
Любые советы или подсказки?
С уважением, куратор
2 ответа
Я полагаю, что вы можете использовать простой топологический тест - подсчитайте, сколько раз каждое ребро появляется в полном списке полигонов.
Если набор полигонов определяет поверхность замкнутого объема, каждое ребро должно иметь count>=2, указывая, что каждое ребро совместно используется (по крайней мере) двумя соседними полигонами. Если поверхность многообразна count==2 именно так.
Края с count==1 указать открытые области поверхности.
Приведенный выше ответ не распространяется на многие случаи. Более правильный (но не обязательно завершенный: я бы не знал) алгоритм должен гарантировать, что каждое ребро каждого многоугольника (или сетки / многогранника) имеет четное число граней, связанных с ним. Рассмотрим следующую сетку:
Отрезок (линия) между ближайшей вершиной и той, что ниже, прикреплен к 3 граням (одна из внешнего треугольника и две из внутреннего треугольника), которая больше двух граней. Однако это явно не закрыто.