c# - Most efficient way to bin an array of geographic points? -

term(s):

• binning: in maps-based ui, objective of binning make spatial data more visible user. rather render each geographical point individually, easier digest 'bin' (e.g. hexagonal or rectangular shape, in below example) simpler information instead (e.g. number of points bin contains).

i trying bin set of geographic points (example: http://a.tiles.mapbox.com/v3/devseed.map-hw6ew799/page.html#9/-0.3246/35.8887). i'm unsure if approach efficient implementation. thoughts on 'algorithm' or pointers appreciated.

i implementing in c#.

say have csv each line (lat,lon) point. read n of them , must render these points in bins make data easier view on map.

for implementation try bin points rectangular shapes (so in example, except more square-y because it's simpler calculations). here is:

1. determine maximum , minimum latitude , longitude total of 4 different values. these values form overall bounding box of possible points. cost: n=> o(n)using afor loop, wherenis number ofpoints` read.

2. once have above 4 values, subdivide big bounding box hashmap, mapping single points respective mini-bounding box object (which contain information like: specific points contains, point count, bounds, etc). cost: * b => o(a * b), a time takes construct single bounding box , b number of bounding boxes constructed.

3. then, re-iterate through list of points, hashing each point respective bounding box. cost: n => o(n), n number of points.

sum cost (if did right): o(n + b).

is efficient algorithm?

thanks!