Как вычислить пересечение выпуклого многогранника с другим многогранником?

Question

Проблема заключается в научном моделировании, связанном с 2D-ростом в трехмерном пространстве. Двумерная форма растет, добавляя (треугольные) сегменты к ранее выращенной форме.

Обратите внимание, что фактические сегменты в 3D имеют толщину, таким образом, мой код на самом деле работает с треугольными призмами.

В какой-то момент эти 2D-формы (с любой относительной ориентацией и положением) сталкиваются.

Если одна из новых треугольных призм пересекается с ранее вставленными сегментами, я хочу только вставить «часть» сегмента, который не пересекается с ранее вставленными сегментами. Как показано ниже для сегментов, обозначенных T1 и T2.

В первом шаге, я вычислил все пересечения края для лица. Затем я использовал пакет триангуляции CGAL Delaunay в 3D для сетки результирующей точки, установленной в тетраэдрической сетке. В качестве последнего шага я выбрасываю все те тетраэдры, которые пересекаются с ранее вставленными сегментами. В большинстве случаев это прекрасно работает, но я убежден, что идея не может работать по фундаментальным причинам.

Что является более надежным способом вычислить это?

Answer 1

Итак, вы ищете, чтобы найти пересечение двух выпуклых корпусов?

Я считаю, что ваш правильный подход не будет работать во всех случаях, но только в некоторых дегенеративных случаях. Например, если одна выпуклая оболочка полностью внутри другого, то нет пересечений между гранями/ребрами.

Более очевидный надежный подход заключается в том, чтобы начать с выпуклой оболочки, достаточной для того, чтобы заключить оба корпуса (так в основном представляя все пространство), а затем для каждой плоскости в обоих выпуклых оболочках эта оболочка разделяет эту плоскость, отбрасывая часть на «снаружи».

В результате будет пересечение - это может быть ничего.