[geos-devel] [GEOS] #699: Optimize Geometry->Intersection with rectangular argument

[Rémi Cura]

2014-08-27 10:09 GMT+02:00 Sandro Santilli <strk at keybit.net>:

> On Tue, Aug 26, 2014 at 09:22:20PM +0300, Mika Heiskanen wrote:
>
> > >#699: Optimize Geometry->Intersection with rectangular argument
>
> > This spring we needed GEOS clipping functionality for rendering maps.
> > Unfortunately GEOS failed to clip the ~3 million vertex ESRI Europe map
> > data, which was key for us, it gave up after about 6 seconds. A quick
> > look at the GEOS code revealed there was no special code for rectangular
> > clipping. Since we were in a hurry, we wrote the needed code ourselves.
> > The resulting code could clip the ESRI data in 0.05 seconds.
> >
> > The code
> >
> >  o was written to use OGR/GDAL objects directly. OGR converts its
> >    geometries to GEOS geometries for more complex tasks, we thought
> >    this was an unnecessary step for us. However, there should be
> >    no reason why converting to code to use GEOS objects would not
> >    be fairly easy.
> >
> >  o allows for two kinds of clipping:
> >
> >     - a polygon remains a polygon if any part of it is inside
> >       the clipping rectangle. The resulting polygon will follow the
> >       edges of the clipping rectangle to maintain the geometry.
> >
> >     - a polygon may become a linestring if any part of it is
> >       outside the clipping rectangle.
>
> If I understood it correctly the second kind would be equivalent
> to the first kind applied to the boundary of the polygon (clipping
> lines instead of polygons).
>
> >  o handles all special cases we could imagine on paper such as
> >    edges entering the rectangle from a corner. There are about
> >    150 tests for such special cases.
>
> That's great !
>
> >  o should be very robust, but we're not experts on that.
> >
> > The code is fast for clipping geometries typical in mapping, we
> > did not consider vastly complex cases which might be mostly of
> > academic interest. For example, if a geometry component begins with a
> > coordinate to the left of the clipping rectangle, only one coordinate
> > comparison is used to decide whether the next vertex is still to the
> > left.
>
> Neat
>
> > We do not have any benchmarks on how our code compares with other
> > resources, apart for the GEOS failure we encountered.
> >
> > If there is interest in our code, we can contribute some time to
> > integrate it with GEOS, but would mostly likely need co-operation from
> > someone already working with GEOS.
> >
> > Mika Heiskanen / Finnish Meteorological Institute
>
> I'm very interested in your code and willing to help with integration.
>
> I guess this could be a RectangleIntersection class under a new
> geos::operation::intersection namespace, eventually further wrapped
> by a generic IntersectionOp using RectangleIntersection when an input
> is a rectangle or the generic OverlayOp in other cases.
> Then Geometry::intersection would be using that specialized class.
>
> Please let me know how I can help with this.
>
> PS: I added Dr.JTS in CC, as he might be interested about this for JTS too
>
> --strk;
>
>
This upgrade would be _much_ appreciated here.
Very good news, thanks !
Cheers,
Rémi-C
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20140827/533c174b/attachment.html>