-
Notifications
You must be signed in to change notification settings - Fork 18
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
improve performance of FastPolygonOperations constructor #33
Conversation
replaces old O(n²) polygon slicing implementation with a quad-recursive O(n log(n)) algorithm.
Geometry[] result = new Geometry[numBands*numBands]; | ||
traverseQuads(bandIterations, 0,0, env, geom, gf, result); | ||
|
||
blocks = new ArrayList<>(Arrays.asList(result)); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
actually, one could store the result directly as a Geometry[]
variable in this.blocks
(instead of the current ArrayList<Geometry>
wrapper). But in order to stay binary compatible with current 0.5 code (that could be already running on an Ignite cluster for example 😉 ), it's probably better to keep it as it for now and change it in a later major version (0.6).
Some quick & dirty benchmarks (timings are for a full oshdb-api request including oshdb processing time, ignite data serialization and other ohsome-api overhead):
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
.
Replaces the straight-forward
O(n²)
polygon slicing implementation with a quad-recursiveO(n log(n))
algorithm (assuming that JTS' intersection method takes O(n) time to compute the intersection of a n-vertex polygon with another 4 vertex polygon). A minor additional change is that now, the number of bands is rounded up to the next power of two (mainly to make the implementation easier).