Topic: How to find out the nearest point in a List<Point3d>?

[TheMaster]

Sorting on dX^2+dY^2+dZ^2 will result in exactly the same ordering as sorting on distance, and it avoids taking the square root -- presumably the slowest part of the distance calculation. I don't know how to express that using LINQ, but I suspect it would be a significant optimization.

LINQ is certainly not the fastest way to solve problems of this type (although PLINQ or 'Parallel Linq' would certainly simplify the job of exploiting multiple CPU cores).

The thing is that the OP's code us unclear, as he's using the result in the operation that produces it.

Code - C#: [Select]

1. Point3d nearestPoint = myList.OrderBy( pt =>
2. Math.Abs(pt.X-nearestPoint.X) +Math.Abs(pt.Y-nearestPoint.Y) + Math.Abs(pt.Z-nearest.Z)).First();
3.  

He's using 'nearestPoint before having been initialized (e.g., Point3d.Origin).

So, I think we're left with guessing what the actual problem he's trying to solve is.

[Delegate]

I find this while googling KD tree - (prob been posted before):

An open source maths libary for .NET 

http://numerics.mathdotnet.com/

and a KD tree source file

http://blog.noldorin.com/2011/03/kd-trees-for-dotnet/

[waterharbin]

Hi.
Thanks for helping. And I apologize if someone gets confused. As you guys can guss, I am not a English native speaker. But I still think that the nearest point is straightforward enough.
The points in my List are sorted by two criterions: first by Y in decending;when Ys are the same, by X in decinding. No repeated points in my List. dgorsman's idea is not good here.
Why I sort the points? For some other purposes, not for finding out the nearest one!
The mathmatic definition of the distance between two points are :Sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2) + (Z1-Z2)*(Z1-Z2)). And since I care little about the exact value of the distance, I use |X1-X2| + |Y1-Y2| + |Z1-Z2| instead. But I will get the same effect. It's simple and fast.
I guss not all of us can master LINQ, a lots of people are just like me: can barely use it. But master it? negative! So that's why I ask for help here.

[owenwengerd]

And since I care little about the exact value of the distance, I use |X1-X2| + |Y1-Y2| + |Z1-Z2| instead. But I will get the same effect.

That is not the same ordering as distance. As I mentioned earlier, you must square the terms to get ordering that is identical to distance. Consider these two points:

(100,2,0)
(101,0,0)

They are listed in order of increasing distance from (0,0,0), but using your calculation of dX+dY+dZ they will be ordered incorrectly. Use dX^2+dY^2+dZ^2 instead.

[TheMaster]

Hi.
Thanks for helping. And I apologize if someone gets confused. As you guys can guss, I am not a English native speaker. But I still think that the nearest point is straightforward enough.
The points in my List are sorted by two criterions: first by Y in decending;when Ys are the same, by X in decinding. No repeated points in my List. dgorsman's idea is not good here.
Why I sort the points? For some other purposes, not for finding out the nearest one!
The mathmatic definition of the distance between two points are :Sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2) + (Z1-Z2)*(Z1-Z2)). And since I care little about the exact value of the distance, I use |X1-X2| + |Y1-Y2| + |Z1-Z2| instead. But I will get the same effect. It's simple and fast.
I guss not all of us can master LINQ, a lots of people are just like me: can barely use it. But master it? negative! So that's why I ask for help here.

Ordering your points by the sum of the delta X,Y,Z to the given point does not put them in the order of closest-to-furthest, if that's what you're doing.  As Owen mentions, you could use the sum of the squares of the delta X, Y, and Z, but if you only need to do this for a single point (as your sorting of the list implies), then there is little point to doing that since the sorting process itself will take longer than a simple linear search. 

If you need to find the point nearest to many given points, rather than just one, then spatial indexing (e.g., KDTrees, etc). would be the best way to do it.

So, while I'm not sure if it is more efficient than using DistanceTo() (which is native code), this is the previous LINQ code with the optimization that Owen suggests:

Code - C#: [Select]

1.    List<Point3d> pointList = ....
2.    
3.    Point3d basePt = // point in pointList that is nearest to
4.    
5.    // Cache each point along with the the sum of the squares
6.    // of the vector to the given point:
7.    
8.    var items = pointList.Select( p => new{ point = p, dist = basePt.GetVectorTo( p ).LengthSqrd } );
9.    
10.    // Find the nearest point:
11.    
12.    Point3d nearest = items.Aggregate( ( a, b ) => a.dist < b.dist ? a : b ).point;
13.  

[Gasty]

Hi,

It depends on the definition of distance, to sort point based in "distance" you can use any function that define a metric which have the following conditions:

d(p1,p2)>=0
d(p1,p2)=0 <=>p1=p2
d(p1,p2)=d(p2,p1)
d((p1,p3)>=d(p1,p2)+d(p2,p3)

But you have to take in count that not all the metric are equal or induce the same ordering over the point set, the metric you are using DOES NOT set the same order that the Euclidean distance (the length of the vector between p1,p2). By the way the distance you are using is called Taxicab metric or Manhatan distance and it's useful in some situation, by example to calculate the "distance" in a grid when you can't take diagonals.
Saying that, Owen it's correct in that you don't need to use square root as squaring (the inner part of the euclidean function) is monotonic (in rigor monotonic increasing), and square root is also monotonic (i.e they preserve order under Euclidean metric. distance).

Gaston Nunez

[TheMaster]

I mentioned that PLINQ makes it easy to execute operations in parallel
across multiple CPU cores, but didn't elaborate on that, so....

To run the previously posted code in parallel on multiple CPU cores, you
only need to call AsParallel() on the List<Point3d> and everything else
stays the same:

Code - C#: [Select]

1.  
2.    List<Point3d> pointList = ....
3.  
4.    Point3d basePt = // point in pointList that is nearest to
5.  
6.    // Cache each point along with the the sum of the squares
7.    // of the vector to the given point:
8.  
9.    var items = pointList.AsParallel().Select(
10.          p => new{ point = p, dist = basePt.GetVectorTo( p ).LengthSqrd }
11.    );
12.  
13.    // Find the nearest point:
14.  
15.    Point3d nearest = items.Aggregate( ( a, b ) => a.dist < b.dist ? a : b ).point;
16.  
17.  

[waterharbin]

Hi.
Owen is right, I should use dX^2+dY^2+dZ^2. He is a very cautous man,haha. And Thanks theMaste for giving great codes. Thanks all people for caring here.
But I still have to clarify something here.
First: my List<Point3d> has already be sorted before I want to pick up the nearest point in it. The points are sorted for some other purposes, not for finding the nearest one. I do not want to sort them again. I just want to pick out the one I want.
Second: how to define a distance? I think we should follow the mathmatic one, which we are taught in math class.