Bug report #2921

Avoid intersection of new polygons.. IS BROKEN

Added by pinux - over 13 years ago. Updated about 10 years ago.

Status:Closed
Priority:Normal
Assignee:Marco Hugentobler
Category:Digitising
Affected QGIS version:master Regression?:No
Operating System:All Easy fix?:No
Pull Request or Patch supplied:No Resolution:fixed/implemented
Crashes QGIS or corrupts data:No Copied to github as #:12981

Description

In the last few month I have used a lot the "Avoid intersection of new polygons.." function i qgis. Yesterday I needed to do merge all the polygons in a postgis table, I tried it with the merge tool in qgis and it was not working. So I tried it in postgis And the result was one polygon with a lot of holes. I understood that the "Avoid intersection of new polygons.." function was not working well. After I corrected all the errors on the polygons in may table I was able to merge all the polygons even with qgis.
My next step was to create a test table with a set of test views to seen all the error that the "Avoid intersection of new polygons.." function is creating in qgis.

the test table:

CREATE TABLE av_intersection (
  gid int UNIQUE,
  t_name varchar(50),
  PRIMARY KEY (gid)
);

SELECT [[AddGeometryColumn]] ('public', 'av_intersection', 'the_geom', '900913', 'MULTIPOLYGON', 2);

CREATE INDEX av_intersection_gidx ON av_intersection USING GIST (the_geom);

the union view:

CREATE OR REPLACE VIEW av_intersection_union AS
SELECT
min(p.gid) as gid,
t_name,
st_union(p.the_geom) AS the_geom
FROM av_intersection p
GROUP BY p.t_name;

view to see if there are multiple rings:

CREATE OR REPLACE VIEW av_intersection_multiple_ring AS
SELECT
gid,
the_geom,
(ST_NRings(the_geom) - ST_NumInteriorRings(the_geom)) as nrings
FROM av_intersection
WHERE ST_NRings(the_geom) > (1 + ST_NumInteriorRings(the_geom));

and a view with all the polygons that are overlapping:

CREATE OR REPLACE VIEW av_intersection_overlaps AS
SELECT DISTINCT 
(a.gid*2+b.gid*10) as gid,
a.gid a_gid,
b.gid b_gid,
a.the_geom
FROM
av_intersection a,
av_intersection b
WHERE
a.gid != b.gid AND ST_Overlaps(b.the_geom, a.the_geom);

The result with 11 polygons:

  • union with 2 holes
  • 9 polygons are overlapping
  • 2 polygon with multiple ring

The result of the test you can see in the attachment with all the code to test yourself and the insert command for the polygons present in my test.

I have done the test on 1.5 but the problem is even in master.

avoid_intersection.sql (12.3 KB) pinux -, 2010-11-21 04:42 AM

bug_intersection_mk.png - Screenshot showing "legs" (wrong topology) in red (one selected polygon) (92.1 KB) Mayeul Kauffmann, 2011-04-16 03:55 PM

