Re: [Jts-topo-suite-user] taking union of large numbers of polygons slow
Brought to you by:
dr_jts
From: Martin D. <mtn...@gm...> - 2012-10-17 21:05:52
|
While each input polygon may be very simple, one problem is that as soon as you start unioning them you can wind up with holes, concavities, etc. The only thing that might offer some possibiity for improvement is that the JTS overlay algorithm starts by finding all self-intersections. This is done because polygons with holes and multipolygons may have valid points where they self-touch. Since your input polygons don't have this condition, and because the output of JTS union is guaranteed to be fully noded, you might be able to improve on the performance of this algorithm. It's still necessary to identify self-touch nodes, but this could be done via checking for duplicate vertices, rather than running a full segment noding. I'm not sure this will make all that much difference, however. The other tweak you could try is removing the check for robust noding (the call to EdgeNodingValidator at line 170 of OverlayOp.java). This is done to detect to allow snapping to be used to make overlay more robust, but if you're lucky with your data you might get away without this. I'm surprised to hear that partitioning over 8 cores didn't provide a performance boost. Any idea why not? For this to work optimally, you need to partition the polygons based on spatial proximity. Using a simple 8-cell grid is probably the easiest way of doing this. If you can post some sample input data, it might provide some further insight. Also, you might try looking at some of the spatial libraries available. Although performance is definitely a key goal of JTS, I make no claim that it has the fastest algorithm available (and in fact it deliberately sacrifices performance for robustness in some places, as in the robust noding check mentioned above). http://tsusiatsoftware.net/jts/jts-links.html#other_apis On Wed, Oct 17, 2012 at 11:28 AM, David Prime <da...@pr...> wrote: > I've tried various ways of chaining unions and partitioning the input, I > even parallelised it over 8 cores. Every tweak slowed it down. My datasets > can get pretty large - 10k polys, of approx 12 vertices each is not rare. I > don't mind losing fidelity - are there any ways I could hack the union algo > within the suite to relax constraints? For example, I know for a fact that > each of my starting polys will never have a hole, be concave or self > intersecting. From my reading of the literature, all of those things > introduce extra cost into computing an accurate union. I've been playing > with writing my own that simply samples over a grid and then draws that out > but it's cumbersome and I know I can get much better precision with other > shortcuts. > > Any ideas? > > > On Wed, Oct 17, 2012 at 4:27 PM, Martin Davis <mtn...@gm...> wrote: >> >> As Imran say, using Geometry.union() (unary union) is the fastest way >> to union geometries. It avoids some issues that can happen when using >> buffer(0), and is often faster as well. >> >> Other than that, it's hard to say what might be the issue. Do you >> think the processing is slower than it should be? Is the performance >> slowing down in a highly non-linear way? >> >> Or is it just that your dataset is very large? In this case the only >> thing that will speed things up is to use more cores, if you have them >> available. Split the dataset into several parts and process each one >> in a separate thread. Alternatively, this could done by parallelizing >> the CascadedUnion code used by unary union. I'd be interested in >> hearing if this approach works for you. >> >> On Wed, Oct 17, 2012 at 1:34 AM, David Prime <da...@pr...> >> wrote: >> > Morning all, >> > >> > I've been using JTS to do some basic work recently - unions, >> > intersections >> > and buffers - on polygons and linestrings. I've now started running into >> > performance problems when unioning large numbers of polygons (circles, >> > in my >> > case). I've read about the buffer(0) trick but it's still pretty slow. >> > Are >> > there any other performance hacks I might consider, even ones that might >> > not >> > produce an accurate result? >> > >> > Cheers, >> > David >> > >> > >> > ------------------------------------------------------------------------------ >> > Everyone hates slow websites. So do we. >> > Make your web apps faster with AppDynamics >> > Download AppDynamics Lite for free today: >> > http://p.sf.net/sfu/appdyn_sfd2d_oct >> > _______________________________________________ >> > Jts-topo-suite-user mailing list >> > Jts...@li... >> > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> > >> >> >> ------------------------------------------------------------------------------ >> Everyone hates slow websites. So do we. >> Make your web apps faster with AppDynamics >> Download AppDynamics Lite for free today: >> http://p.sf.net/sfu/appdyn_sfd2d_oct >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts...@li... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > > ------------------------------------------------------------------------------ > Everyone hates slow websites. So do we. > Make your web apps faster with AppDynamics > Download AppDynamics Lite for free today: > http://p.sf.net/sfu/appdyn_sfd2d_oct > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > |