7

I am working on a project to transform polygons given in a pre-defined precision to a lesser precision, which I think is equivalent to snap them to a fixed spacing grid.

For example, in the example below, I have a polygon in yellow, I need to snap its vertices to the anchors of a grid (in green). I have tried to load my data to QGIS and use the snap to grid feature, which generates transformed polygon (in cyan). But you can see the transformed polygon has some large distortion, especially in the lower right corner. For this example, I would think the polygon (in red) in the second image is probably a more similar transformed version to the original polygon.

Is there any algorithm that works on this kind of problem, to snap a geometry to grid anchors with minimum distortion? Vertices of the transformed polygon do not need to be the closest to their correspondence on the original polygon. Adding or removing vertices are also allowed, but the resulting shape should be as similar as possible to the original polygon, and the resulting polygon vertices must be on the grid anchors.

I have not found a good metric to measure the similarity, but I am thinking the angle at vertices with two long sides shall be with minimum change. It sounds even like an optimization problem to me.

enter image description here

enter image description here

Babel
  • 71,072
  • 14
  • 78
  • 208
Gbuntu
  • 171
  • 4
  • With that grid, could you draw by hand the result that would make you happy? – user30184 Jan 20 '20 at 22:05
  • @user30184, thanks for your reply. I have added another image with the drawn polygon (in red) in the second image. I would think it is a more similar one to the original polygon. As the angle change at the lower left corner is smaller than the first one, also the area change is smaller wto the original polygon. I have not figured out an exact metric to define similarity. As my first thought is that the angle change should be smaller for major vertices (vertices with two long sides), and long sides (above a certain threshold) should have smaller length changes. – Gbuntu Jan 20 '20 at 22:55

1 Answers1

2

You can create a new polygon by snapping each vertex of your original polygon to the nearest anchor point of the grid. For that, you can use the new overlay_nearest expression, available since QGIS 3.16. So each vertex of your polygon is shifte to the nearest anchor point of the grid.

  1. Create a point layer anchor (blue dots on the screenshot) representing the anchor points of the grid - if the grid is a polygon create gridlines using Menu Vector / Geometry Tools / Polygons to lines, than create anchor points with Menu Vector / Analysis Tools / Line intersections.

  2. Create a point layer vertices (green dots), representing the vertices of the polygon you want to simplify using Menu Vector / Geometry Tools / Extract vertices.

  3. Snap the vertices to the nearest anchor and create a new point layer shifted using Menu Processing / Toolbox /Geometry by expression. Use vertices as input and set output geometry type to point. Paste this expression as Geometry expression:

array_first (
    overlay_nearest( 
        'anchor', 
        $geometry
    )
)

  1. Create a line layer boundary Use Menu Processing / Toolbox / Points to path to connect the shifted vertices with a line. Select shifted (from 3) as input, check the box close path and for order field choose vertex_index (this field is created when you extrect the vertices in step 2).

  2. Use Menu Vector / Geometry Tools / Lines to polygons to create a polygon shifted_polygon with the line layer boundary (from 4) as input.

See the shifted polygon with red outline:

QGIS shift polygon, snap vertices to grid using expression

Babel
  • 71,072
  • 14
  • 78
  • 208