need of an advanced "GeomUnion"

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

need of an advanced "GeomUnion"

Thomas Leduc-2
Dear JTS members,

Many thanks for this lib and all functionalities it provides. Vitality of this mailing list is a proof of the strong interest of the community for it.

I'm used to use the JTS-1.10 static method "UnaryUnionOp.union(Geometry geom)". It is indeed incredibly efficient.

I wonder whether it exists an implementation able to :

- process a java.util.Collection<Polygon> as input data,
- so as to return a new java.util.Map<Polygon, Integer> as output data respecting following conditions :
  + the output Collection of polygons must be a partition of the global geometry union of the input polygons (I mean: overlap areas dimension are equals to 1: MultiLineString),
  + for each output polygon, the integer value (key of the Map) corresponds to a counter : number of occurrences of the current ouput Polygon in the input Collection of Polygon (each time it is included in an input Polygon, I increment the counter).

To sum up, let me present you a small example with just 3 polygons (please see attached image) :
- let A, B and C the input polygons,
- what I want as output result is a Map composed of the following 7 items :
A.difference(B).difference(C) ; counter = 1
B.difference(A).difference(C) ; counter = 1
C.difference(A).difference(B) ; counter = 1
A.intersection(B).difference(C) ; counter = 2
A.intersection(C).difference(B) ; counter = 2
B.intersection(C).difference(A) ; counter = 2
A.intersection(B).intersection(C) ; counter = 3

Thanks a lot for your ideas,
PS : I've about thousands polygons to process (several times).

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel

advancedGeomUnion.png (81K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Martin Davis
Thomas,

To rephrase your problem in a more standard terminology, what you're
looking for is a way of building a polygonal coverage from a set of
overlapping input polygons.  (The step of attributing the resultant
polygons with the count of their parents is a minor extension to this
basic algorithm).

Unfortunately currently JTS does not offer such a capability directly.  
It is possible to simulate this functionality in a couple of different ways:

1) Use the Polygon overlay operations to compute intersections and
differences.  However, this is complicated and very inefficient

2) Use Noding and Polygonization to create a polygonal coverage from the
linework of the input polygons, and then determine the parent count of
the polygons in the coverage by running Point-In-Polygon tests against
the input dataset (using a spatial index for performance)

I would recommend trying #2.

I am working on new code to perform a true polygon coverage overlay, but
this is not ready for release yet.

Out of curiosity, could you provide a sample dataset of your polygons?

Martin

Thomas Leduc wrote:

> Dear JTS members,
>
> Many thanks for this lib and all functionalities it provides. Vitality
> of this mailing list is a proof of the strong interest of the
> community for it.
>
> I'm used to use the JTS-1.10 static method
> "UnaryUnionOp.union(Geometry geom)". It is indeed incredibly efficient.
>
> I wonder whether it exists an implementation able to :
>
> - process a java.util.Collection<Polygon> as input data,
> - so as to return a new java.util.Map<Polygon, Integer> as output data
> respecting following conditions :
>   + the output Collection of polygons must be a partition of the
> global geometry union of the input polygons (I mean: overlap areas
> dimension are equals to 1: MultiLineString),
>   + for each output polygon, the integer value (key of the Map)
> corresponds to a counter : number of occurrences of the current ouput
> Polygon in the input Collection of Polygon (each time it is included
> in an input Polygon, I increment the counter).
>
> To sum up, let me present you a small example with just 3 polygons
> (please see attached image) :
> - let A, B and C the input polygons,
> - what I want as output result is a Map composed of the following 7
> items :
> A.difference(B).difference(C) ; counter = 1
> B.difference(A).difference(C) ; counter = 1
> C.difference(A).difference(B) ; counter = 1
> A.intersection(B).difference(C) ; counter = 2
> A.intersection(C).difference(B) ; counter = 2
> B.intersection(C).difference(A) ; counter = 2
> A.intersection(B).intersection(C) ; counter = 3
>
> Thanks a lot for your ideas,
> PS : I've about thousands polygons to process (several times).
>
> --
> Thomas LEDUC
>
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Thomas Leduc-2
Hi Martin,
I'm glad to read your answer.

