2019-03-12 10:04:01 8 Comments

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?

### Related Questions

#### Sponsored Content

#### 5 Answered Questions

### [SOLVED] Creating Minimum Convex Polygon - Home Range from Points in QGIS

**2018-05-16 21:06:09****Phil Allman****1985**View**2**Score**5**Answer- Tags: qgis convex-hull

#### 13 Answered Questions

### [SOLVED] What are Definition, Algorithms and Practical Solutions for Concave Hull?

**2010-08-16 06:05:07****Adam Matan****45825**View**115**Score**13**Answer- Tags: geometry convex-hull algorithm concave-hull gis-principle

#### 0 Answered Questions

### How to generalize shape with PyQGIS without much Distortion in the shape?

**2018-06-25 05:29:52****Bidhan Roy****68**View**1**Score**0**Answer- Tags: qgis pyqgis python-2.7 generalization

#### 2 Answered Questions

### [SOLVED] Finding help for QGIS 3.0?

**2018-03-27 22:25:51****Shane****526**View**6**Score**2**Answer- Tags: qgis qgis-3 documentation

#### 7 Answered Questions

### [SOLVED] Finding minimum-area-rectangle for given points?

**2012-04-05 08:03:35****Developer****66468**View**67**Score**7**Answer- Tags: geometry 3d algorithm extents convex-hull

#### 1 Answered Questions

### [SOLVED] Finding documentation for arcpy.gp functions?

**2017-02-13 20:48:07****Corned Beef Hash Map****477**View**5**Score**1**Answer- Tags: arcpy spatial-analyst documentation

#### 1 Answered Questions

#### 1 Answered Questions

### [SOLVED] Calculate area of geometry derived from current feature in QGIS 2.8

**2016-03-01 00:53:00****Alec Ramsay****470**View**2**Score**1**Answer- Tags: qgis field-calculator geometry area

#### 1 Answered Questions

### [SOLVED] What algorithm does QGIS use to calculate Nearest Neighbor Index?

**2016-02-05 11:19:20****Frances Boreham****1076**View**4**Score**1**Answer- Tags: qgis algorithm spatial-statistics nearest-neighbor distance-matrix

#### 0 Answered Questions

### How to Create a Minimum Bounding Polygon in QGIS

**2014-12-20 06:06:47****cokrzys****129**View**0**Score**0**Answer- Tags: qgis geoprocessing

## 2 comments

## @Candy Gumdrop 2019-03-12 12:16:11

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`

, specifically`QgsGeometry::convexHull()`

and`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.

## @Joseph 2019-03-12 10:13:48

You can check the algorithms at QGIS Github and find scripts for all the tools such as the minimum bounding geometry.

## @Candy Gumdrop 2019-03-12 13:24:02

While these links are good starting points, it's worth noting that the algorithms themselves aren't in the QGIS source repository.

## @Joseph 2019-03-13 10:14:24

@CandyGumdrop - Thanks for providing a comprehensive answer :)