Fast algorithm to find the x closest points to a given point on a plane

c# algorithm map point plane
Michael Junk picture Michael Junk · Feb 2, 2012 · Viewed 19.7k times · Source

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.

Answer

Olivier Jacot-Descombes picture Olivier Jacot-Descombes · Feb 2, 2012

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

UPDATE

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).

Related questions

Best way to reverse a string

I've just had to write a string reverse function in C# 2.0 (i.e. LINQ not available) and came up with this: public string Reverse(string text) { char[] cArray = text.ToCharArray(); string reverse = String.Empty; for (int i = cArray.Length - 1; …

Read More
How to check if a number is a power of 2

Today I needed a simple algorithm for checking if a number is a power of 2. The algorithm needs to be: Simple Correct for any ulong value. I came up with this simple algorithm: private bool IsPowerOfTwo(ulong number) { if (number == 0) …

Read More
Swap two variables without using a temporary variable

I'd like to be able to swap two variables without the use of a temporary variable in C#. Can this be done? decimal startAngle = Convert.ToDecimal(159.9); decimal stopAngle = Convert.ToDecimal(355.87); // Swap each: // startAngle becomes: 355.87 // stopAngle becomes: 159.9

Read More