mapbox/tile-cover

Scanline algorithm without intersections

Closed this issue · 0 comments

It just suddenly occurred to me that there might be a way to get scanline polygon cover without ever calculating intersections at all (and thus not needing active edge table and similar techniques).

All we theoretically need is launching the line-cover algo, which is super-fast, but instead of saving tiles in a hash map, save them in a 2-dimensional array with each element corresponding to Y coord (so that tiles[y] is a list of tiles on the Y coord). We would also need to track local minima/maxima as we go.

What we essentially get is a list of all tile "intersections" per Y scanline, without ever needing to actually calculate an intersection. This could be potentially super-blazing-fast. What do you think?