Simplifying polygon by inner angle in QGIS

Question

I'm trying to simplify a polygon using the interior angle of a vertex as the "tolerance" instead of the distance between vertexes. For e.g. the polygon in the image below would lose one vertex, because of its large internal angle. As an example, I might want to remove all vertexes with an internal angle greater than 170°.

They don't have holes and are mostly rectangular yes. The issue is I'm trying to perform this operation on a large number of polygons, so doing this manually wouldn't be easy — Alec McKay, May 22 '21 at 16:34
Please, do not forget about "What should I do when someone answers my question?" — Taras, Apr 21 '23 at 15:55

Cyril Mikhalchenko · Accepted Answer · 2021-05-24T17:10:04.090

6

Initial data: a pentagon (polygon1).

Output: a simplified quadrilateral.

The process is shown in the gif below in Figure 1.

The sequence of operations from bottom to top is shown in figure 2,

9) Vector->Processing geometry->Combine by feature...
8) Vector->Processing geometry->Delaunay triangulation...
7) Vector->Processing->Intersect...
6) Data Analysis->Analysis Tools->Vector Geometry->Blow Lines...
5) Vector->Processing geometry->Convert polygons into lines...
4) Vector->Process Geometry->Voronoi Polygons...
3) Vector->Processing geometry->Extract vertices...
2) Vector->Processing geometry->Centroids...
1) Source data.

Save the result...

and don't forget to add the centroid to the vertices in the sequence of actions :-)...

option 2

Input data: set of single-type polygons of pentagon-envelope type.

Output data: simplified polygons of the quadrangle type.

The process is shown in Figure 3 below

The sequence of operations is shown in Figure 4 from bottom to top.

7) Vector->Processing geometry->Convert lines to polygons...
6) Data analysis->Analysis tools->Create vector objects->Points to path
5) Data Analysis->Analytical Tools->Vector - Select->Extract by Spatial Position
4) Data Analysis->Analysis Tools->Vector Geometry->Rotate
3) Data Analysis->Analysis Tools->Vector Geometry->Oriented minimum bounding box...
2) Vector->Processing geometry->Extract vertices...
1) Source data.

Important: when extracting by spatial position (5), activate the "disjoint" checkbox...

Original solutions...

Translated with www.DeepL.com/Translator (free version)

edited May 24 '21 at 17:10

answered May 21 '21 at 21:07

Cyril Mikhalchenko

4,397
7
14
45

2

Thanks for your answer but "use the translation yourself" is just not a useful contribution. How are users without kyrillic keyboards even supposed to do that? Please add explanations of the steps in English on this English community website. :) – bugmenot123 May 24 '21 at 10:32
@bugmenot123, by the way, does QGIS have the ability to automatically translate tool names and definitions from one language to another on the fly, for example in "properties->" or in the common tools panel? – Cyril Mikhalchenko May 24 '21 at 18:10
I'm sorry, I don't really understand how this solution works and can't reproduce it, information is still too scarce and moving gifs don't help a lot to understand without further information. I'm not sure if this workflow really works for what was asked - obviously, in the case of convex pentagons, it produces something that looks as what the OP asked for: remove vertices with interior angle > 170. But not sure how precise it works. – Babel May 24 '21 at 18:55
I have several questions: 1) option 1: how you come from step 7 to step 8? step 7 gets you lines, how you can use these for Delaunay? 2) How accurate is this solution for different kind of polygon shapes? Does it work for pentagons only? 3) Solution 2: why etracting vertices? step 4: rotate... by what? I'm not really able to reproduce that solution, either. – Babel May 24 '21 at 18:56
@Babel, So 1) for me, step 7 gives points, not lines; 2) OP presented a pentagon envelope in his drawing and my suggestions were designed for such figures; 3) Vertices are necessary to get rid of an unnecessary vertex later on; 4) You rotate the oriented polygon by 90 degrees to remove an unnecessary vertex 5) I wish you could reproduce the example, maybe I should think about more detail in the solution, though. ..
Translated with www.DeepL.com/Translator (free version)
– Cyril Mikhalchenko May 24 '21 at 19:06
1

