Определение вогнутостей невыпуклого многогранника

Question

Предположим, у вас есть невыпуклый трехмерный многогранник P , выраженный в виде сетки.Каков наилучший алгоритм для определения множества всех его вогнутостей?

Первый, возможно, тривиальный ответ, который я думал, мог бы состоять в том, чтобы вычислить выпуклую оболочку C измногогранник P , а затем разделить симистическую разницу C - P на подключенные компоненты.Могу ли я быть в правильном направлении?Если да, как вы вычисляете «разницу» между сетками?Существуют ли некоторые функции CGAL, которые я могу использовать для «вычитания» мешей и получения подключенных компонентов.

Answer 1

Да, вы можете, вам следует заглянуть в Nef_polyhedron_3: https://doc.cgal.org/latest/Nef_3/classCGAL_1_1Nef__polyhedron__3.html

По сути, вы конвертируете свою сетку и ее выпуклую сетку в nef.Оттуда вы получаете доступ к логическим операциям, включая разницу.Таким образом, вы можете получить то, что вы хотите, а затем преобразовать его обратно в многогранник.input non convex mesh"> input mesh and its convex hull"> result of the difference">