search

mapbox / polylabel

A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)
Other
1.44k stars 151 forks source link

Use rbush to speed up probe checks #8

Open mourner opened 8 years ago

mourner commented 8 years ago

Fixes #7. Makes the implementation considerably more complex though, and I have yet to set up a real world benchmark on a variety of polygons — preliminary results show ~3-4 faster times after warming up, which is less than I hoped for. The speedup may be bigger on other platforms though.

urschrei commented 8 years ago

Nice! I'll have a look at using https://github.com/ambaxter/spatial-rs for my implementation, but yeah, I have a feeling it might be complex to implement…

drnextgis commented 7 years ago

I've tested this PR on one synthetic polygon. Calculation took about one minute. It looks like no effect compared original version:

[ [ [ 12382242.131689133122563, -7840437.468911342322826 ], [ 12382242.131689133122563, 323370.434348836948629 ], [ 18995007.833730760961771, 323370.434348836948629 ], [ 18995007.833730760961771, -7840437.468911342322826 ], [ 12382242.131689133122563, -7840437.468911342322826 ] ], [ [ 15093476.069526199251413, -6916429.451484249904752 ], [ 16647476.009505981579423, -6916429.451484249904752 ], [ 16647476.009505981579423, -4179464.127069373615086 ], [ 18631305.720118477940559, -4179464.127069373615086 ], [ 18631305.720118477940559, -2660328.417218445800245 ], [ 16647476.009505981579423, -2660328.417218445800245 ], [ 16647476.009505981579423, -106602.746021312093944 ], [ 15093476.069526199251413, -106602.746021312093944 ], [ 15093476.069526199251413, -2660328.417218445800245 ], [ 12878199.559342253953218, -2660328.417218445800245 ], [ 12878199.559342253953218, -4179464.127069373615086 ], [ 15093476.069526199251413, -4179464.12706937501207 ], [ 15093476.069526199251413, -6916429.451484249904752 ] ] ]
TWiStErRob commented 7 years ago

Something you may want to consider: I like the fact that the code is just 150 lines + a heap base priority queue implementation; e.g. I'm planning to use this in Java on Android. By accepting this pull request you add ~500+50 lines of dependencies, this hurts portability between languages a lot, and may make it harder to understand the algorithm.

mourner commented 7 years ago

@TWiStErRob yes, that's the main reason I haven't pursued merging this much.