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
