mapbox / tile-cover

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

Much better polygon cover algorithm #69

Closed mourner closed 9 years ago

mourner commented 9 years ago

Makes polygon cover algorithm pretty much as fast and simple as it can get. Closes #58.

@morganherlocker @yhahn you'll like this!

mourner commented 9 years ago

41 additions and 681 deletions, isn't that just cool? My favourite type of PRs.

yhahn commented 9 years ago

@mourner awesome, RIP local min/max ascii art diagrams :joy:

morganherlocker commented 9 years ago

reviewing...

roadrunner

mourner commented 9 years ago

Pushed 2 more changes:

mourner commented 9 years ago

Pushed another perf improvement that leads to up to 3x gain in some polygon cases (where there are a lot of fills):

# before
scan russia polygon - z6 - z6 x 4,849 ops/sec ±2.24% (23 runs sampled)
scan russia polygon - z8 - z8 x 429 ops/sec ±3.56% (22 runs sampled)
scan russia polygon - z10 - z10 x 25.72 ops/sec ±1.72% (13 runs sampled)
scan russia polygon multizoom - z0 - z9 x 80.18 ops/sec ±2.82% (18 runs sampled)

# after
scan russia polygon - z6 - z6 x 6,493 ops/sec ±2.12% (23 runs sampled)
scan russia polygon - z8 - z8 x 1,001 ops/sec ±2.20% (23 runs sampled)
scan russia polygon - z10 - z10 x 81.71 ops/sec ±8.53% (18 runs sampled)
scan russia polygon multizoom - z0 - z9 x 113 ops/sec ±3.30% (19 runs sampled)
morganherlocker commented 9 years ago

:racehorse: published in v3.0.1!

mourner commented 9 years ago

Ha, you're a risky guy for publishing a patch version after half of the code rewritten from scratch :) Thanks Morgan!

morganherlocker commented 9 years ago

@mourner I thought about doing a major, but decided a patch made more sense. This did not change anything functionally (that we know of), other than bugs. If we find any functional - but valid - differences, we can roll this back and publish a major version bump.

That's semver for you ¯\/(°_o)\/¯