Как я могу протестировать, если точка находится в 3-й форме с ее поверхностью, определенной облаком точек?
У меня есть набор точек, которые описывают поверхность формы, которая должна быть примерно сферической, и мне нужен метод, с которым можно определить, находится ли какая-либо другая данная точка в этой форме. Я ранее приближал форму как точную сферу, но это оказалось слишком неточным, и мне нужен более точный метод. Простота и скорость благоприятны по полной точности, хорошее приближение будет достаточно.
Я столкнулся с методами для преобразования облака точек к 3-й сетке, но большинство вещей, которые я нашел, было очень сложно, и я ищу что-то максимально простое.
Какие-либо идеи?
3 ответа
Что, если бы вы вычислили центроид облака и преобразовали его координаты в полярную систему, источником которой является этот центроид.
Затем преобразуйте точку, которую вы хотите исследовать, в ту же систему координат.
Предполагая, что поверхность может быть представлена триангуляцией Делоне, определите три точки с наименьшей разницей в углах от исследуемой точки.
Спроецируйте исследуемую точку на треугольник, определяемый этими тремя точками, и посмотрите, не превышает ли расстояние проецируемой точки от центроида расстояние до фактической точки.
По сути, вы строите треугольную сетку выпуклой оболочки, но при необходимости по одному треугольнику за раз. Если скорость выполнения действительно имеет значение, вы можете кэшировать полученные треугольники по ходу.
Стивен Судит также предложил полезную оптимизацию , которую я бы порекомендовал, если вы пойдете по этому пути.
Я думаю, что метод Билла Кэри находится на правильном пути, но я знаю хочу предложить возможную оптимизацию.
Поскольку форма имеет примерно сферическую форму, вы можете предварительно рассчитать радиус сферы, связанной с ней, и сферы, которая ее ограничивает. Таким образом, если расстояние до точки находится в пределах меньшей сферы, это определенное попадание, а если она находится за пределами внешней сферы, это определенный промах.
Это должно позволить вам очень быстро решать простые дела. В более сложных случаях берет верх метод Кэри.
Используйте kd-tree.
http://en.wikipedia.org/wiki/Kd-tree
Статья дает хорошее объяснение.
Я могу прояснить дальнейшие недоразумения.