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

[waterharbin]

Hi.
I have a List<Point3d>. This List have been sorted by Y in decending. for those points with the same Y, sort them by X in decending. Then I want to find out the nearest point to a given points. My codes are below:

Code: [Select]

List<Point3d> myList = new List<Point3d>(){pt1,pt2, ..., ptn};
Point3d givenPoint = new Point3d(X1, Y1, Z1);
Point3d nearestPoint = myList.OrderBy( pt =>
Math.Abs(pt.X-nearestPoint.X) +Math.Abs(pt.Y-nearestPoint.Y) + Math.Abs(pt.Z-nearest.Z)).First();
Can this do my job?

[BlackBox]

Is this what you're after?

Code - C#: [Select]

1.         public Point3d _GetClosestPointTo(Point3d givenPoint, List<Point3d> pointList)
2.         {
3.             double distance;
4.             double smallestDist = 0.0;
5.             Point3d closestPoint;
6.  
7.             foreach (Point3d point in pointList)
8.             {
9.                 if (givenPoint != point)
10.                 {
11.                     distance = givenPoint.DistanceTo(point);
12.  
13.                     if (smallestDist == 0.0)
14.                     {
15.                         smallestDist = distance;
16.                     }
17.  
18.                     if (smallestDist > distance)
19.                     {
20.                         smallestDist = distance;
21.                         closestPoint = point;
22.                     }
23.                 }
24.             }
25.  
26.             return closestPoint;
27.         }
28.  

** Untested, and written quickly.

[TheMaster]

Hi.
I have a List<Point3d>. This List have been sorted by Y in decending. for those points with the same Y, sort them by X in decending. Then I want to find out the nearest point to a given points. My codes are below:

Code: [Select]

List<Point3d> myList = new List<Point3d>(){pt1,pt2, ..., ptn};
Point3d givenPoint = new Point3d(X1, Y1, Z1);
Point3d nearestPoint = myList.OrderBy( pt =>
Math.Abs(pt.X-nearestPoint.X) +Math.Abs(pt.Y-nearestPoint.Y) + Math.Abs(pt.Z-nearest.Z)).First();
Can this do my job?

RenderMan shows the straight-foward conventional way to do what you need.

Here's a way to do it with Linq:

Code - C#: [Select]

1.  
2.    List<Point3d> pointList = // list of candidate points
3.    
4.    Point3d bp = // point used to select nearest point in pointList
5.  
6.    // Because the same source element can be passed
7.    // to the function given to Aggregate() many times,
8.    // we cache each point along with the result of calling
9.    // DistanceTo() in an anonymous type, allowing us to
10.    // avoid redundant calls to DistanceTo():
11.    
12.    var items = pointList.Select( p => new{ point = p, dist = p.DistanceTo( bp ) } );
13.    
14.    // Find the nearest point:
15.    
16.    Point3d nearest = items.Aggregate( ( a, b ) => a.dist < b.dist ? a : b ).point;
17.  
18.  

[BlackBox]

RenderMan shows the straight-foward conventional way to do what you need.

Here's a way to do it with Linq:

Code - C#: [Select]

1.  
2.    List<Point3d> pointList = // list of candidate points
3.    
4.    Point3d bp = // point used to select nearest point in pointList
5.  
6.    // Because the same source element can be passed
7.    // to the function given to Aggregate() many times,
8.    // we cache each point along with the the result of
9.    // DistanceTo() in an anonymous type, to eliminate
10.    // redundant calls to DistanceTo():
11.    
12.    var items = pointList.Select( p => new{ point = p, dist = p.DistanceTo( bp ) } );
13.    
14.    // Find the nearest point:
15.    
16.    Point3d nearest = return items.Aggregate( ( a, b ) => a.dist < b.dist ? a : b ).point;
17.  
18.  

I'm still trying to get out of the 'linear' way of looking at things that persists coming from LISP; thanks for both confirming the validity of my offering above, and pointing out a simpler way using LINQ.

This is educational for me, Cheers! :beer:

[owenwengerd]

I didn't look very closely, but didn't the OP use dX+dY+dZ instead of the distance? That would be much faster than actually calculating the distance to each point.

[dgorsman]

With ordered points, once a point's distance is larger than the previous point then all further points do not need to be checked.  And the starting point need not be at one end of the list but can be started with getting the first sorted ordinate (Y, in the given case) that is less than or greater than (depending on front-to-back or back-to-front) the point being checked.  That can save a butt-load of iterations if a large set needs going over multiple times.