On Wed, Sep 23, 2009 at 6:48 PM, Martin Davis <[hidden email]> wrote:

2) Use Noding and Polygonization to create a polygonal coverage from the linework of the input polygons, and then determine the parent count of the polygons in the coverage by running Point-In-Polygon tests against the input dataset (using a spatial index for performance)
 
To rephrase your advice, I should :
  - call the Polygonizer.add(Collection<Geometry>) method with the collection of input polygons as argument,
  - and, then, for each Polygonizer.getPolygons() item, increment the counter each time it is included in an input Polygon (using a STRtree on the input data set - that I can 1st convert into a set of PreparedPolygon so as to take benefit from its contains() method).
That's it ?

I am working on new code to perform a true polygon coverage overlay, but this is not ready for release yet.

Out of curiosity, could you provide a sample dataset of your polygons?

Yes, please see attached zip file.
Thank you for your help.

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel

sample.zip (10K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Stefan Steiniger
In reply to this post by Thomas Leduc-2
mhm.. is this the same as OpenJUMP's "Tools>Analysis>Two
Layers>Intersect Polygon Layers", but with just one layer?

I know this implementation is slow, but it may give hints if you do not
need to work on the geometry level (I think it uses option 1)

stefan

>
> Message: 1
> Date: Wed, 23 Sep 2009 09:48:48 -0700
> From: Martin Davis <[hidden email]>
> Subject: Re: [jts-devel] need of an advanced "GeomUnion"
> To: JTS Topology Suite Development <[hidden email]>
> Message-ID: <[hidden email]>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Thomas,
>
> To rephrase your problem in a more standard terminology, what you're
> looking for is a way of building a polygonal coverage from a set of
> overlapping input polygons.  (The step of attributing the resultant
> polygons with the count of their parents is a minor extension to this
> basic algorithm).
>
> Unfortunately currently JTS does not offer such a capability directly.  
> It is possible to simulate this functionality in a couple of different ways:
>
> 1) Use the Polygon overlay operations to compute intersections and
> differences.  However, this is complicated and very inefficient
>
> 2) Use Noding and Polygonization to create a polygonal coverage from the
> linework of the input polygons, and then determine the parent count of
> the polygons in the coverage by running Point-In-Polygon tests against
> the input dataset (using a spatial index for performance)
>
> I would recommend trying #2.
>
> I am working on new code to perform a true polygon coverage overlay, but
> this is not ready for release yet.
>
> Out of curiosity, could you provide a sample dataset of your polygons?
>
> Martin
>
> Thomas Leduc wrote:
>> Dear JTS members,
>>
>> Many thanks for this lib and all functionalities it provides. Vitality
>> of this mailing list is a proof of the strong interest of the
>> community for it.
>>
>> I'm used to use the JTS-1.10 static method
>> "UnaryUnionOp.union(Geometry geom)". It is indeed incredibly efficient.
>>
>> I wonder whether it exists an implementation able to :
>>
>> - process a java.util.Collection<Polygon> as input data,
>> - so as to return a new java.util.Map<Polygon, Integer> as output data
>> respecting following conditions :
>>   + the output Collection of polygons must be a partition of the
>> global geometry union of the input polygons (I mean: overlap areas
>> dimension are equals to 1: MultiLineString),
>>   + for each output polygon, the integer value (key of the Map)
>> corresponds to a counter : number of occurrences of the current ouput
>> Polygon in the input Collection of Polygon (each time it is included
>> in an input Polygon, I increment the counter).
>>
>> To sum up, let me present you a small example with just 3 polygons
>> (please see attached image) :
>> - let A, B and C the input polygons,
>> - what I want as output result is a Map composed of the following 7
>> items :
>> A.difference(B).difference(C) ; counter = 1
>> B.difference(A).difference(C) ; counter = 1
>> C.difference(A).difference(B) ; counter = 1
>> A.intersection(B).difference(C) ; counter = 2
>> A.intersection(C).difference(B) ; counter = 2
>> B.intersection(C).difference(A) ; counter = 2
>> A.intersection(B).intersection(C) ; counter = 3
>>
>> Thanks a lot for your ideas,
>> PS : I've about thousands polygons to process (several times).
>>
>> --
>> Thomas LEDUC
>>
>> ------------------------------------------------------------------------
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> jts-devel mailing list
>> [hidden email]
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>  
>
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Martin Davis
In reply to this post by Thomas Leduc-2
Polygonizer only operates on properly noded input, so you need to node
the linework of the input polygons first.

