Using LINQ To Find A Closest Point
Recently there was a question on the XNA forums about finding the closest object to a certain point. Ultimately an answer was given using a for loop that is probably the best route to go. But I was curious about this and decided to try and write a LINQ query that would do the same thing.
Turns out it’s pretty easy actually. Here’s all you’d need to find the closest point. Assuming you have an IEnumerable<Vector3> called points:
Vector3 myPoint = new Vector3(0f, 23, 1f);
Vector3 closestPoint =
(from v in points
let d = Vector3.Distance(myPoint, v)
orderby d
select v).First();
Console.WriteLine("Closest Point: {0}", closestPoint);
How’s that for cool and concise? There’s a bit of garbage overhead from LINQ, so running these all the time on the Xbox might not be a great idea, but performance wise this is probably about the same as doing the manual for loop. Once I figure out my DBP game idea, I’m going to see how much I can utilize LINQ queries as they really are a nice way to condense code. Not to mention it feels really cool writing one line of code that replicates a whole for loop with distance logic and everything. 
Possibly Related Posts
(Automatically Generated)More Fun With LINQ
Finding Distances The Extension Way
Quick attempt at more complex animations
Wow. I’m *really* surprised to hear you say the performance is about the same as doing a manual loop. I ran into an issue a couple months ago that made me do some performance tests that showed running my code through a couple of foreach loops was significantly faster than the LINQ solution.
In my case I was looping through a list of 28,000 words to find anagram solutions. My painfully verbose for loop (10 lines of code) ran at 101ms whereas the LINQ solution was 167ms.
Both code blocks are shown here: http://stackoverflow.com/questions/380171/regular-expression-for-finding-parts-of-a-string-within-another
I actually said “probably”, because I never actually tested the speed :p. For my, admittedly small, test case it happened fast enough that I assumed it was good. So I made a quick test just now (http://www.ziggyware.com/codepaste.php?pasteID=1153) and you can see the results I’ve found:
Took 0.0719763 seconds to find closest point with LINQ and Vector3.Distance.
Took 0.0628771 seconds to find closest point with LINQ and Vector3.DistanceSquared.
Took 0.0973399 seconds to find closest point with LINQ and manual distance squared.
Took 0.0058474 seconds to find closest point with a foreach loop.
Took 0.0042778 seconds to find closest point with a foreach loop and Vector3.DistanceSquared.
Took 0.0063279 seconds to find closest point with a for loop and ref/ref/out Vector3.Distance.
Took 0.003603 seconds to find closest point with a for loop and ref/ref/out Vector3.DistanceSquared.
Took 0.0026592 seconds to find closest point with a foreach loop and manual distance squared.
Took 0.0031165 seconds to find closest point with a for loop and manual distance squared.
So there is a pretty big gap there in perf. The best route is a foreach loop with a manual distance squared. Interestingly the fastest LINQ was the one that utilized the Vector3.DistanceSquared instead of my manual math.
So yes, LINQ is not the most efficient mainly because it orders the WHOLE list of results. I didn’t catch that this morning due to being tired, but that makes a lot of sense now. I’m going to keep playing with LINQ and see if I can optimize it some in the coming days.
And as I keep working on my test, I realize there are a few errors in some of the maths in the above test case. Nothing that drastically changes the outcome, but worth noting.
Looking further my test is really broken because I did manual math for 2D distance; not 3D. Wow, I need more coffee today. So if you’re going to run the test, convert the manual math to 3D or change everything else to Vector2.
I always viewed LINQ as a nice-to-have and generally only use it when performance is not a concern. For example, I use it liberally in my content processors, or possibly sometimes when loading a level, where a few extra milliseconds is not significant. I’d definitely be interested in seeing how much perf you can squeeze out of it, though.
I wonder what kind of sorting algorithm LINQ uses. I’ve been trying to think of a better method than O(nlogn) for finding the closest m objects.
I’m guessing it’s using a simple bubble sort. If you run my LINQ test I commented with it runs pretty decently with 50,000 items with about .07 seconds of execution, but once you’re at 5,000,000 it took my machine 15 seconds to process. Something like O(n^2) seems rather appropriate and not all that unlikely given that LINQ probably wasn’t intended for performance sensitive code.
I’m going to keep playing with LINQ to see what things I can do. I looked a bit today and I didn’t see anything that looked really encouraging, but it’ll be a fun experiment.
It makes sense that LINQ can’t use a more efficient algorithm, given that it relies on the IEnumerable interface. I would speculate that insertion sort would be the algorithm of choice, since it’s an online algorithm and perfect for this task.
How about using Min?
points.Min(p=>Vector3.Distance(p, v))
Or skipping the let statement?
(from v in points
orderby Vector3.Distance(myPoint, v)
select v).First();
But using a space partitioning datastructure is definitely the way to go, consider e.g. KD-Tree for fixed points…