Author Topic: How to find out the nearest point in a List<Point3d>?  (Read 16249 times)

0 Members and 1 Guest are viewing this topic.

waterharbin

  • Guest
How to find out the nearest point in a List<Point3d>?
« on: June 05, 2012, 10:14:35 AM »
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

  • King Gator
  • Posts: 3770
Re: How to find out the nearest point in a List<Point3d>?
« Reply #1 on: June 05, 2012, 11:10:27 AM »
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.
"How we think determines what we do, and what we do determines what we get."

TheMaster

  • Guest
Re: How to find out the nearest point in a List<Point3d>?
« Reply #2 on: June 05, 2012, 01:27:00 PM »
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.  
« Last Edit: June 05, 2012, 01:36:31 PM by TheMaster »

BlackBox

  • King Gator
  • Posts: 3770
Re: How to find out the nearest point in a List<Point3d>?
« Reply #3 on: June 05, 2012, 01:31:36 PM »

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:
"How we think determines what we do, and what we do determines what we get."

owenwengerd

  • Bull Frog
  • Posts: 451
Re: How to find out the nearest point in a List<Point3d>?
« Reply #4 on: June 05, 2012, 02:34:53 PM »
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

  • Water Moccasin
  • Posts: 2437
Re: How to find out the nearest point in a List<Point3d>?
« Reply #5 on: June 05, 2012, 05:11:02 PM »
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.
If you are going to fly by the seat of your pants, expect friction burns.

try {GreatPower;}
   catch (notResponsible)
      {NextTime(PlanAhead);}
   finally
      {MasterBasics;}

jmaeding

  • Bull Frog
  • Posts: 304
  • I'm just here for the Shelties.
Re: How to find out the nearest point in a List<Point3d>?
« Reply #6 on: June 05, 2012, 06:11:29 PM »
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.
James Maeding

BlackBox

  • King Gator
  • Posts: 3770
Re: How to find out the nearest point in a List<Point3d>?
« Reply #7 on: June 05, 2012, 06:25:59 PM »
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.

"How we think determines what we do, and what we do determines what we get."

dgorsman

  • Water Moccasin
  • Posts: 2437
Re: How to find out the nearest point in a List<Point3d>?
« Reply #8 on: June 05, 2012, 06:48:13 PM »
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 you are going to fly by the seat of your pants, expect friction burns.

try {GreatPower;}
   catch (notResponsible)
      {NextTime(PlanAhead);}
   finally
      {MasterBasics;}

TheMaster

  • Guest
Re: How to find out the nearest point in a List<Point3d>?
« Reply #9 on: June 05, 2012, 08:32:03 PM »
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

  • Guest
Re: How to find out the nearest point in a List<Point3d>?
« Reply #10 on: June 05, 2012, 08:37:05 PM »
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

  • Bull Frog
  • Posts: 451
Re: How to find out the nearest point in a List<Point3d>?
« Reply #11 on: June 05, 2012, 08:49:38 PM »
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!

  • Retired
  • Needs a day job
  • Posts: 8661
  • AKA Daniel
Re: How to find out the nearest point in a List<Point3d>?
« Reply #12 on: June 05, 2012, 09:27:41 PM »
闻仲, 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 
« Last Edit: June 05, 2012, 09:35:41 PM by eNotEnoughBeer »

BlackBox

  • King Gator
  • Posts: 3770
Re: How to find out the nearest point in a List<Point3d>?
« Reply #13 on: June 05, 2012, 09:57:21 PM »
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).
"How we think determines what we do, and what we do determines what we get."

pkohut

  • Bull Frog
  • Posts: 483
Re: How to find out the nearest point in a List<Point3d>?
« Reply #14 on: June 05, 2012, 10:49:46 PM »
闻仲, 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.
New tread (not retired) - public repo at https://github.com/pkohut