test_polygons_no_intersection_shp.zip - Shapefile illustrating wrong typology (see http://trac.osgeo.org/qgis/ticket/2921#comment:10) (2.43 KB) Mayeul Kauffmann, 2011-04-16 03:59 PM


Related issues

Related to QGIS Application - Bug report #8174: Polygons digitized in Postgis layer with "Avoid Intersect... Closed 2013-06-26

History

#1 Updated by Marco Hugentobler over 13 years ago

I cannot entirely follow your description. Do you mean that the merge tool and avoid intersection tools don't work with invalid geometries? And after you fixed the geometry errors on the polygons, it did work?
If yes, that's the behaviour I would expect. Because merge and avoid intersection use geos and I'm pretty sure it does not do union or difference on invalid geometries. Maybe postgis tests the geometries first and tries to fix them automatically?

#2 Updated by pinux - over 13 years ago

Replying to [comment:1 mhugent]:

I cannot entirely follow your description. Do you mean that the merge tool and avoid intersection tools don't work with invalid geometries? And after you fixed the geometry errors on the polygons, it did work?
If yes, that's the behaviour I would expect. Because merge and avoid intersection use geos and I'm pretty sure it does not do union or difference on invalid geometries. Maybe postgis tests the geometries first and tries to fix them automatically?

My problem is not with the merge, when I was trying to merge polygons that I had digitized with the option "Avoid intersection of new polygons" I had some errors. So i have made some view to understand what was happening with my data.
And I have found that the option "Avoid intersection of new polygons" is not working correctly:

  1. If I do an union in postgis I have 2 holes,
  2. Polygons are overlapping;
  3. Polygons with multiple ring, even if I don't have digitized polygons with multiple rings.

If you load the sql that I have uploaded you will see what I'm talking about.

The result with 12 polygons:
  • union with 2 holes
  • 9 polygons are overlapping
  • 2 polygon with multiple ring

#3 Updated by Marco Hugentobler over 13 years ago

I'm having problems importing the attached .sql into postgres:
ERROR: AddGeometryColumns() - invalid SRID
(Seems my db does not know the google crs)

Could you attach shape or spatialite? The individual (overlaping) polygons should be enough. All I need is a set of polygons to replay the problematic intersection steps.

#4 Updated by pinux - over 13 years ago

Replying to [comment:3 mhugent]:

I'm having problems importing the attached .sql into postgres:
ERROR: AddGeometryColumns() - invalid SRID
(Seems my db does not know the google crs)

Could you attach shape or spatialite? The individual (overlaping) polygons should be enough. All I need is a set of polygons to replay the problematic intersection steps.

I have uploaded a new version of the file with the SRID -1.

#5 Updated by Marco Hugentobler over 13 years ago

Ok, I can reproduce the bug now.

#6 Updated by Marco Hugentobler about 13 years ago

  • Resolution set to fixed
  • Status changed from Open to Closed

This was a rounding problem, should be fixed in 8e84137a (SVN r15088). Please test and reopen the bug if the problem still persist.

#7 Updated by pinux - about 13 years ago

  • Status changed from Closed to Feedback
  • Resolution deleted (fixed)

The problem is still present

#8 Updated by Paolo Cavallini almost 13 years ago

Is this really so bad to be blocking for 1.7?

#9 Updated by pavolsk - almost 13 years ago

Yes, it really is. I spent few hours trying to understand, where can be the problem. Apparently this function itself is not broken, removePolygonIntersections function is broken (something in the internal logic of this - something inside is antiGEOS). More or less, it is not really necessary to have function like this. Complex digitising tasks can be solved using polygonize function (polygonize plugin, polygonize in PostGIS), It would be great to have own polygonize function in QGIS core. Bugs like this are the worst promotion for digitising eager newcomers to qgis. I think, this function and removePolygonIntersections function should be droped in the new release.

#10 Updated by Mayeul Kauffmann almost 13 years ago

Hi,

I can confirm most of the above, with some comments which might help debugging.

You can try this query:

select *, st_area(geom), st_isvalid(geom)  from (select a.gid + b.gid * 100 AS gid, a.gid AS a_gid, b.gid AS b_gid,
st_setsrid((st_intersection(a.the_geom, b.the_geom)), 4326) as geom
FROM av_intersection a, av_intersection b
  WHERE a.gid < b.gid AND st_overlaps(b.the_geom, a.the_geom)) as the_intersects;

You'll see that 2 thirds of the intersections have a null area. For the other ones, their area is always (on my machine) 0.00048828125 and I believe it is a Postgis/geos error, see below:

WITH av_intersect_911 as (
select 91104 AS gid,
st_setsrid(ST_GeometryN((st_intersection(a.the_geom, b.the_geom)),4), 4326) as geom
FROM av_intersection a, av_intersection b
  WHERE a.gid=9 and b.gid=11
LIMIT 1)

SELECT gid, geom, [[GeometryType]] (av_intersect_911.geom), st_area(av_intersect_911.geom), ST_AsEWKT (av_intersect_911.geom)
FROM av_intersect_911;

The above query shows a polygon which is (part of) the intersection of polygons 9 and 11. It's area is 0.00048828125. This polygon has this EWKT definition:

"SRID=4326;POLYGON((
1517034.97851789 5634807.73109361,
1517034.97851789 5634807.73109361,
1517034.11662417 5634808.29056848,
1517034.97851789 5634807.73109361))" 