OK, in that case it means that I probably didn't understand step 6: can't find Menu Data Analysis->Analysis Tools...? Blow lines - you mean explode lines - this here: https://docs.qgis.org/3.16/en/docs/user_manual/processing_algs/qgis/vectorgeometry.html?highlight=explode#explode-lines ? Than you get lines, if you intersect them with the polygon (step 7), you still have lines. How could you use Dealaunay on this? – Babel May 24 '21 at 19:17
Remember that I work with autotranslation; 2) The tool does this -This algorithm takes a lines layer and creates a new one in which each line is replaced by a set of lines representing the segments in the original line. Each line in the resulting layer contains only a start and an end point, with no intermediate nodes between them.

If the input layer consists of CircularStrings or CompoundCurves, the output layer will be of the same type and contain only single curve segments. 3) Data Analysis->Toolbar...

Cyril Mikhalchenko

May 24 '21 at 19:22

Explode lines select the necessary points...Try not to complicate the processes, but rather simplify them... – Cyril Mikhalchenko May 24 '21 at 19:32

1

OK, I got your option 2 solution to work. It seems to be reliable for the kind of shape asked for (pentagon), but not for all kind of shapes. @Alec McKay: you did not state if you only have this kind of shapes or others as well? – Babel May 24 '21 at 19:36

There may be 3, 4, 5, etc., and judging by the picture we are talking about a pentagon, although we can be wrong, which is why I ask OP to provide the original geodata in the form of a link to them! By the way, my first option, can do just fine without voronoi Diagrams and Triangle Delone, but I didn't understand to the end whether we are really only talking about pentagons :-)... – Cyril Mikhalchenko May 24 '21 at 19:39

Babel · Answer 2 · 2021-05-21T19:20:58.597

5

You can use the tool Menu Processing / Toolbox / Orthogonalize and set a Maximum angle tolerance (degrees).

Blue: orginal polygon with vertices (red); orange: output of orthogonalize:

edited May 21 '21 at 19:20

answered May 21 '21 at 19:14

Babel

71,072
14
78
208

1

is there any way of doing this without moving the position of the polygon? i.e. the four vertexes of the orange polygon would remain in the same place as the corresponding four vertexes of the blue polygon – Alec McKay May 21 '21 at 19:46
1

I thought you will answer with an expression solution =) – Taras May 21 '21 at 19:51
@Taras: takes more time... but maybe you have a virtual layer to offer? – Babel May 21 '21 at 19:52
@Alec McKay: unfortunately, this tool offers only limited control - max. tolerenace being the only paramenter to set. So result depends on the original shape. – Babel May 21 '21 at 19:53
To retain remaining original vertices and be able to exactly control which vertices to delete, you must calculate to angle at each vertex. See my other solution for this: it allows maximum control over which vertices to delete, and because of this is a bit more complex. However, it works with whatever polygon-shape. Do you have only pentagons as in your screensot or other shapes as well? – Babel May 24 '21 at 17:49

Taras · Answer 3 · 2023-04-21T15:56:24.167

Here is a solution performed in QGIS 3.18

Let's assume there is a polygon layer 'poly' with a corresponding attribute table, see the image below

Step 1. Apply the "Extract vertices" geoalogorithm

Step 2. Procced with "Delete duplicate geometries"

Step 3. In the Field Calculator create a new integer field

with the following expression (It may look creepy but it is simply an implication of the 'Law of cosines', for more details please see this answer).

