Выбраковка внутренних треугольников

Question

У меня есть массив из тысяч четырехугольников;4-х сторонние 3D полигоны.Все, что я знаю, это координаты четырехугольных углов.

Подмножество этих четырехугольников определяет закрытую внешнюю оболочку трехмерной формы.Остальные квады находятся внутри этого замкнутого твердого тела.

Как определить, какие квады являются частью оболочки, а какие - частью внутреннего пространства?Это не критичный для производительности код.

---

Редактировать: Дополнительные ограничения формы оболочки

• Внутри фигуры нет отверстий, это отдельная поверхность.
• Содержит как выпуклые, так и вогнутые части.
• У меня есть несколько точек, которые, как известно, находятся внутри оболочки.

Answer 1

Это может быть трудно реализовать, если ваша фигура самостоятельно пересекается, но если вы можете найти один квад, который, как вы знаете, находится на поверхности (возможно, один самый дальний от центроида), тогда наметьте концентрические круги квадов вокруг него. Затем найдите непрерывное кольцо четырехугольников снаружи и так далее, пока не окажетесь на «противоположной» стороне. Если ваши четырехугольники пересекаются или внутренне связаны, то это сложнее. Я попытался бы разбить те, которые пересекаются, затем найти все возможные гладкие поверхности и выбрать ту, которая имеет наибольший внутренний объем.

Answer 2

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

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

Если он выпуклый или внутренние четырехугольники не имеют общих ребер свнешние квады, есть более простые способы.

Answer 3

Это можно сделать довольно легко, если форма выпуклая. Когда форма вогнута, это намного сложнее.

В выпуклом случае найдите центроид, вычислив среднее значение всех точек. Это дает точку, которая находится внутри, для которой выполняется следующее свойство:

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

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

Редактировать: Только что видел ваше разъяснение выше. В более сложном случае, когда форма вогнута, вам понадобится одна из двух вещей:

1. Описание (параметризация) фигуры, которую можно использовать для выбора четырехугольников, или
2. Некоторое другое свойство, такое как смежные граничные квады

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

Answer 4

Как насчет этого?

Рассчитать вектор нормали квадратора (назовите его "текущим" квадом).Сделайте тест пересечения с этим вектором и всеми остальными квадратами.Если он пересекает другой квад в положительной части вектора, вы знаете, что текущий квад является внутренним квадом.Повторите эти действия для всех оставшихся четырехугольников.

Это предполагает, что квадраты обращены наружу.

Answer 5

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

Вы знаете, что некоторые из четырехугольников образуют замкнутую оболочку. Следовательно, эти квадраты соединены по краям. Если три взаимно смежных ребра четырехугольника (то есть ребра образуют замкнутый контур) перекрывают ребро другого квада, то эти квады могут быть частью оболочки (эти взаимно смежные ребра служат границей 2D-области; Назовите этот регион "связным лицом" четырехугольника). Составьте список этих «кандидатов в оболочку». Теперь просмотрите этот список и отбросьте любого кандидата, у которого есть ребро, которое не перекрывается с другим кандидатом (то есть ребро перекрывает ребро четырехугольника, которого нет в списке). Повторяйте этот процесс отбраковки, пока вы больше не сможете удалить любые квады. То, что вы оставили, должно быть вашей оболочкой. Создайте список «без оболочки», содержащий все квады, которых нет в списке «оболочки».

Нарисуйте ограничивающую рамку (или сферу, эллипс и т. Д.) Вокруг этой оболочки. Теперь просмотрите список квадроциклов, не относящихся к оболочке, и выкиньте все квады, которые лежат за пределами ограничивающей области. Их точно нет в интерьере.

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