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
