¿Cómo puedo probar si un punto se encuentra dentro de una forma 3D con su superficie definida por una nube de puntos?

Question

Tengo una colección de puntos que describen la superficie de una forma que debería ser aproximadamente esférica, y necesito un método para determinar si cualquier otro punto dado se encuentra dentro de esta forma. Anteriormente he estado aproximando la forma como una esfera exacta, pero esto ha demostrado ser demasiado inexacto y necesito un método más preciso. La simplicidad y la velocidad son favorables sobre la precisión completa, una buena aproximación será suficiente.

He encontrado técnicas para convertir una nube de puntos en una malla 3D, pero la mayoría de las cosas que he encontrado han sido muy complicadas, y estoy buscando algo tan simple como sea posible.

¿Alguna idea?

Answer 1

¿Qué sucede si se calcula el centroide de la nube y se convierten sus coordenadas a un sistema polar cuyo origen es ese centroide?

A continuación, convierta el punto que desea examinar al mismo sistema de coordenadas.

Suponiendo que la superficie es representable mediante una triangulación Delaunay, determine los tres puntos con la menor diferencia de ángulo desde el punto que está examinando.

Proyecte el punto que está examinando en el triángulo determinado por esos tres puntos, y vea si la distancia del punto proyectado desde el centroide es mayor que la distancia del punto real.

Básicamente, estás construyendo una malla triangular del casco convexo, pero si es necesario un triángulo a la vez. Si la velocidad de ejecución realmente importa, puede almacenar en caché los triángulos resultantes sobre la marcha.

Steven Sudit también ha sugerido a useful optimization que recomiendo si sigues este camino.

Answer 2

Creo que el método de Bill Carey está en el camino correcto, pero quiero sugerir una posible optimización.

Dado que la forma es más o menos esférica, puede precalcular el radio de la esfera que lo une y de la esfera que lo delimita. De esta manera, si la distancia del punto está dentro de la esfera más pequeña, es un golpe definitivo y si está fuera de la esfera externa, es una falla definitiva.

Esto debería permitirle resolver los casos fáciles muy rápidamente. Para los más duros, el método de Carey se hace cargo.

Answer 3

Usa un árbol kd.

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

El artículo proporciona una buena explicación.

Puedo aclarar cualquier otro malentendido.