Porting to C++ and harmonization of Processing algorithms

[wonder-sk]

QGIS Enhancement: Porting to C++ and harmonization of Processing algorithms

Date 2023/05/03

Author Martin Dobias (@wonder-sk) and Alex Bruy (@alexbruy)

Contact wonder.sk at gmail dot com

Maintainer @wonder-sk

Version QGIS 3.34

Summary

There has been a lot of effort to move as much code of the Processing framework and its algorithms from Python to C++ for a number of reasons, mainly to improve the robustness, code quality and speed. The aim of this proposal is to continue with these efforts and port some of the remaining QGIS algorithms from Python to C++.

Currently there are at least few dozens of QGIS algorithms for Processing that are written in Python and could/should be migrated - too many to handle all at once, so we have picked a subset of algorithms: the ones that are more commonly used and they are more complex in terms of porting efforts at the same time.

In addition to that, we also want to continue the efforts to bring existing QGIS analysis functionality under the umbrella of the Processing framework, to give them benefits of Processing integration (standard GUI, batch runs, usage in models, qgis_process support).

Proposed Solution

We are going to address the following algorithms:

• Voronoi polygons and Delanuay triangulation

  • Port the algorithms from Python to C++
  • Both of these algorithms are based on an unmaintained Python module, but GEOS library provides this functionality out of the box now, so we will drop the Python module and use GEOS

• Concave Hull

  • There are two existing Python implementations of the algorithm
  • There is also implementation available in GEOS, but only from 3.11 which is fairly new and not yet widely available
  • We will implement C++ algorithm using GEOS, and also port the existing Python implementation based on Delaunay triangulation for cases when the needed GEOS algorithm is not available
  • We will deprecate the "k-nearest neighbor" variant - it will not show up in the list, but it will be still available for backwards compatibility of existing models/scripts

• Generate XYZ Tiles (2 algorithms)

  • These two algorithms are in Python, they have a bit brittle multi-threaded implementation
  • We will port them to C++, including proper and safer multi-threading support

• Raster Calculator

  • There is a custom GUI (menu Raster > Raster Calculator) in C++ and there is a Processing algorithm in Python
  • We will port the Python implementation to C++ (including the GUI widgets for Processing) and we will drop the custom GUI - the entry in Raster menu will open the Processing algorithm instead. The existing custom GUI will be dropped
  • A separate "Raster calculator" algorithm will be created to produce virtual raster layers (with a different output type)

• Align Rasters

  • This algorithm is not available in Processing framework, only through a custom GUI (menu Raster > Align Rasters)
  • We will port the algorithm to Processing (including a new parameter type and its GUI) in C++ and we will drop the custom GUI - the entry in Raster menu will open the Processing algorithm instead

Affected Files

Python modules in python/plugins/processing/algs/qgis, C++ classes in src/app (QgsRasterCalcDialog, QgsAlignRasterDialog)

Performance Implications

Performance should stay the same or improve thanks to porting from Python to C++

Backwards Compatibility

All changes should be backwards compatible. Users will be presented with a slightly different GUI layout in Raster Calculator and Align Raster tools, but the functionality will be the same.

Votes

(required)

[elpaso]

Nice to see this coming!

About the raster calculator I am totally in favor of dropping the python one in favor of the existing C++ implementation, I don't see why re-implementing it in C++ is required: the Python implementation already uses the C++ QGIS classes.

[wonder-sk]

About the raster calculator I am totally in favor of dropping the python one in favor of the existing C++ implementation, I don't see why re-implementing it in C++ is required: the Python implementation already uses the C++ QGIS classes.

Yes, raster calculator itself is in C++, but there are some Processing-related GUI widgets for raster calculator processing alg implemented in Python - these will need to be ported to C++ so that we can get rid of those bits (I am talking about python/plugins/processing/algs/qgis/ui/RasterCalculatorWidgets.py)

[nyalldawson]

Great proposal @wonder-sk !

Voronoi polygons and Delanuay triangulation
Port the algorithms from Python to C++
Both of these algorithms are based on an unmaintained Python module, but GEOS library provides this functionality > out of the box now, so we will drop the Python module and use GEOS

This one is actually a little trickier then it first looks -- while I'm all in favour of removing that unmaintained module, it does offer something we use which is NOT possible via the GEOS implementation. Specifically the module retains information about the input features, so the voronoi polygons output includes the input point feature attributes, and the delaunay triangulation output includes the feature ids of the 3 points which each triangle was built from.

