4

I need to buffer a polygon with a different distance in the x and y directions. I should add that my polygon has the following properties:

  • closed (obviously)
  • simple (no edge crossing, no more than 2 edges at any given vertex)
  • potentially concave
  • may or may not have hole(s) that may or may not be concave (this being said, 90% of the time there won't be any hole so I'm OK to leave this out)

I understand the buffer of a polygon is basically the Minkowski sum of that polygon and a circle of radius r (r = buffer distance), so I thought my problem may just be computing the Minkowski sum of a polygon with an ellipse.
I have read a lot on the subject of Minkowski sum here, here and there and found some algorithms easy enough to implement in Python (see below) but these are usually for convex polygons which is not my case.
I even set out to decipher CGAL's Minkowski_sum_by_reduced_convolution code but it is way too cryptic for me (I am not familiar with C).

Can you point me to a Python version or anything actually readable (pseudo-code included) of the above or similar algorithm?

For reference only (this is not what I'm trying to implement):
minkowski

  • What about this approach : Squishing the polygons on one axis, then using a regular circle-based buffer, then un-squishing the result ? Might be a bit convoluted way of doing this, but to me it should solve the problem. – GHRF Jul 23 '18 at 8:37
  • What do you mean by squishing / un-squishing ? – YeO Jul 23 '18 at 10:05
  • What I mean is transforming them so that what used to be a square becomes a rectangle (eg. dividing the y axis by some factor), then buffering, then doing the inverse transformation (multiplying the y axis by the same factor). – GHRF Jul 23 '18 at 11:27
  • Squishing my polygon will alter its form as it won't buffer in one direction but stretch or compress it so angles will change. This may be a good approximation for simple cases. – YeO Jul 24 '18 at 18:03
  • Isn't buffering with a sort of stretch over one axis precisely what you want to do ? Here's a visualisation of what it would look like : imgur.com/a/fziNQDD – GHRF Jul 25 '18 at 8:21
0

I kind of gave up on Minkowski's sum as it is too difficult for me to understand C/C++ code. As I was browsing one more time the excellent documentation of CGAL for 2D Minkowski Sum, I realised offsetting convex polygons or triangles should be easy enough.

So I resorted to triangulate my polygon using a readily available algorithm ('3d:tessellate' in QGIS for instance) and use this simple routine that offsets along the x-axis only:

def offset_x(geom, offset, epsilon):
    """
    Offset a convex polygon given as a QgsGeometry along the x axis
    Polygon should be left-handed (i.e. vertices given in counter-clockwise
    order)
    """
    nodes = list(geom.vertices())
    new_nodes = []
    if is_clockwise(nodes):
        nodes.reverse()
    for i in range(len(nodes) - 1):
        a, b = nodes[i], nodes[i + 1]
        ax, ay, bx, by = a.x(), a.y(), b.x(), b.y()
        if abs(ay - by) < epsilon: # we are parallel to x-axis, so we just extend our edge
            off = -offset if ax > bx else offset
            new_nodes = new_nodes + [QgsPointXY(ax - off, ay),
                                     QgsPointXY(bx + off, by)]
        else: # in all other cases, we offset right or left, depending on the orientation of the edge (up is right, down is left)
            off = -offset if ay > by else offset
            new_nodes = new_nodes + [QgsPointXY(ax + off, ay),
                                     QgsPointXY(bx + off, by)]
    no_dupes = list(dict.fromkeys(new_nodes)) # eliminate duplicates, whilst preserving order
    return QgsGeometry.fromPolygonXY([no_dupes])

So given a list of vertices in counter-clockwise order, going up, we offset right (positive offset) and going down, we offset left (negative offset).

It is just a matter of rotating my polygon prior to using this routine and rotate it back to get the offset in any direction.

Inset (negative offset/buffer, or reducing the polygon instead of extending it) will be a little more tricky but it should be doable.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.