Menu
What is the fastest way to find closest point to the given point in data array?
For example, suppose I have an array A of 3D points (with coordinates x, y and z, as usual) and point (x_p, y_p, z_p). How do I find the closest point in A to (x_p, y_p, z_p)?
As far as I know, slowest way to do it is to use linear search. Are there any better solutions?
Addition of any an auxiliary data structure is possible.
200
The basic algorithm is to check every segment of the polygon and find the closest point for it. This will either be the perpedicular point (if it is on the segment) or one of the endpoints. After doing this for all segments, pick the point with the smallest total difference.
Closest Pair of Points using Divide and Conquer algorithm.
You may organize your points in an Octree. Then you only need to search a small subset.
A Octree is a fairly simple data structure you can implement yourself (which would be a valuable learning experience), or you may find some helpful libraries to get you going.
78
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
