Bug report #8002

Voronoi Polygons tool makes overlapped polygons

Added by dr - over 7 years ago. Updated about 2 years ago.

Status:Closed
Priority:Normal
Assignee:-
Category:Processing/QGIS
Affected QGIS version:3.0.0 Regression?:No
Operating System: Easy fix?:No
Pull Request or Patch supplied:Yes Resolution:fixed/implemented
Crashes QGIS or corrupts data:No Copied to github as #:16852

Description

1) Open vector layer garden-nodes-merc1.shp (in attachment);
2) Build Voronoi Polygons using appropriate tool;
3) Change transparency of layer to 50%;
In result you can see that some of adjacent polygon are overlapped

garden-nodes.zip (1.84 KB) dr -, 2013-06-05 03:24 AM

voronoi-issue.png (139 KB) dr -, 2013-06-05 03:53 AM

london.geojson (2.73 KB) Giles Collingwood, 2013-09-05 03:25 AM

Capture2.PNG (186 KB) Giles Collingwood, 2013-09-05 03:25 AM

voronoi_errors.png - Before patch - darker pinks are overlaps (482 KB) Andrew Bevitt, 2015-07-15 04:47 PM

voronoi_patched.png - After patch - no darker green areas (448 KB) Andrew Bevitt, 2015-07-15 04:47 PM

voronoi.patch Magnifier - Patch against master but applies cleanly to 2.8.1 (8.31 KB) Andrew Bevitt, 2015-07-15 04:47 PM


Related issues

Duplicated by QGIS Application - Bug report #18212: Voronoi creates overlapping polygons Rejected 2018-02-24

Associated revisions

Revision 28fa839a
Added by Håvard Tveite about 2 years ago

[processing] Update to VoronoiPolygons.py, some fixes for #8002

  • Update to VoronoiPolygons.py, fixes #8002 adds comments, ++
  • Fixed a spelling an an indentation mistake reported by travis
  • Found some new cases (vertical line clipping and a mistake in the handling of extreme points)

Revision acbb27c2
Added by Håvard Tveite about 2 years ago

[processing] Update to VoronoiPolygons.py, some fixes for #8002

  • Update to VoronoiPolygons.py, fixes #8002 adds comments, ++
  • Fixed a spelling an an indentation mistake reported by travis
  • Found some new cases (vertical line clipping and a mistake in the handling of extreme points)

(cherry-picked from 28fa839a0)

Revision d2b71c30
Added by Håvard Tveite about 2 years ago

[processing] Added isclose function to VoronoyPolygons.py to avoid numerical instability

Fixes #8002 - hopefully, and adds tests

Revision 7c2a9982
Added by Håvard Tveite about 2 years ago

[processing] Added isclose function to VoronoyPolygons.py to avoid numerical instability

Fixes #8002 - hopefully, and adds tests

(cherry-picked from d2b71c30)

History

#1 Updated by Maxim Dubinin over 7 years ago

f1f17ed

works good for me (with 5% buffer and without)

#2 Updated by dr - over 7 years ago

Update QGIS to current master 5e29777 and get the same issue.

#3 Updated by Giovanni Manghi over 7 years ago

  • Status changed from Open to Feedback

result is ok here too (master/linux).

#4 Updated by Daniel Vaz over 7 years ago

I can't reproduce this bug. Probably it was fixed in meanwhile.

I think that issue should be closed.

Thanks in advance.

#5 Updated by Giovanni Manghi over 7 years ago

  • Resolution set to worksforme
  • Status changed from Feedback to Closed

Closing for lack of feedback and because seems ok now, please reopen if necessary.

#6 Updated by Giles Collingwood about 7 years ago

Hi I managed to reproduce this issue with a very small data set of 14 points on the master version today (QGIS-OSGeo4W-1.9.0-35-Setup.exe) attached a screenshot showing the overlapping polygon selected and the data file that generated it.

#7 Updated by Anita Graser over 6 years ago

  • Category changed from Vectors to 44
  • Resolution deleted (worksforme)

You can easily replicate the issue using the airports dataset from QGIS sample dataset. It creates overlapping polygons if used from the Vector menu as well as in processing.

#8 Updated by Andrew Bevitt over 5 years ago

This is still an issue in 2.8* and the master branch. This issue stems from the line clipping function incorrectly calculating intercept points for the buffer boundary. Attached is a patch to correct this and two example images before and after (5% buffer applied). In the images the Voronoi layer has 50% transparency. In the before the darker pinky/purple areas are where the polygons are overlapping. In the after there is no such darker (green) region.

#9 Updated by Giovanni Manghi about 5 years ago

  • Operating System deleted (Windows)
  • Pull Request or Patch supplied changed from No to Yes

Andrew Bevitt wrote:

This is still an issue in 2.8* and the master branch. This issue stems from the line clipping function incorrectly calculating intercept points for the buffer boundary. Attached is a patch to correct this and two example images before and after (5% buffer applied). In the images the Voronoi layer has 50% transparency. In the before the darker pinky/purple areas are where the polygons are overlapping. In the after there is no such darker (green) region.

Many thanks for this patch! I tested it and it produces much better outputs, for example fixes the issue described here #13092.

Anyway there are point layers where still overlapping polygons are produced, for example the "airports" shape of the qgis sample dataset.

#10 Updated by Giovanni Manghi almost 4 years ago

  • Category changed from 44 to Processing/QGIS

#11 Updated by Giovanni Manghi almost 4 years ago

  • Priority changed from High to Normal

#12 Updated by Giovanni Manghi over 3 years ago

  • Easy fix? set to No
  • Regression? set to No

#13 Updated by Alexander Bruy over 2 years ago

#14 Updated by Erik Sigra over 2 years ago

This is a confirmation that the bug is still reproducible in QGIS 3.0.0.

#15 Updated by Giovanni Manghi over 2 years ago

  • Description updated (diff)
  • Affected QGIS version changed from master to 3.0.0

#16 Updated by Håvard Tveite about 2 years ago

  • % Done changed from 0 to 100
  • Status changed from Reopened to Closed

#17 Updated by Håvard Tveite about 2 years ago

With the applied changeset, there are still issues with overlapping polygons for the airports dataset. https://github.com/qgis/QGIS/pull/7566 adds more numerically robust comparison, and that seems to solve the issue also for the airports dataset.

#18 Updated by Håvard Tveite about 2 years ago

The pull request that fixed the airport dataset issue has been merged, so I suggest that this issue can be closed.

#19 Updated by Giovanni Manghi about 2 years ago

  • Resolution set to fixed/implemented

Also available in: Atom PDF