mapbox / tile-cover

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

[tile-scanline] Scanline using tile-based coords #37

Closed yhahn closed 10 years ago

yhahn commented 10 years ago

Addresses gaps in polygon scanline algorithm by switching line intersection check to use tile-based coords rather than the top edge of tiles. When switching to this much simplified coordinate system a bunch of new problems present themselves (these would also present themselves in the top-edge approach but the coordinate space is much more granular leading to much rarer occurrence...). This branch adds handling for these cases as well:

Some comparisons between current tile-scanline:

tile-scanline tile-scanline-tilecoords
orig1 tiled1
orig2 tiled2
orig3 tiled3

TODO

yhahn commented 10 years ago

Removed stray Math.min/Math.max from dev that are no longer necessary. Bench now looks good/negligible diff from tile-scanline:

# tile-scanline

scan building - z6 - z6 x 32,916 ops/sec ±2.66% (18 runs sampled)
scan building - z12 - z12 x 31,627 ops/sec ±2.59% (19 runs sampled)
scan building - z18 - z18 x 19,229 ops/sec ±8.98% (19 runs sampled)
scan building - z20 - z20 x 9,410 ops/sec ±6.09% (22 runs sampled)
scan building - z22 - z22 x 1,929 ops/sec ±1.47% (21 runs sampled)
scan building - z25 - z25 x 58.59 ops/sec ±2.45% (15 runs sampled)
scan building - z28 - z28 x 0.62 ops/sec ±0.77% (5 runs sampled)

# tile-scanline-tilecoords

scan building - z6 - z6 x 35,122 ops/sec ±7.49% (20 runs sampled)
scan building - z12 - z12 x 36,459 ops/sec ±1.29% (20 runs sampled)
scan building - z18 - z18 x 24,699 ops/sec ±1.07% (24 runs sampled)
scan building - z20 - z20 x 10,467 ops/sec ±0.63% (24 runs sampled)
scan building - z22 - z22 x 1,856 ops/sec ±1.25% (24 runs sampled)
scan building - z25 - z25 x 56.27 ops/sec ±1.02% (19 runs sampled)
scan building - z28 - z28 x 0.54 ops/sec ±4.99% (5 runs sampled)
morganherlocker commented 10 years ago

still hacking on this, but I merged it into the tile-scanline branch for simplicity