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

[Sandro Santilli]

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; 

 ()  ASCII ribbon campaign  --  Keep it simple !
 /\  http://strk.keybit.net/rants/ascii_mails.txt