I'm looking for the algorithms (the math) used by QGIS but I can't find any documentation about it
The ones I'm looking for are:
- Minimum bounding geometry (convex hull)
- Clip a polygon by a polygon
Does anyone knows where I can find them?
The "minimum bounding geometry" and "clip polygon" algorithms in QGIS are implemented in /python/plugins/processing/algs/qgis/MinimumBoundingGeometry.py and /src/analysis/processing/qgsalgorithmclip.cpp.
If you follow through the source of these, you'll find that they rely on geometry-related functions from a C++ class called
QgsGeometry::intersection(). The "clip" algorithm also contains additional logic for building a union of geometries to form a mask polygon, as well as testing for points within the polygon, in the case of non-polygon vectors.
Reading through the
QgsGeometry class shows that the actual algorithms themselves are implemented in a library called GEOS. GEOS is a C++ port of a Java library called the JTS Topology Suite, which implements a suite of geometry-related algorithms.
The core of the
ConvexHull algorithm from GEOS is implemented here using an algorithm called Graham's scan. The implementation of intersection in GEOS is a bit more complicated and spread out, but here's a place to start looking. GEOS supports various binary operations between geometries and "intersection" is only one of them.
In general, GEOS is the place to look for the implementations of the various vector algorithms in QGIS, but there are also some raster algorithms in QGIS which are implemented by the GDAL library.