开发者

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