#699 closed enhancement (fixed)
Optimize Geometry->Intersection with rectangular argument
| Reported by: | strk | Owned by: | |
|---|---|---|---|
| Priority: | major | Milestone: | 3.5.0 |
| Component: | Default | Version: | main |
| Severity: | Unassigned | Keywords: | |
| Cc: |
Description
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...
Change History (20)
comment:1 by , 10 years ago
comment:2 by , 10 years ago
I'm currently in the process of slightly modifying the algo so that points on the rectangle boundary are also included in the output (if the other geometry has any intersection with them). This requires reviewing each testcase and adapt it to the new expectance (the code part wasn't hard)
comment:3 by , 10 years ago
UPDATE: boundary intersections are now included in the result, and GEOS can be built to automatically use RectangleIntersection from the standard intersection API by defining USE_RECTANGLE_INTERSECTION macro at compile-time.
Doing that enables a lot of other tests existing for general intersection. Some of them fail for the removal of boundary vertexes which are already covered by an edge segment, as reported by Mika on the mailing list. That we want fixed.
Some of them fail due to the presence of duplicated vertices, minor but also worth fixing.
Some are failing badly, returning invalid multipolygons.
A good starting point is ./tests/general/TestFunctionAA.xml I'll keep looking at them.
comment:4 by , 10 years ago
As of commit bd3ca56e6ecc27586f83fd7f2a0abb91e7351c49 bounday intersections are only included in the result as collection element IFF they were part of internal holes (otherwise the boundary would just be included as boundary of the exterior ring. Back to test time.
comment:5 by , 10 years ago
As of commit 94238a220de2f64f8f4753652a7659107f77ea51 also the exterior ring is correctly handled no matter its winding order. Enabling rectangle optimized intersection transparently still gives some failures which has to be researched upon.
With PostGIS a single test fails, the one for http://trac.osgeo.org/postgis/ticket/2423 It seem to be related to including a point which is already covered.
comment:6 by , 10 years ago
The inclusion of the spurious point was fixed with commit 416a6689a2e2fcd941cb57385588719934dc30ed
Thinking about it, I guess there are still many failure cases for linestrings, which are allowed to get on the same vertex multiple times (non-simple lines). In that case the builder should remove duplicate points and then avoid to add as points those that are already covered by lines. I guess it'd take another container for "boundary points".
comment:7 by , 10 years ago
Next issue: robustness.
Existing test in TestFuncionAAPrec:
Description: AA - sliver triangle, cut by polygon Geometry A: POLYGON ((10 10, 100 10, 10 11, 10 10)) Geometry B: POLYGON ((90 0, 200 0, 200 200, 90 200, 90 0)) Expected result: LINESTRING (90 10, 100 10) Obtained result: POLYGON ((90 10, 90 10, 100 10, 90 10))
In this case RectangleIntersection class returns an invalid polygon (collapsed to a line)
comment:8 by , 10 years ago
I start to think that RectangleIntersection goals (speed) may not be compatible with Geometry::intersection goals (correctness, robustness), enough that it might really be better for it to only be available as a separate interface... I'm thinking about Z interpolation, support for invalid input and tolerance to invalid output
comment:9 by , 10 years ago
Other failures: CCW shell boundary partially overlapping the rectangle boundary is not included in the result, same with shell boundary touching the rectangle boundary in a single point.
comment:10 by , 10 years ago
I'd notice that both documented failures (invalid polygon output from sliver polygon and lack of boundary line and point) would not be real failures if the behaviour is documented to be like that, and thus different from the one of Geometry->Intersection
comment:11 by , 10 years ago
A precision about the sliver polygon test: the expected result is only valid with a FIXED precision model. In FLOATING precision model there's no collapse. But this is another problem with the RectangleIntersection (it does not take PrecisionModel in consideration)
comment:12 by , 10 years ago
So I officially decided this optimization will NOT get used transparently by Geometry::intersection. There's just a lot of effort taken to validate the result which may not be the target of RectangleIntersection.
The RectangleIntersection class is more useful as it was originally, known to possibly return invalid results but good enough for some uses (quick visualization). So I'll rebase it to trunk and squash to a single commit, then commit as its C++ interface.
At that point we'll need a name for the C-API signature, a name hopefully reflecting the "quick&dirty" nature of the function.
comment:13 by , 10 years ago
| Milestone: | 3.4.3 → 3.5.0 |
|---|---|
| Version: | 3.4.2 → svn-trunk |
As of r4021 the RectangleIntersection class and a GEOSClipByRect C-API function are in trunk (for 3.5.0). I've reverted the algorithm to the initial one, just adding the CCW/CW handling.
The function will not attempt to handle precision model nor to ensure a valid output, nor to retain boundary points. But it will be fast.
Adding the PHP binding of it would be nice, before closing this ticket.
comment:14 by , 9 years ago
strk is this all done. Should we just break out the PHP binding thing as a separate ticket so we can close this?
comment:15 by , 9 years ago
It shouldn't be hard to add the PHP side. Anyone willing to play a bit in that field ?
comment:16 by , 9 years ago
| Resolution: | → fixed |
|---|---|
| Status: | new → closed |
I opened a separate ticket for PHP bindings at #734 slated for 3.6.0
Will consider this one done for 3.5.0
Work is in progress here: https://github.com/strk/libgeos/tree/svn-trunk-fast-rect-intersection
Thanks Mika Heiskanen for the algorithm!
I'm not sure if this should be in 3.4.3 or 3.5.0 ... (when ready)