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

Question

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

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

Есть идеи?

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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