Find nearest point


I’ve got a list with thousands of points. I want to add functionality when the user click meshes on scene and gets the position of the clicked point I need to find the nearest point from my list of points. The list of points is really large so iterating the overall list and calling static function Vector3.Distance() would be not efficient. Is there any efficient and fast method build-in Babylon to achieve my goal?

Not sure about Babylon, but in general you’d solve that by having some pre-processing to partition your points so when you need to search, it executes in a much smaller space

Depending how well you do partitioning, execution should be close to O(log(n))

Check out k-d tree and ANN library

1 Like

In Babylon we use octree internally for partitioning Optimizing With Octrees | Babylon.js Documentation but I am not sure you can use it for this.

In your case building a partitioned space would be the way to go.

Yes. I thought about k-dimensional tree before but i hope that there is some build in method in Babylon. Anyway i found npm library to solve my problem. Thanks for answer.

1 Like