with_variable('buffer_size',50,
    with_variable('orignal_layer','poly',
        round(
            if("vertex_index" = minimum("vertex_index",group_by:="id"),
                -- first vertex
                degrees(
                    acos(
                        (
                        length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),maximum("vertex_index",group_by:="id")+1)))^2
                        +
                        length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                        -
                        length(make_line(centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50))),point_n(geometry(get_feature(@orignal_layer,'id',"id")),maximum("vertex_index",group_by:="id")+1)))^2
                        )
                        /
                        (
                        2
                        *
                        length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),maximum("vertex_index",group_by:="id")+1)))
                        *
                        length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))
                        )
                        )
                    )
                    +
                    degrees(
                        acos(
                            (
                            length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            +
                            length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"+2)))^2
                            -
                            length(make_line(point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"+2),centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            )
                            /
                            (
                            2
                            *
                            length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))
                            *
                            length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"+2)))
                            )
                        )
                    ),
                -- last vertex
                if("vertex_index" = maximum("vertex_index",group_by:="id"),
                    degrees(
                        acos(
                            (
                            length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            +
                            length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index")))^2
                            -
                            length(make_line(point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"),centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            )
                            /
                            (
                            2
                            *
                            length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))
                            *
                            length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index")))
                            )
                        )
                    )
                    +
                    degrees(
                        acos(
                            (
                            length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),minimum("vertex_index",group_by:="id")+1)))^2
                            +
                            length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            -
                            length(make_line(centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50))),point_n(geometry(get_feature(@orignal_layer,'id',"id")),minimum("vertex_index",group_by:="id")+1)))^2
                            )
                            /
                            (
                            2
                            *
                            length(make_line($geometry,point_n(geometry(get_feature(@orignal_layer,'id',"id")),minimum("vertex_index",group_by:="id")+1)))
                            *
                            length(make_line($geometry,centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))
                            )
                        )
                    ),
                    -- everything in between
                    degrees(
                        acos(
                            (
                            length(make_line($geometry, point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index")))^2
                            +
                            length(make_line($geometry, centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            -
                            length(make_line(point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"), centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            )
                            /
                            (
                            2
                            *
                            length(make_line($geometry, centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))
                            *
                            length(make_line($geometry, point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index")))
                            )
                        )
                    )
                    +
                    degrees(
                        acos(
                            (
                            length(make_line($geometry, centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            +
                            length(make_line($geometry, point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"+2)))^2
                            -
                            length(make_line(point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"+2), centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))^2
                            )
                            /
                            (
                            2
                            *
                            length(make_line($geometry, centroid(intersection(geometry(get_feature(@orignal_layer,'id',"id")), buffer($geometry,@buffer_size,50)))))
                            *
                            length(make_line($geometry, point_n(geometry(get_feature(@orignal_layer,'id',"id")),"vertex_index"+2)))
                            )
                        )
                    )
                )
            )
        )
    )
)

and get a value of inner angles

Step 4. Use a filter for a point layer with a condition of your own choice. Here "innerangle" <= 150 was used

Step 5. By means of the "Points to path" geoalogirhm with "vertex_index" as the Order expression and "id" as the Path group expression, convert a new set of points into a polyline. Do not forget to tick the Create closed paths(*)

Step 6. And finally use the "Polygonize" and get the final output

To get back the attributes from the original layer one may use for instance the "Join attributes by location", like this

If the following procedure has to be repeated frequently it is highly recommended to convert this workflow into a Graphical Model by means of the Graphical Modeler.

(*) In QGIS versions that do not support this option please use the "Minimum bounding geometry" straight (or beforehand proceed with the "Points to path"(without Create closed paths), that may sufficiently improve the quality of the final output), see image below

Babel · Answer 4 · 2021-05-24T16:24:37.023

My first solution was a "quick and dirty" approach that in this case worked more or less, but did not exactly do what you asked for. This solution allows you to exactly filter for vertices with a certain value for angles and delete them.

Convert your polygon to lines, than explode the line.
On the exploded lines, apply the expression from step no. 5 at this solution (can be found at the section titled C. Create a separate value for each angle of a line or polygon) with field calculator: it calculates the interior angle of the polygon at the end-point of each line (= at every vertex of the polygon). Create a new attribute field called interior_angle with field calculator.
On the polygon line, use extract vertices.
Copy the values of the field interior_angle from step 2 above to the extracted vertices layer. Use this expression with field calculator: attribute (get_feature_by_id ('exploded', $id-1),'interior_angle').
On the extracted vertices layer, use select by expression with this expression: interior_angle>170 (or any other value you like).
Toggle editing and delete the selected vertices.
Run Points to path, select the vertices layer as input and as Order expression set $id.
Convert the created line-layer to polygons using Lines to polygons.

See my example: yellow (original polygons), angles (blue, labeled with their value) and red line: simplified polygon. I deleted all vertices with angle > 270 degrees:

Further simplification, deleting all vertices with angle > 170. For complex geometries, be aware that there can result invalid geomtries (crossing lines) as you can see on the right side (blue box). So you should either use higher values for angle (less simpification), lower values (more simplification, see next screenshot) or afterwards repair geometries:

Even further simplified: deleted all vertices at angles> 90 degrees:

And further simpifying, angles > 40 degrees. Only vertices with extremely small (acute) angles are connected. There is one exception on the left (red arrow): this is the last vertex of the polygon and thus does not have an angle-value as this is calculated based on the azimuth of the next line as well. You could manually remove this point:

Of course, this solution works also the other way round: delete vertices with angle smaller than a certain threshold (or any other criteria based on the calculated angle-value). See here the result with deletion of all vertices with angles < 270 degrees:

Result with keeping only vertices with angles between 150 and 210:

Babel · Answer 5 · 2022-05-06T15:15:07.493

An easy, more effective and interactive version than my other expression-based solution is to calculate the interior angle at each vertex (based on azimuth, as explained in my other solution), than construct interactively and automatically a new polygon driven by a filter-condition based on the angle value. The animated gif below shows the effect when you change the settings.

This can be used to test and achieve different simplification results, like making the polygon more convex (get rid of "bays") or delete extreme acute angles to get rid of extremely small, needle-like spikes (see last screenshots), while still retaining some basic characteristics of the shape.

Different seetings lead to different results - original polygon in orange, modified one in blue. Left: deleting "spikes" with setting angle >50; middle: geting rid of "bays (angle < 180), right: a combination of both:

The conditions for the angle-filter can be complex - not just angle > x and angle < y, but any kind of nested condition: (angle > 50 and angle < 70) or (angle > 290 and angle < 350) etc. This allows detailed control over the resulting shape to find the optimal solution for different requirements.

Animated screenshot, showing the effect of changing the settings for the filter condition:

How to do it:

Extract vertices.
On the extracted vertices, create a new attribute field for interior_angle with this expression:

with_variable (
    'last',
    if (vertex_index = 0, maximum( vertex_index), $id-1),
    with_variable (
    'azimuth1',
    degrees (
        azimuth(
            geometry (get_feature_by_id(@layer,@last)),
            geometry (get_feature_by_id(@layer,$id))
    )),
    with_variable (
        'azimuth2',
        degrees (azimuth(
            geometry (get_feature_by_id(@layer,$id)),
            geometry (get_feature_by_id(@layer,$id+1)))
        ),
    case
        when (@azimuth1 > @azimuth2) and (@azimuth1 > @azimuth2+180) then 540-@azimuth1+@azimuth2
        when (@azimuth1 > @azimuth2) then 180-@azimuth1+@azimuth2
        when (@azimuth1 < @azimuth2) and (@azimuth1+180>@azimuth2) then 180 + @azimuth2-@azimuth1
        when (@azimuth1 < @azimuth2) then @azimuth2-@azimuth1-180 
    end
)))

Now, create a new symbol layer, set it to Geometry generator / Polygon and paste this expression. This will immediately and interactively generate a new polygon with deleted vertices, based on the condition in line 9 - now set to "interior_angle">220. Change this condition and the polygon will immediately adapt to the new settings. When satisfied, run Geometry by expression to create an actual geometry with the same expression:

make_polygon( 
    geom_from_wkt( 
    'linestring(' || 
    array_to_string (
        with_variable (
            'array',
            array_agg( 
                $x || ' ' ||  $y  , 
                filter:="interior_angle">220
            ),
            array_foreach (
                generate_series (0, array_length (@array)),
                array_get (@array, @element)
    ))) ||   ')'
))

Screenshot: original polygon in orange, automatically generated polygon with Geometry generator in blue. The expression above is modified so that only vertices are connected with angles from 50 to 70 and from 290 to 350 degrees. When you change these values, the blue polygon will automatically change accordingly:

Seems like this topic made you really hot – Taras May 26 '21 at 06:57 — Taras, May 26 '21 at 06:57

Simplifying polygon by inner angle in QGIS

5 Answers5