Minkowski dimension calculator plugin for QGIS short manual
(zip, github)


You can read about Minkowski dimension (aka box-counting dimension) at many sources [1,2]. Shortly, it characterize how complicated shape of object is. Many geographical researches are based on fractal dimensions of different natural and urban objects.

Technically, for calculating Minkowski dimension we need to:
Lets imagine this procedure with Ukraine boundaries feature from Natural Earth Data:

On each step we accurately count number of yellow squares and their sizes. Two value series obtained:
Size of cells (e): [200000, 195365, 190731, 186097, 181463, 176829, 172195, 167560, 162926, 158292, 153658, 149024, 144390, 139756, 135121, 130487, 125853, 121219, 116585, 111951, 107317, 102682, 98048, 93414, 88780, 84146, 79512, 74878, 70243, 65609, 60975, 56341, 51707, 47073, 42439, 37804, 33170, 28536, 23902, 19268, 14634, 10000]
Number of cells containing object (N): [44, 44, 43, 41, 44, 46, 49, 48, 52, 52, 54, 58, 59, 62, 62, 67, 64, 74, 77, 76, 87, 88, 96, 90, 106, 111, 120, 122, 143, 149, 158, 181, 192, 217, 242, 276, 333, 380, 458, 584, 799, 1223]

According to the method of calculating the Minkowski dimension, its value will be equal to the angular coefficient of the regression line constructed on the plane of the ranks of values of log(N) and log(1/e). Without plotting this problem can be solved, for example, using NumPy. But for clarity, lets draw:

So, Minkowski dimension for Ukraine boundaries is 1.14523476825017. Not bad.

Developed simple QGIS Plugin allows you to compute the Minkowski dimension for the objects in the sets of vector data with line geometry. Requires no additional libraries, is distributed under the GNU GPL v2, supported versions of QGIS 2.0 and above.

The main output of this module is a new (or overwrited existing) attribute of the vector layer with fractal dimension for every (or selected) feature(s). The user selects the investigated vector layer and sets the attribute name in which to save the result. Further, depending on the selected approach of constructing the grid, sets the parameters. The module supports two approaches to building grids for computing fractal dimension: the Layer Grid and Feature Grid.

Layer Grid method implies the construction of a single mesh for the whole survey area (in fact, the coverage of mesh will coincide with the coverage of a layer or selected objects), and simultaneous calculation of required indicators for all objects on it. In this case, the mesh parameters (initial and final size, the number of steps) are set by the user once. This approach allows to correctly compare dimensions of various objects in the layer, since the measurements are performed in the same cells. Requred that the complexity of the objects (and their magnitude) was comparable and could be defined with single mesh. Suppose, we want to compute the Minkowski dimension for the borders of India, Turkmenistan and Saudi Arabia (data from Natural Earth Data). In the mode of the Layer Grid the calculation will be as follows:

Grid Feature method involves constructing separate grids for each individual object, with the ability to set the grid settings through attributes. In this mode, the user can accurately and with the required accuracy to set the grid properties for each individual object, taking into account their complexity and scale, and to obtain accurate dimensions for each of them. Here's how the calculations are performed for the borders of the same States in the mode Grid Feature:

The initial information for constructing meshes are three parameters: the start size of the cell (the maximum), the size of the end cell (the smallest), the number of steps from start to end sizes. Choose the value based on the complexity and scale of objects.

In both methods, automatic selection of parameters available, at this stage implemented a rather primitive (based on extent of features in the layer).
Lets calculate the Minkowski dimension for the borders of the Russian Federation. In this case there just one feature, and there is no difference in the use of Layer Grid / Feature Grid. When automatic selection of parameters, as can be seen, the size of the smallest cell is quite large, and the calculation complexity will be made quite crudely. But - quickly, because you don't need to build a huge mesh details (what is the main problem).

Theoretically, the most correct result for the vector object will be obtained if the size of the smallest grid cell will be equal to the smallest (or close to it) the distance between neighboring nodes. So the algorithm will take into account all details. It is obvious, however, that in such case the computation will take huge time. Russia has very complex boundaries and extent. In many cases (rivers, boundaries, cities) it is possible to use maximum detail in mind is not as complex as in the example.

This is reason why it's necessary to seek a compromise consistent with common sense. If you increase the number of steps to 40 and select the minimum cell size is 50000, in the attribute table find the final value.

You can test this plugin with ex-USSR countries dataset (from Natural Earth Data)


Silent Eddie, 2015