how to group points of interest by lat lon for my WP7 app
I have a collection of my own PointOfInterest
classes (approx. 1500) each having their own Latitude
and Longitude
double properties.
Im trying to draw them on my screen, but at a certain logical zoom level, there is no point showing some of them because they are so close together.
How can I very efficiently group POI's by their lat lon properties?
I have this type of thing:
var pointOfInterests = (from p in PointsOfInterest select p).Distinct(new EqualityComparer()).ToList();
where the EqualityComparer
is:
public class EqualityComparer : IEqualityComparer<PointOfInterest>
{
public bool Equals(PointOfInterest x, PointOfInterest y)
{
return Math.Round(x.Latitude.Value, PointOfInterest.DecimalPlaceFilterL开发者_运维知识库evel) == Math.Round(y.Latitude.Value, PointOfInterest.DecimalPlaceFilterLevel) &&
Math.Round(x.Longitude.Value, PointOfInterest.DecimalPlaceFilterLevel) == Math.Round(y.Longitude.Value, PointOfInterest.DecimalPlaceFilterLevel);
}
public int GetHashCode(PointOfInterest obj)
{
return Math.Round(obj.Latitude.Value, PointOfInterest.DecimalPlaceFilterLevel).GetHashCode() ^ Math.Round(obj.Longitude.Value, PointOfInterest.DecimalPlaceFilterLevel).GetHashCode();
}
}
and the PointOfInterest.DecimalPlaceFilterLevel
is a static int property that I set when the user is at a certian zoom level.
But this isnt working, I keep getting overlapping POI's and its not very fast... since I am on the phone, I need it to perform very well.
Thanks for any help you can give
You may want to consider a quadtree. These trees represent a rectangular space (lat/lon will be fine, unless you have a lot of POIs around the north/south pole :) ), and a node's children subdivide it into four equal parts. Quadtrees are well documented and you shouldn't have any problem finding an algorithm that does what you need.
On the other hand, a simpler solution may just be bucketing. Imagine the world as a big grid. You can make the grid cells as big or small as you want, but in the end it's just grid, and each grid cell contains a collection of PointOfInterest objects. Insert your POIs into their appropriate place on the grid, and when you need to, it'll be easy to find all the POIs you want to filter.
I have made an example of the bucket (grid) version with C# code. This should be able to handle lots of points (fast running time code).
http://kunuk.wordpress.com/2011/09/15/clustering-grid-cluster
精彩评论