Even without code improvements it would be handy if the javadoc included
an indication of the time complexity of each operation so that users can
more readily see how they might improve performance using this sort of
technique.
It would have saved me a lot of time if the javadoc for difference()
said it's O(n^2), (or whatever it is), and the intersection() and
buffer() are comparatively cheap, as I would have seen straight away
that splitting it up should improve performance.
------ Original Message ------
From: "Martin Davis" <[email protected]>
To: "Mart" <[email protected]>
Cc: "[email protected]"
<[email protected]>
Sent: 21/11/2014 12:28:42
Subject: Re: [Jts-topo-suite-user] Geometry.difference performance
problem
Thanks for this - I"ll do some experimenting to see if there's any
potential improvements that might be easy to implement.
The observation that Split/Difference/Union is faster than the
Difference against the original geometries isn't too surprising.
That's to be expected from non-linear operations (like difference).
The performance of difference depends (roughly) on the product of the
number of vertices in the inputs. If the number of vertices in one
input is very small (e.g 4, for a box) the operation will run a lot
faster.
But there might be something else hurting performance. Optimizing
geometric computation is playing whack-a-mole - all it takes is one
little O(n^2) operation to kill performance.
On Thu, Nov 20, 2014 at 5:00 PM, Mart <[email protected]> wrote:
Thanks for your response Martin (and Stefan).
The performance issue seems to be related to the fact that the
geometries being diffed contain complex monolithic polygons.
Below is a link to a zip file containing two sample geometries.
http://wildwildweb.com.au/temp/diff-performance.zip (4MB)
It contains both original WKT and also KML (simplified) to get a
visual sense of it.
Performing flow6.difference(flow5) on my laptop it takes almost half
an hour.
I managed to improve performance by at least a couple orders of
magnitude by doing this:
- Split the envelope that covers both geometries into a 20 x 20 grid
of rectangles
- Intersect each geometry with the 400 rectangles
- Perform the difference operation on the two intersected geometries
in each rectangle
- Combine all of the resulting diffs together using buffer(0)
This took a total of 6 seconds, with the initial intersections taking
4 seconds, the diffs 2 seconds, and combining them together again less
than a second.
So JTS can perform 400 separate difference operations about 1000 times
faster than one monolithic difference operation of the same overall
complexity. Theoretically the only difference in the result should be
additional verticies where the resulting geometries cross the grid
boundaries, but I haven't got time to confirm that myself as my
project is only used for visuals.
I doubt this technique could be exploited internally by JTS as
detecting when to use it would probably be an expensive operation in
itself, and also determining the optimal number of squares. But it
might be useful to others who encounter performance problems with
difference operations.
Mart
------ Original Message ------
From: "Martin Davis" <[email protected]>
To: "Mart" <[email protected]>
Cc: "[email protected]"
<[email protected]>
Sent: 13/11/2014 03:53:50
Subject: Re: [Jts-topo-suite-user] Geometry.difference performance
problem
Difference (and overlay operations in general) are some of the more
expensive operations in JTS. That said, they been optimized to the
abilities of (my) current knowledge. It's possible there are faster
overlay algorithms available, but all the ones I am aware of are
significant work to implement. You might try looking at some of the
other libraries here:
http://tsusiatsoftware.net/jts/jts-links.html#other_apis
Please post back if you try one of them and they are significantly
faster.
You can also post an example WKT dataset that shows the performance
question - perhaps there is some data-related improvement that is
possible. In particular, it's unlikely there is any improvement
possible due to "very small differences", but perhaps the data will
reveal something.
Re "very small differences" do you mean that due to the clipping
there is a large amount of shared linework between the geometries
being differenced?
On Tue, Nov 11, 2014 at 6:22 PM, Mart <[email protected]> wrote:
Hi all,
I'm working on a project where I need to iteratively buffer a source
geometry, clip it to another very complex geometry, and produce a
series of geometries representing the difference between each
iteration. It is simulating flow of water through a stream network.
The only way I can think of to produce each band is to use
currentGeometry.difference(previousGeometry).
This works ok but 99% of the processing time is taken up doing the
difference calculations.
Considering there is typically only a very small difference between
currentGeometry and previousGeometry I'm wondering whether there is
a more efficient way of calculating the difference.
I suspect the performance problem might be something to do with
garbage collection as it typically processes 1-4 iterations very
quickly, then spends a couple of minutes caught on a call to the
difference method. A couple of minutes on garbage collection seems a
bit excessive but it's got a 30GB heap. Are there known issues with
the performance of difference or is it just a notoriously
inefficient operation to perform?
Thanks for any insight.
Mart
------------------------------------------------------------------------------
Comprehensive Server Monitoring with Site24x7.
Monitor 10 servers for $9/Month.
Get alerted through email, SMS, voice calls or mobile push
notifications.
Take corrective actions from your mobile device.
http://pubads.g.doubleclick.net/gampad/clk?id=154624111&iu=/4140/ostg.clktrk
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