Since 3 of its four points are identical, it is trivial to say that this polygon is flat and its area is zero, hence the area computation is false.

I am not 100% sure that there are "real" intersections, as several of the intersections are not polygons but lines at the boundary of 2 polygons. Still, I agree that the topology is incorrect: the topology is broken.

Still, this does not corrupt existing data nor create invalid geometry: they can be displayed in qgis and the following is true in postgis:

select st_isvalid(the_geom) from av_intersection;

Given this postgis bug, I tried to reproduce this with a shapefile (to make sure that we are hunting a QGIS bug, not a postgis bug).

Below an ASCCI art explanation of what I found, please see also attached screenshot and attached shapefile.

You have A: 
++
    |
A   |
-----

You add B:

++++++
    |B     /
A   |     /
----|----/

Everything is OK until you add C:

   ++
  / C  \\
_/+++\\+_
    |B     /
A   |     /
----|----/

You expect C to be like this:

   ++
  / C  \\
 /+++\\

The topological error that I can confirm is the following: C is like this:

   ++
  / C  \\
 /+++\\
    |  
    |     

My conclusion:
When you add a polygon C where two polygons A and B are touching (or are supposed to), then C will have a leg going in between A and B. It is not clear whether A and B are
strictly contiguous or if there is an (unwanted) hole between them.

#11 Updated by Marco Hugentobler almost 13 years ago

The removePolygonIntersction method from QGIS just calls difference() method from geos repeatedly.

Taking the attached shape and removing the last polygon, it seems to me that the polygons in that dataset are not really adjacent to each other (there are small legs between). You could test that with the union function in QGIS directly.

Is it possible those 'legs' have been introduced by adding polygons with the 'topological editing' mode in QGIS? That's where 8e84137a (SVN r15088) enhanced the precision. Now I don't manage to introduce legs like that anymore. If you do, please send me a shapefile, a screenshot how to add the new polygon and the settings you used for it (e.g. snapping tolerance) used.

#12 Updated by Marco Hugentobler almost 13 years ago

Wait, I managed to reproduce the mentioned issue with the test shape. So probably using a more sensitive rounding tolerance should be enough.

#13 Updated by Mayeul Kauffmann almost 13 years ago

I can reproduce the bug on the shapefile I attached with those parameters:

For the shapefile I attached:

tolerance: 0.000001 (in map units)

Mode:to vertex and segment

It is still unclear to me whether there is originally a hole between A and B, or if they are OK and only C is wrong. Is there any reliable way to check? Visible inspection is useless even at scale>1:1 and postgis does not seem reliable here.

#14 Updated by Marco Hugentobler almost 13 years ago

You could check if the polygons are really have a common boundary with the merge edit tool in QGIS.

Could you try if it works with c1a768a1 (SVN r15742) (creation of the whole polygon collection, not only the last step)?

Thanks,
Marco

#15 Updated by Mayeul Kauffmann almost 13 years ago

Hi Marco,
I will look at it. In the meantime, I found this:

same bug with tolerance: 0.0001(in map units)

same bug with tolerance: 0.1(in map units)

However, with tolerance: 1 (in map units, Mode:to vertex and segment ), then there is snapping during digitization of each point, and with snapping I could not reproduce the bug anymore with 5b1e7999 (SVN r15719). (In fact, snapping makes the set operation unnecessary and probably the bug cannot appear).

