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

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

Я столкнулся с методами преобразования облака точек в 3d-сетку, но большинство вещей, которые я нашел, были очень сложными, и я ищу что-то как можно более простое.

Любые идеи?

Ответ 1

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

Затем преобразуйте точку, которую вы хотите проверить, в ту же систему координат.

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

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

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

Стивен Судит также предложил полезную оптимизацию, которую я бы рекомендовал, если вы пойдет по этому пути.

Ответ 2

Я думаю, что метод Билла Кэри находится на правильном пути, но я хочу предложить возможную оптимизацию.

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

Это должно позволить вам быстро разрешить простые дела. Для более сложных методов Кэри берет верх.

Ответ 3

Используйте kd-дерево.

http://en.wikipedia.org/wiki/Kd-tree

В статье дается хорошее объяснение.

Я могу устранить любые другие недоразумения.