We could handle the voronoi output attribute situation by re-joining the voronoi polygons to the original point set and copying the attributes across (albeit with the performance penalty associated with the point-in-polygon tests).

However, I can't see an elegant way to handle the delaunay output attributes. We likely can't just compare the output triangle vertices against the input ones due to numerical instability in the calculations. Possibly we could do some nearest neighbour indexing approach, that's the best approach I can think of.

But ideally, this situation would be entirely handled in the GEOS library. There's been prior discussion there about ensuring that voronoi multipolygon features always keep the same ordering as input points, but in my understanding this wasn't yet implemented. And there's been no discussion yet about handling the delanauy input->output associations...

Align Rasters

I'd be very happy to see this ported to processing 🥳

[wonder-sk]

Specifically the module retains information about the input features, so the voronoi polygons output includes the input point feature attributes, and the delaunay triangulation output includes the feature ids of the 3 points which each triangle was built from.

@nyalldawson Thanks for pointing it out, I was not aware of that bit.

While it is a bit of a complication, I do not see a big problem with either of those:

• voronoi - the point in polygon tests should be fairly straightforward, with a spatial index things should be quite efficient
• delaunay - my understanding is that with zero tolerance, the coordinates of input points should perfectly coincide with the coordinates of vertices of output triangles. With non-zero tolerance (currently only supported by GEOS, not by the processing alg), the points may not align perfectly, but my assumption is that the output vertices will be coincident with a subset of the original points - so even here searching for the source points should be easy.

I can imagine that this post-processing for both voronoi & delaunay could be optional within a parameter (but enabled to keep algorithms backwards compatible), so those who don't need it won't get the performance penalty. By the way, for delaunay, it could be very useful to get not just the feature IDs copied to output triangles, but (optionally?) even the attributes like with voronoi.

Performance-wise, the existing Processing algorithms seem extremely slow: trying it with a simple layer with 52 points (tests/testdata/3d/trees.shp), voronoi took 66 seconds (!) and delaunay took 450 seconds (!!!). It think the slowness is in "our" current post-processing (doing loads of getFeatures() calls), not in the custom voronoi module itself. So even with the addition of some extra work, we should see at least 10x speed improvement 🙂

[agiudiceandrea]

About the "Delaunay triangulation" and the "Voronoi polygons" algorithm, see the issue qgis/QGIS#52172 probably due to some numerical instability.

[anitagraser]

The work has been completed with several pull requests:

 * Port various geometry algorithms to C++ qgis/QGIS#53787
 * Port Align Rasters tool to Processing qgis/QGIS#53874
 * Port Raster Calculator algorithm to C++ qgis/QGIS#54035
 * Port XYZ Tiles algorithms to C++ qgis/QGIS#54321

Existing Processing algorithms Voronoi Polygons and Delaunay Triangulation have been ported to C++ and now use GEOS instead of the unmaintained Python module. Both algorithms have been given additional parameters to disable post-processing step (adding attributes of input points for Voronoi polygons and adding feature IDs of the 3 points forming a triangle for Delaunay triangulation) and thus improve algorithm performance. The Concave Hull algorithm has been ported to C++ and uses GEOS for QGIS builds with GEOS >= 3.11, while a port of the existing implementation based on Delaunay triangulation is used for builds with older GEOS versions.

Two algorithms for generating XYZ tiles (directory and MBTiles variants) have been ported to C++ using a safer and cleaner multi-threading approach.

The Align Rasters tool (available from the Raster → Align Rasters menu), which was not exposed to Processing, has been removed and a new Processing algorithm with the same functionality has been added. To make this possible, we have added a new QgsProcessingParameterAlignRasterLayers parameter type to Processing, which provides an adapter to QList<QgsAlignRaster::Item>.
The "Raster" menu item now opens the Processing algorithm. We have also added a separate, simplified modeler-only version of the algorithm that accepts a single raster to align and returns a single raster layer output.

The existing Raster Calculator algorithm has been ported to C++. The algorithm now has two variants: a toolbox version that works the same way as before, and a modeler version that uses the same approach to input naming as the GDAL raster calculator (in the formula, you should use letters instead of layer names). The old algorithm implementation has been retained for compatibility with existing models and will be removed in QGIS 4. We have also added a separate raster calculator algorithm for creating virtual raster layers.