Come posso verificare se un punto si trova all'interno di una forma 3d con la sua superficie definita da una nuvola di punti?

Question

Ho una raccolta di punti che descrivono la superficie di una forma che dovrebbe essere approssimativamente sferica, e ho bisogno di un metodo con cui determinare se un altro dato punto si trova all'interno di questa forma. In precedenza ho approssimato la forma come una sfera esatta, ma ciò è risultato troppo impreciso e ho bisogno di un metodo più accurato. La semplicità e la velocità sono favorevoli per una precisione completa, una buona approssimazione sarà sufficiente.

Mi sono imbattuto in tecniche per convertire una nuvola di punti in una mesh 3D, ma la maggior parte delle cose che ho trovato sono state molto complicate e sto cercando qualcosa di più semplice possibile.

Qualche idea?

Answer 1

cosa succede se si Computerizzata il baricentro della nube, e convertito le sue coordinate ad un sistema polare la cui origine è quella baricentro.

Quindi, convertire il punto che si desidera esaminare per lo stesso sistema di coordinate.

Supponendo che la superficie è rappresentabile da una triangolazione Delaunay, determinare i tre punti con la più piccola differenza di angolo dal punto si sta esaminando.

Proiettare il punto che si sta esaminando sul triangolo determinato da questi tre punti e verificare se la distanza del punto proiettato dal centroide è maggiore della distanza del punto effettivo.

sostanza, si sta costruendo una maglia triangolare convesso, ma al bisogno un triangolo alla volta. Se la velocità di esecuzione è davvero importante, è possibile memorizzare nella cache i triangoli risultanti man mano che si procede.

Steven sudit ha anche suggerito a useful optimization che vi consiglio se si va su questa strada.

Answer 2

Penso metodo di Bill Carey è sulla strada giusta, ma io voglio suggerire una possibile ottimizzazione.

Dal momento che la forma è approssimativamente sferica, è possibile pre-calcolare il raggio della sfera da essa vincolata e della sfera che delimita esso. In questo modo, se la distanza del punto è all'interno della sfera più piccola, è un colpo definito e se si trova al di fuori della sfera esterna, è un errore preciso.

Questo dovrebbe permettere di risolvere i casi facili molto rapidamente. Per i più duri, il metodo di Carey prende il sopravvento.

Answer 3

Utilizzare un kd-tree.

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

L'articolo fornisce una buona spiegazione.

posso chiarire eventuali ulteriori malintesi.