Group list of points

Question

I have a list of points which I need to group by closer points.

The points are the white spots which I circled in red here:

Points are X and Y coordinates, here's a sample ordered by X.

+        [0]    {X = 435 Y = 347}    System.Drawing.Point
+        [1]    {X = 435 Y = 348}    System.Drawing.Point
+        [2]    {X = 434 Y = 347}    System.Drawing.Point
+        [3]    {X = 434 Y = 348}    System.Drawing.Point
+        [4]    {X = 434 Y = 349}    System.Drawing.Point
+        [5]    {X = 433 Y = 201}    System.Drawing.Point
+        [6]    {X = 433 Y = 202}    System.Drawing.Point
+        [7]    {X = 433 Y = 348}    System.Drawing.Point
+        [8]    {X = 432 Y = 149}    System.Drawing.Point
+        [9]    {X = 432 Y = 200}    System.Drawing.Point
+        [10]    {X = 432 Y = 201}    System.Drawing.Point
+        [11]    {X = 432 Y = 202}    System.Drawing.Point
+        [12]    {X = 432 Y = 203}    System.Drawing.Point
+        [13]    {X = 431 Y = 148}    System.Drawing.Point
+        [14]    {X = 431 Y = 149}    System.Drawing.Point
+        [15]    {X = 431 Y = 200}    System.Drawing.Point
+        [16]    {X = 431 Y = 201}    System.Drawing.Point
+        [17]    {X = 431 Y = 202}    System.Drawing.Point
+        [18]    {X = 431 Y = 203}    System.Drawing.Point
+        [19]    {X = 430 Y = 148}    System.Drawing.Point
+        [20]    {X = 430 Y = 149}    System.Drawing.Point
+        [21]    {X = 349 Y = 69}    System.Drawing.Point
+        [22]    {X = 349 Y = 70}    System.Drawing.Point

I need to group all closer points to then calculate the center of mass (actually my issue is getting all closer points together).

I know there's a formula to calculate the Euclidean distance between 2 points and that way find (using a range) the closest points to a given point but not sure how would that be in C# using LINQ or other method.

Answer 1

A known solution to group points is the k-means clustering algorithm.

http://en.wikipedia.org/wiki/K-means_clustering

That will also give you the center of mass for each group.

Answer 2

If I understand correctly what you're trying to do, (a little difficult because your phrasing could be better) you want to order a List by each point's distance to some unknown location.

Your question wasn't clear, so I'm going to assume you want them grouped by distance to the origin. In that case, the LINQ would look something like this:

var output = points.OrderBy(p1 => Math.Pow(p1.X, 2) + Math.Pow(p1.Y, 2));

where points is your List<Point>.

If you're looking instead to order them by the distance to an arbitrary point, it would look instead like this:

var output = points.OrderBy(p1 => Math.Sqrt(Math.Pow(p1.X - p2.X, 2) + Math.Pow(p1.Y -p2.Y, 2)));

where p2 is the point you want to find the distance from, and where points is your List<Point>.

Sources:

http://msdn.microsoft.com/en-us/library/system.drawing.point(v=vs.110).aspx

http://msdn.microsoft.com/en-us/library/bb549422.aspx

http://en.wikipedia.org/wiki/Distance#Geometry

Answer 3

[EDIT] Regarding the closest points problem, what you could is iterate over each point and check the points that are closer to a distance R (dist(Point a, Point b) < R). That way you can define what you think is close to a given point.

Regarding your question on the Center of Mass, what you could do is, for each coordinate, sum each value and divide by the number of points. For example:

foreach (var point in Points)
{
    xCenterOfMass +=  point.X;
    yCenterOfMass +=  point.Y;
}

xCenterOfMass /= Points.Count();
yCenterOfMass /= Points.Count();