search

mapbox / tile-cover

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

Faster and simpler line cover algorithm (+60-70%) #50

Closed mourner closed 9 years ago

mourner commented 9 years ago

Addresses #28. Before:

scan road - z6 - z6 x 145,080 ops/sec ±2.21% (22 runs sampled)
scan road - z8 - z8 x 143,097 ops/sec ±1.94% (22 runs sampled)
scan road - z10 - z10 x 139,791 ops/sec ±1.47% (21 runs sampled)
scan road - z12 - z12 x 140,806 ops/sec ±1.97% (21 runs sampled)
scan road - z18 - z18 x 27,404 ops/sec ±1.25% (21 runs sampled)
scan building - z6 - z6 x 50,509 ops/sec ±1.45% (21 runs sampled)
scan building - z8 - z8 x 50,656 ops/sec ±1.85% (21 runs sampled)
scan building - z10 - z10 x 50,009 ops/sec ±1.54% (21 runs sampled)
scan building - z12 - z12 x 49,631 ops/sec ±2.06% (21 runs sampled)
scan building - z18 - z18 x 25,895 ops/sec ±7.45% (22 runs sampled)
scan russia polygon - z6 - z6 x 1,261 ops/sec ±1.77% (21 runs sampled)
scan russia polygon - z8 - z8 x 194 ops/sec ±4.92% (21 runs sampled)
scan russia polygon - z10 - z10 x 17.10 ops/sec ±5.89% (13 runs sampled)
scan russia polyline - z6 - z6 x 2,742 ops/sec ±2.79% (21 runs sampled)
scan russia polyline - z8 - z8 x 1,346 ops/sec ±1.92% (22 runs sampled)
scan russia polyline - z10 - z10 x 443 ops/sec ±1.35% (22 runs sampled)

After:

scan road - z6 - z6 x 232,156 ops/sec ±2.30% (22 runs sampled)
scan road - z8 - z8 x 231,810 ops/sec ±1.73% (22 runs sampled)
scan road - z10 - z10 x 228,979 ops/sec ±1.16% (22 runs sampled)
scan road - z12 - z12 x 223,686 ops/sec ±2.04% (22 runs sampled)
scan road - z18 - z18 x 43,110 ops/sec ±1.71% (21 runs sampled)
scan building - z6 - z6 x 79,607 ops/sec ±1.64% (21 runs sampled)
scan building - z8 - z8 x 78,612 ops/sec ±2.21% (22 runs sampled)
scan building - z10 - z10 x 79,797 ops/sec ±1.82% (20 runs sampled)
scan building - z12 - z12 x 79,706 ops/sec ±1.67% (23 runs sampled)
scan building - z18 - z18 x 39,330 ops/sec ±8.58% (21 runs sampled)
scan russia polygon - z6 - z6 x 1,460 ops/sec ±5.16% (21 runs sampled)
scan russia polygon - z8 - z8 x 195 ops/sec ±2.02% (21 runs sampled)
scan russia polygon - z10 - z10 x 16.24 ops/sec ±1.83% (10 runs sampled)
scan russia polyline - z6 - z6 x 4,672 ops/sec ±2.06% (23 runs sampled)
scan russia polyline - z8 - z8 x 2,074 ops/sec ±1.38% (20 runs sampled)
scan russia polyline - z10 - z10 x 634 ops/sec ±2.02% (23 runs sampled)
mourner commented 9 years ago

Fixed the failing polygon test, safe to merge now.