finding the closest value in a SortedDictionary

[swellfr]

Hi
i need a structure to store some 2D points and to be able to
interpolate. The pb is that i need to find very very quickly what are
the the closest values around my point.
Is the SortedDictionary the right structure and how can i search for
the 2 closest points.

Something similar to lower_bound and upper_bound method with the STL
map

Thx
manu

 

[Nicholas Paldino [.NET/C# MVP]]

manu,

I think that a List<T> would be best for this, where T is a structure
that represents your points. Let's assume that your point is the Point
structure in the System.Drawing namespace.

You could then define a comparer class which will compare points based
on the X value, like so:

public class PointXAxisComparer : IComparer<Point>
{
public int Compare(Point x, Point y)
{
// If the x parts are the same, then return 0, otherwise, return -1
if x < y or 1 if x > y.
if (x.X == y.X)
{
// Return 0.
return 0;
}

// Return -1 if x < y, 1 if x > y.
return (x.X < y.X ? -1 : 1);
}
}

You could then add all the items to your List<Point> calling Sort when
you are done, passing an instance of the above class. This will sort the
points in the list by the X value of the point.

Then, you can call BinarySearch on your list, passing an instance of
PointXAxisComparer to the method, which will return the index of the point
where X is located. If the point does not exist with that X value, then a
negative number is returned which is the bitwise compliment of the next
element that is larger than the item being searched for.

Since you would know the item that is after the one you are looking for,
the one at the index before must come before your point. You can then use
those two points to interpolate.

Of course, make sure to check for bounds conditions as well.