So the steps are:
1) Extract the linework (boundaries) of the source polygons
2) Node the linework.  UnaryUnionOp is a convenient way to do this
(Union on a set of LineStrings has the effect of noding them)
3) Pass the noded linework into Polygonizer and polygonize it
4) For each resultant polygon, determine an interior point and then find
the source polygons which contain this point.  You will definitely want
a spatial index for this.  Using a PreparedGeometry would improve speed
further, at the cost of using more memory.

Two caveats:

1. When I tried UnaryUnionOp on your sample data, I got a
TopologyException during noding, caused by rounding error.  One easy way
to avoid this is to reduce the precision of the input linework
(essentially snap it to a grid).  I tried reducing precision to 5
decimal places and it then worked fine   (A more theoretically correct
approach is to use snap-rounding during noding - but there's no
convenient way to do this in JTS yet.  Also my new coverage noding code
doesn't exhibit this problem, so this may just be an overly-cautious QA
check in the current union code.)

2. The Point-In-Polygon test is theoretically subject to error for some
pathological input polygons (eg very skinny ones).  Hopefully this won't
matter - or if it does cause a problem there's probably a workaround
using a filter step and a more exact test (ie test if the interiors
intersect using relate, which is expensive but accurate).  Of course,
reducing precision complicates this a bit more, since the output is then
slightly shifted from the input.  But if you're requiring that level of
accuracy, you need a more sophisticated approach anyway.


Thomas Leduc wrote:

> Hi Martin,
> I'm glad to read your answer.
>
> On Wed, Sep 23, 2009 at 6:48 PM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>
>     2) Use Noding and Polygonization to create a polygonal coverage
>     from the linework of the input polygons, and then determine the
>     parent count of the polygons in the coverage by running
>     Point-In-Polygon tests against the input dataset (using a spatial
>     index for performance)
>
>  
> To rephrase your advice, I should :
>   - call the Polygonizer.add(Collection<Geometry>) method with the
> collection of input polygons as argument,
>   - and, then, for each Polygonizer.getPolygons() item, increment the
> counter each time it is included in an input Polygon (using a STRtree
> on the input data set - that I can 1st convert into a set of
> PreparedPolygon so as to take benefit from its contains() method).
> That's it ?
>
>     I am working on new code to perform a true polygon coverage
>     overlay, but this is not ready for release yet.
>
>     Out of curiosity, could you provide a sample dataset of your polygons?
>
>
> Yes, please see attached zip file.
> Thank you for your help.
>
> --
> Thomas LEDUC
> ------------------------------------------------------------------------
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Thomas Leduc-2
On Wed, Sep 23, 2009 at 11:51 PM, Martin Davis <[hidden email]> wrote:
Polygonizer only operates on properly noded input, so you need to node the linework of the input polygons first.

So the steps are:
1) Extract the linework (boundaries) of the source polygons
2) Node the linework.  UnaryUnionOp is a convenient way to do this (Union on a set of LineStrings has the effect of noding them)
3) Pass the noded linework into Polygonizer and polygonize it
4) For each resultant polygon, determine an interior point and then find the source polygons which contain this point.  You will definitely want a spatial index for this.  Using a PreparedGeometry would improve speed further, at the cost of using more memory.

