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