Какие существуют алгоритмы для нахождения ограничивающей поверхности для множества точек?

Question

Предположим, у вас есть облако точек, и вы хотите, чтобы поверхность, которая обвивает эти точки, охватывала их все, и плотно обертывала их, чтобы они пересекались с внешними точками в облаке - как вы создаете эту обернутую поверхность?То есть, когда некоторые или несколько точек могут находиться внутри объема, и поэтому поверхность не должна пересекать их, только заключите их в оболочку, но поверхность должна хорошо подходить для «внешнего» слоя точек.

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

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

Answer 1

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

Надеюсь, это поможет!

Answer 2

Я думаю, вы ищете выпуклый корпус .

Алгоритмы для его вычисления, посмотрите здесь .

Answer 3

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

Я не уверен, что это полезно для вас, Mathematica имеет интерфейс TetGenLink для TetGen.