Two caveats:

1. When I tried UnaryUnionOp on your sample data, I got a TopologyException during noding, caused by rounding error.  One easy way to avoid this is to reduce the precision of the input linework (essentially snap it to a grid).  I tried reducing precision to 5 decimal places and it then worked fine   (A more theoretically correct approach is to use snap-rounding during noding - but there's no convenient way to do this in JTS yet.  Also my new coverage noding code doesn't exhibit this problem, so this may just be an overly-cautious QA check in the current union code.)

Good morning,

I've implemented the 4 steps mentioned above. On a really simple example (the one of the image sent yesterday), result is ok if I test with an interior point as written in step 4. Problem is indeed with the noding step. What I've tried to do in the linework extraction is :
- for each input polygon boundary called "boundary",
- instead of just adding it as it is to the linework collection,
- use :
   GeometrySnapper snapper = new GeometrySnapper(boundary);
   double snapTolerance = GeometrySnapper.computeSizeBasedSnapTolerance(boundary);
   and add the "snapper.snapTo(boundary, snapTolerance)" result to the linework collection.
I still have the exception even if I increase the snapTolerance value up to 0.01

What I am doing wrong ?

Many thanks for your help, once again.

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Thomas Leduc-2
In reply to this post by Stefan Steiniger
On Wed, Sep 23, 2009 at 11:08 PM, Stefan Steiniger <[hidden email]> wrote:
mhm.. is this the same as OpenJUMP's "Tools>Analysis>Two Layers>Intersect Polygon Layers", but with just one layer?

I know this implementation is slow, but it may give hints if you do not need to work on the geometry level (I think it uses option 1)

stefan

hi,
I do not think so. Indeed, I've just tried it with OJ-1.2.0 and the small sample (see the screenshot attached to my 1st mail). The result I obtain is composed of 9 rows (while I was waiting only 7 items).

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Martin Davis
In reply to this post by Thomas Leduc-2


Thomas Leduc wrote:

>
> Good morning,
>
> I've implemented the 4 steps mentioned above. On a really simple
> example (the one of the image sent yesterday), result is ok if I test
> with an interior point as written in step 4. Problem is indeed with
> the noding step. What I've tried to do in the linework extraction is :
> - for each input polygon boundary called "boundary",
> - instead of just adding it as it is to the linework collection,
> - use :
>    GeometrySnapper snapper = new GeometrySnapper(boundary);
>    double snapTolerance =
> GeometrySnapper.computeSizeBasedSnapTolerance(boundary);
>    and add the "snapper.snapTo(boundary, snapTolerance)" result to the
> linework collection.
> I still have the exception even if I increase the snapTolerance value
> up to 0.01
>
> What I am doing wrong ?
Thomas,

The GeometrySnapper is really only intended for a very specific use
case, so it isn't too surprising that it doesn't help in this
situation.  It doesn't implement full-blown snap rounding.  There is a
SimpleSnapRounder class which you could try and use (although it might
be slowish)

Or, have you tried reducing the precision of the input coordinates?

>
> Many thanks for your help, once again.
>
> --
> Thomas LEDUC
> ------------------------------------------------------------------------
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Thomas Leduc-2
On Thu, Sep 24, 2009 at 6:06 PM, Martin Davis <[hidden email]> wrote:

Thomas,

The GeometrySnapper is really only intended for a very specific use case, so it isn't too surprising that it doesn't help in this situation.  It doesn't implement full-blown snap rounding.  There is a SimpleSnapRounder class which you could try and use (although it might be slowish)

Or, have you tried reducing the precision of the input coordinates?

Good evening Martin,

Yes, indeed, a CoordinatePrecisionReduceFilter applied to each boundary is enough. What remains annoying is that the polygonization output (I mean the number of output polygons) is a function of the scale of the PrecisionModel : scale = 1.0E4 -> 77 polygons, scale = 1E5 -> 93 polygons... Visually, both results seem correct.

