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

[Mika Heiskanen]

Hello,

On 08/22/2014 08:46 PM, GEOS wrote:
> #699: Optimize Geometry->Intersection with rectangular argument
> -------------------------+--------------------------------------------------
>   Reporter:  strk         |       Owner:  geos-devel@…
>       Type:  enhancement  |      Status:  new
>   Priority:  major        |   Milestone:  3.4.3
> Component:  Default      |     Version:  3.4.2
>   Severity:  Unassigned   |    Keywords:
> -------------------------+--------------------------------------------------
>   Intersection involving a rectangle could be optimized using rectangle
>   predicates. I've tested it for queries against large (~1.5 million
>   vertices in ~200k component polygons) and it takes the timing down from
>   ~2000 seconds to less than 3 seconds...

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.

  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.

  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.

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