mapbox / tile-cover

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

stripe aliasing #20

Closed morganherlocker closed 10 years ago

morganherlocker commented 10 years ago

@mourner had the awesome idea to get around slow intersection operations entirely by employing some standard rasterization techniques used in image processing. This could be drastically faster for polygon covers.

The basic algorithm:

  1. find max and min vertex y of polygon
  2. get tile of max vertex for max_zoom
  3. get intersections of a horizontal line at the tile's y value across the polygon
  4. add tiles from the first intersection (far left) to intersection + 1 (use tilebelt.pointToTile, which is fast)
  5. go to intersection + 2 and repeat [4] until there are no intersections left (this would skip over holes and caves)
  6. go to [3] for the tile one y down until you hit the min vertex tile's y
  7. return all the tiles that were added (first recursively merge tiles up if min_zoom != max_zoom)

Note: "to handle cusps like V and /\, so intersections at local minima or maxima should be counted twice"

This method would prevent split-stop optimizations (which had the potential to speed up covers with a wide range between min_zoom and max_zoom), but I think that the gain here would dwarf the penalty.

mourner commented 10 years ago

On a second thought, we can make this even faster by optimizing intersection search for each scan line.

With naive approach, it's O(N M), where N is the number of points and M is the number of scan lines (or max number of tiles in a column for the feature).

Lets say we build an y-axis centered interval tree for all the edges. We only care about M possible intersection checks, so the resulting tree height will equal log M. Then the tree construction should cost O(N log M).

Each intersection should cost O(log M), and we have M intersections to check. Then the whole scanline pass will cost O(M log M). So resulting algorithm will be O((N+M) log M). Which looks really fast to me.

mourner commented 10 years ago

Also, polyline covers can also avoid intersection checks and get lightning fast if you modify Brasanham's line drawing algorithm to include all squares intersected by a line and use it to find all the tiles.

morganherlocker commented 10 years ago

This is implemented in master as of https://github.com/mapbox/tile-cover/commit/bc45de62a8b91afd924ba754a6085d3f2ed1a542