When I try to apply this process to the real set of polygons, I face an out of memory error (even with a -XX:+AggressiveHeap JVM option) during the UnaryUnionOp.union task (with a scale equals to 1E5 - I'll retry with a shorter value).

Concerning the SimpleSnapRounder I don't know how to use it. Is it possible for you to tell me more ?

Best regards et "merci beaucoup",

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Martin Davis


Thomas Leduc wrote:
>
>
> Yes, indeed, a CoordinatePrecisionReduceFilter applied to each
> boundary is enough. What remains annoying is that the polygonization
> output (I mean the number of output polygons) is a function of the
> scale of the PrecisionModel : scale = 1.0E4 -> 77 polygons, scale =
> 1E5 -> 93 polygons... Visually, both results seem correct.
I think that's because there's a lot of precision in the data, and a lot
of "noise" - eg linework which is almost but not quite coincident.  This
linework will tend to create lots of sliver polygons at high precision
values.  What you have to decide is how relevant those sliver polygons
are to your actual use case.  (To help decide this, you might want to
use a tool like JUMP to have a look at the extra polygons which are created)
>
> When I try to apply this process to the real set of polygons, I face
> an out of memory error (even with a -XX:+AggressiveHeap JVM option)
> during the UnaryUnionOp.union task (with a scale equals to 1E5 - I'll
> retry with a shorter value).
Hmmm.  How many polygons and vertices are in the input?  Do you have the
JVM -Xmx memory size parameter set as high as you can?

Other than that, there may not be much that can be done using the
current code.  However, if you can send me the full dataset off-list, I
can try and see whether my new overlay algorithm can handle this.
>
> Concerning the SimpleSnapRounder I don't know how to use it. Is it
> possible for you to tell me more ?
Thomas, are you able to download the current codebase from CVS?  I've
been adding some code today to allow trying out Snap Rounding on your
sample data.  The easiest thing would be for you to look at the new code
- I can point you to where it is.

>
> Best regards et "/merci beaucoup/",
>
> --
> Thomas LEDUC
> ------------------------------------------------------------------------
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Thomas Leduc-2
On Thu, Sep 24, 2009 at 11:05 PM, Martin Davis <[hidden email]> wrote:
I think that's because there's a lot of precision in the data, and a lot of "noise" - eg linework which is almost but not quite coincident.  This linework will tend to create lots of sliver polygons at high precision values.  What you have to decide is how relevant those sliver polygons are to your actual use case.  (To help decide this, you might want to use a tool like JUMP to have a look at the extra polygons which are created)


When I try to apply this process to the real set of polygons, I face an out of memory error (even with a -XX:+AggressiveHeap JVM option) during the UnaryUnionOp.union task (with a scale equals to 1E5 - I'll retry with a shorter value).
Hmmm.  How many polygons and vertices are in the input?  Do you have the JVM -Xmx memory size parameter set as high as you can?

good morning,

To be able to process all the 865 polygons (104872 nodes), I have to set those JVM options : -Xmx3072m -XX:+AggressiveHeap, but I also have to reduce the PrecisionModel scale value up to 1 ! Things seem now ok (4th step is quite heavy and still not finished !). I'll then have to evaluate the result...
 
Other than that, there may not be much that can be done using the current code.  However, if you can send me the full dataset off-list, I can try and see whether my new overlay algorithm can handle this.

I've just sent it to you. Please, let me know if you don't receive it.

Thomas, are you able to download the current codebase from CVS?  I've been adding some code today to allow trying out Snap Rounding on your sample data.  The easiest thing would be for you to look at the new code - I can point you to where it is.

Yes, I am (thanks to the "Development" section of the http://tsusiatsoftware.net/jts/main.html webpage).

Thanks a lot,

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Markus Eichhorn
Thomas,
maybe I'm a bit late, but you can also try the CascadedPolygonUnion.union(Collection polygonCollection);
This is imho more efficient than the UnaryUnionOperator.
Another try could be
GeometryCollection geomColl = new GeometryCollection(polygons);
geomColl.union();
Hope, I Gave new ideas.
Greets
Markus


2009/9/25 Thomas Leduc <[hidden email]>
On Thu, Sep 24, 2009 at 11:05 PM, Martin Davis <[hidden email]> wrote:
I think that's because there's a lot of precision in the data, and a lot of "noise" - eg linework which is almost but not quite coincident.  This linework will tend to create lots of sliver polygons at high precision values.  What you have to decide is how relevant those sliver polygons are to your actual use case.  (To help decide this, you might want to use a tool like JUMP to have a look at the extra polygons which are created)


When I try to apply this process to the real set of polygons, I face an out of memory error (even with a -XX:+AggressiveHeap JVM option) during the UnaryUnionOp.union task (with a scale equals to 1E5 - I'll retry with a shorter value).
Hmmm.  How many polygons and vertices are in the input?  Do you have the JVM -Xmx memory size parameter set as high as you can?

good morning,

To be able to process all the 865 polygons (104872 nodes), I have to set those JVM options : -Xmx3072m -XX:+AggressiveHeap, but I also have to reduce the PrecisionModel scale value up to 1 ! Things seem now ok (4th step is quite heavy and still not finished !). I'll then have to evaluate the result...
 
Other than that, there may not be much that can be done using the current code.  However, if you can send me the full dataset off-list, I can try and see whether my new overlay algorithm can handle this.

I've just sent it to you. Please, let me know if you don't receive it.

Thomas, are you able to download the current codebase from CVS?  I've been adding some code today to allow trying out Snap Rounding on your sample data.  The easiest thing would be for you to look at the new code - I can point you to where it is.

Yes, I am (thanks to the "Development" section of the http://tsusiatsoftware.net/jts/main.html webpage).

Thanks a lot,

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel



_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Thomas Leduc-2
On Fri, Sep 25, 2009 at 11:16 AM, Markus Eichhorn <[hidden email]> wrote:
Thomas,
maybe I'm a bit late, but you can also try the CascadedPolygonUnion.union(Collection polygonCollection);
This is imho more efficient than the UnaryUnionOperator.
Another try could be
GeometryCollection geomColl = new GeometryCollection(polygons);
geomColl.union();

Hi Markus,
As rephrased by Martin 2 days ago, what I'm looking for is a way of building a polygonal coverage from a set of overlapping input polygons. I'm not "really" looking for an efficient geometries union operator.
Bye,

--
Thomas LEDUC

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|

Re: need of an advanced "GeomUnion"

Martin Davis
In reply to this post by Thomas Leduc-2
Thomas,

I did get the full dataset - thanks.  I have to say, that is an
extremely challenging dataset to process!  Many almost- coincident
lines, many overlaps, and not much spatial partitioning possible.  The
last aspect - limited spatial partitioning - is probably why the
UnaryUnion is so memory-intensive and takes so long.  UnaryUnion doesn't
really provide any optimization for overlaying sets of linestrings, in
the realm of both performance and memory footprint.

I have done some preliminary testing with my new overlay algorithm, and
so far it looks promising - it noded the entire dataset at full
precision in about 250 sec, using less than 1 GB of memory. I have not
yet tried the polygon formation step, however.

This will be an excellent test case to have during my algorithm
development!  8^)

Martin

Thomas Leduc wrote:
> good morning,
>
> To be able to process all the 865 polygons (104872 nodes), I have to
> set those JVM options : -Xmx3072m -XX:+AggressiveHeap, but I also have
> to reduce the PrecisionModel scale value up to 1 ! Things seem now ok
> (4th step is quite heavy and still not finished !). I'll then have to
> evaluate the result...
>  
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel