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

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

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

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


person David    schedule 05.03.2012    source источник


Ответы (3)


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

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

person templatetypedef    schedule 05.03.2012
comment
Выпуклый корпус ... это действительно похоже на то, что мне нужно. Спасибо тоже за ссылку. Есть опыт работы с конкретными алгоритмами? - person David; 06.03.2012

Я думаю, что вы ищете выпуклую оболочку.

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

person Sirko    schedule 05.03.2012
comment
Спасибо за ссылку! Легко ли эти два алгоритма расширять до трехмерных точек? - person David; 06.03.2012

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

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

person Community    schedule 06.03.2012