[jmaeding]

what do you mean by ordered list?
You cannot mean list of points with distance from a given point, as generating that distance takes too long.
It seems to me you could make a list of coords sorted by x coord.
It takes time to make, but can be re-used.
Use the sorted list to find first point to the left of the test point, calc its distance away.
That distance will be a search limiting factor, and will be refined as you move forward.
You will never need to look at points further away on the x axis than that distance.
Try the next point to the left, if its distance away is less, it becomes the new winner and the search radius is revised too.
Keep going left until you pass the search radius (smallest distance found so far).
Then repeat for the right side on x axis.

I wonder if the process could also be sped up by using three lists, sorted by x, y, and z.
The idea is to narrow down the search radius as fast as possible, to limit loops needed.
So maybe look at point to before test point in x list, then look at point before point in y list, and then z list.
I think that is the fastest way, but the initial list creation may take too long if it will not be re-used enough.

You could run tests to see what ratios are best for number of points, vs how many "nearest to" operations are needed. I tend to just assume large datasets, as small datasets are fast so why optimize them further?
You must deal with the large datasets though.

I did a similar routine for finding all intersecting lines/arcs. You use coords of bounding boxes instead of one coord. It sounds complicated, but when you need it, you need it bad. The efficiency gain is 100 fold.

[BlackBox]

There's been multiple mentions for how long the DistanceTo Method takes... Now, I'm all for simple, efficient code, and have never used DistanceTo() (just looked it up today)... But how long are you guys talking about the darn thing taking!?

I did a similar task in LISP to graphically select the nearest MText/Text to a user selected MText/Text, and even at 1,000,000 iterations it only took a few milliseconds.

Again, without knowing how long each concept takes on it's own precludes me from confirming the efficiency winner mentioned thus far, but the last concept of searching for the nearest point to the given point (which also assumes that the given point is a member of List<Point3d>) seems logical.

[dgorsman]

Milliseconds sounds a little low.  I've got routines that do repeated self-intersecting tests against hundreds of lists, so thats hundreds of iterations across hundreds of points, and the time is in the seconds.

[TheMaster]

I didn't look very closely, but didn't the OP use dX+dY+dZ instead of the distance? That would be much faster than actually calculating the distance to each point.

I didn't look at that part, but it looks like he's using the sum of the delta x,y,z to sort points by ordinate, and that doesn't look right.

The code I posted finds the point from the collection that's nearest to a given point.

[TheMaster]

With ordered points, once a point's distance is larger than the previous point then all further points do not need to be checked.  And the starting point need not be at one end of the list but can be started with getting the first sorted ordinate (Y, in the given case) that is less than or greater than (depending on front-to-back or back-to-front) the point being checked.  That can save a butt-load of iterations if a large set needs going over multiple times.

That's the case if the points are ordered by their distance from the given point.

But that doesn't seem to be what the OP's intention was, as he says that
the points are ordered by their X, Y and Z components.

[owenwengerd]

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.

[It's Alive!]

闻仲, if it's your intent to iterate and find the next closest point, there may be better/faster, albeit more significantly more difficult,  solutions..such as spatial indexing, Rtrees....  I would bet that there are freely available routines somewhere out there.
Cheers 

[BlackBox]

Milliseconds sounds a little low.  I've got routines that do repeated self-intersecting tests against hundreds of lists, so thats hundreds of iterations across hundreds of points, and the time is in the seconds.

No, it took milliseconds... Again, I specifically mention using MText/Text entities, and not points, which I presume the to be more of (points that is) in any given drawing. Obviously, the larger the data set, the longer the runtime for the iteration(s). Entity types may vary in the time needed to query, but that is negligible by comparison, as a generalization (conversational purposes).

[pkohut]

闻仲, if it's your intent to iterate and find the next closest point, there may be better/faster, albeit more significantly more difficult,  solutions..such as spatial indexing, Rtrees....  I would bet that there are freely available routines somewhere out there.
Cheers

A final KD Tree implementation can be found here.
http://www.theswamp.org/index.php?topic=32874.msg401826#msg401826
After the KD Tree is built (points collected), use the helper function FindNearest to find the nearest node to the queried position.

For benchmarking, building the the tree with a 1 million point set took about 2.5 seconds on my Q6600. Nearest neighbor and range queries are extremely fast.

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