#16 Updated by Marco Hugentobler almost 13 years ago

enabling 'topological editing' also plays an important role. With it enabled, qgis inserts new vertices and the bug is less likely to appear.

#17 Updated by Mayeul Kauffmann almost 13 years ago

Hi,

Unfortunately the bug is still there with c1a768a1 (SVN r15742) (with 0.000001 as snapping option in map units).

And I got as often as earlier the following message:

"The feature could not be added because removing the polygon intersections would change the geometry type."

(especially when trying to create a polygon over areas with many polygons and where many polygons touch).
Which I guess might be due to some holes in the polygons: the difference create multipart polygons, hence the message (postgis is more flexible than the shapefile format here and allows the buggy geometries to be created).

#18 Updated by Giovanni Manghi over 12 years ago

  • Target version changed from Version 1.7.0 to Version 1.7.4

#19 Updated by marisn - about 12 years ago

  • Crashes QGIS or corrupts data set to No
  • Pull Request or Patch supplied set to No
  • Affected QGIS version set to master

With current master (e71494a) I haven't used "topological editing" tool, still I see MULTIPOLYGON features in my edits. The worst part - they contain invalid geometries. I.e. one of parts is like this: ((691468.806198 299398.980041,691468.806198 299398.980041,691555.402717 298695.383322,691468.806198 299398.980041)) It doesn't pass GEOS geometry validity test, as three of polygon vertices have the same coordinate. As all polygons have been created in "non overlap" mode, there should be no holes between them (still some of polygons might be created with an older master version).

#20 Updated by Paolo Cavallini almost 12 years ago

  • Target version changed from Version 1.7.4 to Version 1.8.0

#21 Updated by marisn - over 11 years ago

  • Priority changed from Low to Normal

Didn't made to 1.8.0 and is still present in current 1.9.0 master :(

I'll take freedom to rise priority to normal, as it prevents me to finish my landcover map with many small patches. This is one of QGIS "killer" features and thus should be functional :)

#22 Updated by Paolo Cavallini over 11 years ago

  • Target version changed from Version 1.8.0 to Version 2.0.0

#23 Updated by Marco Hugentobler about 11 years ago

The small gaps appear because of numerical problems, see geos-devel list (http://lists.osgeo.org/pipermail/geos-devel/2013-February/006227.html). So my workaround in QGIS dc074b393e800368bd0ed35b137d9dd930b73f75 is to always enable topological editing if avoid intersection is used (also to background layers if they are editable).

I'm suggesting closing this ticket.

#24 Updated by Stefan Blumentrath almost 11 years ago

The bug can - at least in my case - still occur, also with snapping and topological editing activated (see discussion: http://osgeo-org.1560.n6.nabble.com/Polygon-digitalization-td5040680.html).
Although this is mainly a GEOS problem, it affects the Avoid Intersection function in in a way that it is not 100% reliable. As marsin points out, working properly, the "avoid Intersection" function would make QGIS the probably most handy tool for digitising (for example vegetation or landcover maps)...

#25 Updated by Giovanni Manghi over 10 years ago

Marco Hugentobler wrote:

The small gaps appear because of numerical problems, see geos-devel list (http://lists.osgeo.org/pipermail/geos-devel/2013-February/006227.html). So my workaround in QGIS dc074b393e800368bd0ed35b137d9dd930b73f75 is to always enable topological editing if avoid intersection is used (also to background layers if they are editable).

I'm suggesting closing this ticket.

As this workaround is not 100% error proof, is there anything else can be done to workaround this issue?

#26 Updated by Paolo Cavallini about 10 years ago

  • Target version changed from Version 2.0.0 to Future Release - High Priority

#27 Updated by Giovanni Manghi about 10 years ago

  • Resolution set to fixed/implemented

see #8174

#28 Updated by Jürgen Fischer about 10 years ago

  • Status changed from Feedback to Closed

Also available in: Atom PDF