Menu
I would like to find a fast algorithm in order to find the x closest points to a given point on a plane.
We are actually dealing with not too many points (between 1,000 and 100,000), but I need the x closest points for every of these points. (where x usually will be between 5 and 20.)
I need to write it in C#.
A bit more context about the use case: These points are coordinates on a map. (I know, this means we are not exactly talking about a plane, but I hope to avoid dealing with projection issues.) In the end points that have many other points close to them should be displayed in red, points that have not too many points close to them should be displayed green. Between these two extremees the points are on a color gradient.
969
The closest point on a plane to a point away from the plane is always when the point is perpendicular to the plane. So if we work out the equation of the line that goes through the point (1, 3, 6) which is perpendicular to the plane, then we can use it to find where it intersects the plane.
In this problem, a set of n points are given on the 2D plane. In this problem, we have to find the pair of points, whose distance is minimum. To solve this problem, we have to divide points into two halves, after that smallest distance between two points is calculated in a recursive way.
Approach: The idea is to calculate the Euclidean distance from the origin for every given point and sort the array according to the Euclidean distance found. Print the first k closest points from the list. Sort the points by distance using the Euclidean distance formula. Print the points obtained in any order.
What you need is a data structure appropriate for organizing points in a plane. The K-D-Tree is often used in such situations. See k-d tree on Wikipedia.
Here, I found a general description of Geometric Algorithms
I ported a Java implementation of a KD-tree to C#. Please see User:Ojd/KD-Tree on RoboWiki. You can download the code there or you can download CySoft.Collections.zip directly from my homepage (only download, no docu).
109
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
