[geos-devel] Progress on #837 - TopologyException in UnaryUnion

[Daniel Baston]

My PostGIS implementation may be lost to time, but I can put together a
GEOS implementation during or maybe before the sprint.

Yes, if exposed in PostGIS it would have to be as a separate function. One
correctness check is that area is preserved; it's difficult for me to
imagine a case where the algorithm I described produces an incorrect result
that still preserves area, but perhaps it's possible.

I used it most often for unioning subsets of triangulations or Voronoi
diagrams, but it did produce correct results on every TIGER dataset I
tried. It is tolerant of some noding errors, as long as they're not on a
boundary of the dissolved polygon.

Dan

On Tue, Apr 16, 2019 at 11:38 AM Martin Davis <mtnclimb at gmail.com> wrote:

> I've also been thinking that for the case of unioning a polygonal coverage
> there could be a much faster algorithm.  Good to hear that you have an
> implementation lined up.  Can you work up a GEOS version based on your Java
> code?  (And if there are any extension needed to the Polygonizer to support
> it, those can be in scope as well).
>
> Are you thinking this would be exposed as a different PostGIS function
> (say ST_UnionCoverage)?
>
> I'm aconcerned about what happens if the input is not a valid polygonal
> coverage.  It can be very hard to "see" if a dataset is coverage-valid.
> (For instance, the dataset of Norwegian poiygons that was posted recently
> is *almost* a valid coverage, but out of it's 1.2 M segments has about 3
> which cross slightly!  It might be important to provide a IsCoverageValid
> function, or perhaps even better a function to report the locations of
> crossing segments.  And ideally the ST_UnionCoverage function could report
> an error on invalid input - but it's not clear how to do that efficiently,
> which would defeat the purpose.
>
>
> On Tue, Apr 16, 2019 at 8:21 AM Daniel Baston <dbaston at gmail.com> wrote:
>
>> Either way, the union of a polygonal coverage is a common special case
>> that would benefit from having its own algorithm. I implemented this for
>> PostGIS a couple of years ago, though there didn't seem to be much interest
>> at the time [1]. It's probably a better fit for GEOS anyway. I wrote a
>> fairly ugly Java implementation several years ago [2] that I could re-do to
>> take advantage of recent polygonizer improvements and bring into GEOS.
>>
>> Dan
>>
>> [1]
>> https://lists.osgeo.org/pipermail/postgis-devel/2016-April/025784.html
>> [2]
>> https://github.com/dbaston/CoverageOp/tree/master/src/main/java/org/dbaston/coverageop
>>
>> On Tue, Apr 16, 2019 at 11:06 AM Martin Davis <mtnclimb at gmail.com> wrote:
>>
>>> That's good to know, Darafei.   Can you provide a data example that we
>>> can use for doing performance testing?
>>>
>>> I'm not seeing that JTS buffer(0) is slower than union() on a random
>>> triangulation.  So perhaps either your dataset has some different
>>> characteristic, or possibly GEOS buffer has different performance
>>> characteristics to JTS.
>>>
>>> On Tue, Apr 16, 2019 at 5:27 AM Darafei "Komяpa" Praliaskouski <
>>> me at komzpa.net> wrote:
>>>
>>>> Hello,
>>>>
>>>>
>>>>> Ultimately I think the ideal approach is going to be abandoning
>>>>> CascadedUnion and switch to a full union algorithm (which will essentially
>>>>> be the same as running buffer(0).  This should have very good performance.
>>>>>
>>>>
>>>>  We're using PostGIS's ST_Union to dissolve a clipped TIN into a
>>>> polygon. Current ST_Union implementation handles this measurably faster
>>>> than ST_Buffer(ST_Collect(geom),0). Please keep this case in mind.
>>>>
>>>>
>>>> --
>>>> Darafei Praliaskouski
>>>> Support me: http://patreon.com/komzpa
>>>> _______________________________________________
>>>> geos-devel mailing list
>>>> geos-devel at lists.osgeo.org
>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>>
>>> _______________________________________________
>>> geos-devel mailing list
>>> geos-devel at lists.osgeo.org
>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>
>> _______________________________________________
>> geos-devel mailing list
>> geos-devel at lists.osgeo.org
>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20190416/1daa0f97/attachment.html>