search

mapbox / tile-cover

Generate the minimum number of tiles to cover a geojson geometry
MIT License
189 stars 40 forks source link

Better line algorithm #28

Closed morganherlocker closed 9 years ago

morganherlocker commented 9 years ago

Speedup for lines and multilines. This will need to adapt the geometry into fractional tiles to work, but that should not be a problem.

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

mourner commented 9 years ago

Yep. You also need to change the algorithm itself to include all tiles that get intersected.

morganherlocker commented 9 years ago

A basic Bresenham's algo is implemented on the tile-scanline branch

https://github.com/mapbox/tile-cover/blob/tile-scanline/index.js#L200-L245

Now I just need to make the tolerance such that every intersecting tile is included in the hash map.

morganherlocker commented 9 years ago

Did not end up going with Bresenham, but got something working.

https://github.com/mapbox/tile-cover/commit/10f18436518900879b7684221e6f7b476b8a1445

mourner commented 9 years ago

@morganherlocker why did you ditch Bresenham's? The current approach is probably slower.

morganherlocker commented 9 years ago

@mourner Bresenham did not have float precision, so it dropped or added tiles inappropriately. There might be a way to get it working with floats properly, but all of the implementations I found were rounding off points to an integer value.

mourner commented 9 years ago

You may want to kill me, but I've found a clean, elegant algorithm that fits our use case and should be much faster: http://www.cse.chalmers.se/edu/course/TDA361/grid.pdf

morganherlocker commented 9 years ago

@mourner I actually read that one. I was never able to get it working properly based on the description (cannot remember what exactly was off), but someone else might have more luck. I agree that an incremental error approach like this would be ideal.

mourner commented 9 years ago

OK, made the algorithm work — will try it in tilecover now :)