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?
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};
Can this do my job?
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();
RenderMan shows the straight-foward conventional way to do what you need.
Here's a way to do it with Linq:Code - C#: [Select]
List<Point3d> pointList = // list of candidate points Point3d bp = // point used to select nearest point in pointList // Because the same source element can be passed // to the function given to Aggregate() many times, // we cache each point along with the the result of // DistanceTo() in an anonymous type, to eliminate // redundant calls to DistanceTo(): // Find the nearest point: Point3d nearest = return items.Aggregate( ( a, b ) => a.dist < b.dist ? a : b ).point;
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.
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.
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.
闻仲, 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
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.
Code - C#: [Select]
Point3d nearestPoint = myList.OrderBy( pt => Math.Abs(pt.X-nearestPoint.X) +Math.Abs(pt.Y-nearestPoint.Y) + Math.Abs(pt.Z-nearest.Z)).First();
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.
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.