[geos-devel] Possible speed improvement for overlay operations

Martin Davis mtnclimb at gmail.com
Fri Nov 30 09:25:04 PST 2018


On Fri, Nov 30, 2018 at 4:49 AM Darafei "Komяpa" Praliaskouski <
me at komzpa.net> wrote:

>
>
> On Fri, Nov 30, 2018 at 12:05 AM Martin Davis <mtnclimb at gmail.com> wrote:
>
>>
>>
> Can you share one?
>

There's one in GeoTools:
https://github.com/geotools/geotools/blob/master/modules/library/main/src/main/java/org/geotools/geometry/jts/GeometryClipper.java

But I see comments that indicate it may not produce valid geometry either,
just something good enough for rendering.  But the basic approach
(Cohen-Sutherland / Liang-Barsky) might be possible to make valid.
There's a JTS-adapted port here, so you can try it in TestBuilder:
https://github.com/dr-jts/jts-ports

>
>
>>
>> Collapsed linework causes problems in the topology-building phase of
>> overlay - the noding doesn't care.   I've been wrestling with this a bit
>> recently, to try and get snap-rounding to work.  Unfortunately it's not
>> easy.  One issue is that the GeometryGraph code is quite complex and
>> supports both overlay and relate computation.  I think these are probably
>> going to have to split apart, and then both can be optimized for their
>> different usages.
>>
>
> May it happen that snap-rounding for axis aligned overlaps is more trivial
> than one for generic overlap?
>

Maybe... although snap-rounding in theory is a global operation that needs
to be applied to the entire line arrangement, to ensure that no lines
result in further intersections after adjustment.  But as per previous
comment, maybe it's possible to restrict it to just the rectangle area.
That won't make it more "trivial", however, since a geometry can be highly
complex inside the rectangle.  It should be faster though.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181130/ec3834a5/attachment.html>


More information about the geos-devel mailing list