Better line algorithm
Closed this issue · 8 comments
Speedup for lines and multilines. This will need to adapt the geometry into fractional tiles to work, but that should not be a problem.
Yep. You also need to change the algorithm itself to include all tiles that get intersected.
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.
Did not end up going with Bresenham, but got something working.
@morganherlocker why did you ditch Bresenham's? The current approach is probably slower.
@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.
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
@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.
OK, made the algorithm work — will try it in tilecover now :)