3

I've been using the 'Vector geometry--> Voronoi ploygons'function in QGIS to create voronoi cells for 200,000 points with success. However, recently I am working with a bigger point set (500,000 points randomly generated into a polygon repreesenting 1000km2) and the function consistently freezes without error at 99%.

I have tried outputting both to a temporary file (memory) and to a package file, but both still freeze at 99%.

Each point has coordinates and several attributes, so I thought perhaps the file was just too large for QGIS. I have tried running again with only the coordinates, but it still hangs at 99%.

Can anyone advise?

3

There is a second implementation of Voronoi in QGIS using GRASS which is maybe more stable. Search the toolbox for "voronoi", then choose "v.voronoi".

| improve this answer | |
  • This is a good suggestion, and what I attempted as a fix as well. However, I received an error in the GRASS window, with no helpful info. – Shawn Sep 25 '18 at 22:03
2

I dont have a big data set for reference on this but I have found QGIS 3.2 to be much more stable and less prone to crashing. Try to see if it can output a result on that.

Also, check if all the geometries are valid otherwise it can cause errors.

Another option to try would be to just give the points one unique attribute, say "ID" and move the rest of the data onto a spreadsheet. Once the polygon is created, use table joins to bring in the rest of the attributes.

Have you tried doing this in another software like Mapinfo? That way you know its not the input file that is causing errors.

| improve this answer | |
  • I've recently sworn off Mapinfos and ArcGIS, in favour of QGIS only workflows. However, I just tried the operation with SAGA's Thiessen polygons and it worked. Although Thiessen polygons are meant to be equivalent to Voronoi cells, I don't believe using a different function is a true solution, although it got me where I needed to go – Shawn Sep 25 '18 at 22:00
2

Eventually, I was able to get an equivalent product using SAGA --> Vector Point Tools --> Thiessen ploygons

| improve this answer | |
1

This is a bug in the interface. The progress bar passes three times during the Vonoroi tessellation.

This first pass of the progress bar represents a preprocessing step. In small sets, the progression passes almost instantly—so the bug was probably went unnoticed. In bigger sets, like in your case, it appears to hang at 99% while it is still in fact doing work. It would be best not to touch it at this point, though you can't be sure how long the process will take.

If you wait long enough, QGIS will complete the first pass and move on to the actual tessellation, which appears to progress more reasonably.

The third pass involves saving to memory or disk and garbage collection.

I'm not sure if this bug is documented. I discovered it in my tessellation of a ~70,000-point dataset, which took 10 minutes to complete on a Xeon Phi. Note QGIS processing is currently single-threaded. Best case time complexity for Vonoroi is O(n log(n)), but I am not quite sure of this specific implementation—so your mileage may vary.

| improve this answer | |
  • A great response - thanks Jack. The SAGA implementation (as per my accepted response) gives essentially the same result, so that method is still OK. Good to know that this is a bug. Your not on the time complexity estimate is valuable; thanks also for that. – Shawn Jun 28 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.