Hei Martin, my algo works as follows:
I create a list (initialList) of features/geometries and add them all to a quadtree. I start unioning of one geometry with its neighbours (that are received from the quadtree) until there are no more close ones (i.e. merge candidates). While doing so I delete the unioned polys from the tree and add at the end the new larger poly to the tree again and to a temporaryList. Single polygons -without neihbours received from the tree - are put into a seprate singleList. Then i take the next one from the initial list... After the first round through the initial list, the tempList is set to the initialList. The process is repeated until the reassigend initialList has no more polygons - i.e. all polygons are in the singleList. the improvement for a test dataset of 24000 buildings was from estimated 24*(3min+11sec)=1h15min down to 15min (about the 15min i am not sure--but it should be about that size). I also checked how fast ArcGIS union function for these test data is; and this was incredible: a few seconds only (11sec). I would really like to know what they did (except that this is c-code..). stefan Michaël Michaud schrieb: > 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 > > ------------------------------------------------------------------------- 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
