Thanks for the feedback, Michael & Stefan. I agree, it would be nice to get this into JTS. I don't know that it will be any more performant than your solutions, but at least the API will be standardized, and maybe a clever way to improve performance even further will show up down the road. (Sleuthing out the Arc approach, maybe?). I'll try and find some time to work on this. I have an idea about enhancing the STRtree to provide a nested List mirroring the structure of the R-tree, which can then be iterated over to perform the union efficiently...
Martin Michaël Michaud wrote: > Hi Martin, > > The way I optimized the union plugin in OpenJUMP is not as clever as > using a quadtree, but it is equivalent in the ideal case of regularly > distributed features. > I just grouped features in a regular grid which size is computed based > on the featurecollection envelope and size (number of features). This is > an iterative process : when I finished the union in all grid cells, I do > it again with a larger grid until I have no more geometry to union. I > called it progressive union. > Performance improvement may be more than 10 x, and for large datasets, > it simpley make it possible to union the layer. > I did not look for a better hack at the plugin level, as I thought that > better performances can be obtained from JTS itself. But I'm not sure it > is possible : what about PreparedGeometry ? > > Regards > > Michael > > Martin Davis a écrit : > > >> Not sure I do see... Either way, if you are doing repeated calls to >> union(), then this is going to be slow. But maybe you mean that you are >> *combining* the input geometries in to a single multi-geometry, and then >> buffering that once? That should be faster, then. Although... for >> complex inputs, I suppose this could actually end up being slower than >> doing the buffers individually, and then using a cascading scheme to >> union them. >> >> Sounds like Stefan has a scheme to do this, anyway. But it would be >> nice to get it into JTS. >> >> Larry Becker wrote: >> >> >> >>> Hi Martin, >>> >>> The union operation is implemented by buffering the union of the >>> input, rather than the union of the input buffered, if you see the >>> distinction. I was hoping JTS had already optimized this, but from >>> what you are saying, I would guess not. >>> >>> Larry >>> >>> On 8/31/07, Martin Davis <[EMAIL PROTECTED]> wrote: >>> >>> >>> >>> >>>> Cool... >>>> >>>> I think that one way around the "slow union" problem is to develop a >>>> "Cascading Union" function. This will build up a union of multiple >>>> geometries by forming them into a tree, and recursively unioning the >>>> branches of the tree from the leaves to the root. In theory this >>>> should provide a fairly optimal balance between performance and memory use. >>>> >>>> A nice way to form the tree would be to add the input geometries to a >>>> JTS Quadtree or STRtree and then traverse the tree in depth-first >>>> order. Unfortunately currently the implementations don't support the >>>> ability to traverse the tree in any order - this wouldn't be too hard to >>>> add, though. >>>> >>>> Thoughts? Anyone keen on trying this out? >>>> >>>> Martin >>>> >>>> >>>> >>>> Larry Becker wrote: >>>> >>>> >>>> >>>> >>>>> I have committed the improved buffer plugin. Three sample screens are >>>>> attached in english, french, and german. It now supports buffering >>>>> the selection. It provides a convenience union option. The sidebar >>>>> picture now previews the current options. It copies attributes by >>>>> default, even from selections on multiple layers, but this can be >>>>> turned off. It supports setting the number of segments in a quarter >>>>> circle. >>>>> >>>>> Be careful with the union operation. With large selections, it can >>>>> take a long time. For instance using Uwe's GeoCity project, I tried >>>>> to buffer everything by 1000 meters. Without union it completed in >>>>> about 20 seconds, and with union I finally killed it after 5 minutes. >>>>> >>>>> regards, >>>>> Larry Becker >>>>> >>>>> >>>>> ------------------------------------------------------------------------ >>>>> >>>>> >>>>> ------------------------------------------------------------------------ >>>>> >>>>> >>>>> ------------------------------------------------------------------------ >>>>> >>>>> ------------------------------------------------------------------------ >>>>> >>>>> ------------------------------------------------------------------------- >>>>> This SF.net email is sponsored by: Splunk Inc. >>>>> Still grepping through log files to find problems? Stop. >>>>> Now Search log events and configuration files using AJAX and a browser. >>>>> Download your FREE copy of Splunk now >> http://get.splunk.com/ >>>>> ------------------------------------------------------------------------ >>>>> >>>>> _______________________________________________ >>>>> Jump-pilot-devel mailing list >>>>> Jump-pilot-devel@lists.sourceforge.net >>>>> https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel >>>>> >>>>> >>>>> >>>>> >>>>> >>>> -- >>>> Martin Davis >>>> Senior Technical Architect >>>> Refractions Research, Inc. >>>> (250) 383-3022 >>>> >>>> >>>> ------------------------------------------------------------------------- >>>> This SF.net email is sponsored by: Splunk Inc. >>>> Still grepping through log files to find problems? Stop. >>>> Now Search log events and configuration files using AJAX and a browser. >>>> Download your FREE copy of Splunk now >> http://get.splunk.com/ >>>> _______________________________________________ >>>> Jump-pilot-devel mailing list >>>> Jump-pilot-devel@lists.sourceforge.net >>>> https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel >>>> >>>> >>>> >>>> >>>> >>> >>> >>> >>> >> >> >> > > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > Jump-pilot-devel mailing list > Jump-pilot-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jump-pilot-devel mailing list Jump-pilot-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
