search

qgis / QGIS

QGIS is a free, open source, cross platform (lin/win/mac) geographical information system (GIS)
https://qgis.org
GNU General Public License v2.0
10.32k stars 2.97k forks source link

Difference and Symmetrical Difference give wrong results on layers containing intersecting lines #40769

Open uclaros opened 3 years ago

uclaros commented 3 years ago

Describe the bug I met a case where applying symmetrical difference on identical layers gives incorrect output instead of empty.

How to Reproduce

  1. load https://github.com/qgis/QGIS/blob/master/python/plugins/processing/tests/testdata/expected/points_to_path_grouped.gml and https://github.com/qgis/QGIS/blob/master/python/plugins/processing/tests/testdata/expected/points_to_path_grouped2.gml
  2. Run symmetrical difference on those two layers (or even use only one of them as both source layers
  3. Result is not empty

QGIS and OS versions a92c8825 on debian testing / geos 3.10.0dev-CAPI-1.15.0

Additional context Also valid for 3.14 with older geos (non overlayNG)

uclaros commented 3 years ago

Just download the files locally first

elpaso commented 3 years ago

@uclaros this rings me a bell, can you check if https://github.com/qgis/QGIS/commit/a89d564934eda16d4e5f9b93b6fd4670c4432f86#diff-4fee2614497dee4cc3f5a07119e7e69e354d0846e8e1406e0d84cd814c3e013a fixed this?

uclaros commented 3 years ago

@elpaso No, unfortunately. The offending dataset is linear and not point though.

uclaros commented 3 years ago

It seems the problem is in QgsOverlayUtils::difference() QgsGeometry::unaryUnion is applied to sourceB geometries so that a single difference() has to be computed for each sourceA geometry. However, unaryUnion fully nodes the sourceB collection, adding vertices to all line intersections, which in turn produces a difference when a line is intersected in multiple locations since there is no precision model.

The result is that Difference and Symmetrical Difference algorithms between line layers may produce wrong results and can't be trusted. Maybe for line layers QgsGeometry::collect could be used instead, but I don't know how that would affect performance.