How to handle polyline offset with variable width ("buffer")?

Question

My problem statement:

I have a polyline, and I want to do variable width offset along the points, in just one direction. How can I do it? For the polyline, I just need to support straight lines, no need to support curves or arcs.

The polyline can be closed or open, and the offset is in only one direction-- for the sake of argument, let's just say that it's in the Left Hand Side direction.

The above image almost encapsulates what I want to do; the only thing is, it is uniform offset throughout the polylines, whereby I want variable offset.

The problem is a lot more trickier than it first seems. There are a few libraries that not quite do. Let's go through them one by one.

Clipper

Clipper can handle polygon buffer, which means that the offsetting lines are created in both directions and finally a polygon is form around the line. So it's not suiting my needs. Furthermore it doesn't handle variable buffering.

There were some discussions on this on the forum involving the Clippers developers, but unfortunately nothing came out.

NetTopologySuite

NetTopologySuite has a VariableBuffer class, which can handle variable offset. But unfortunately NetTopologySuite can only handle polygon buffering ( whereby you convert a line into a polygon enclousing the line), and not polyline offsetting ( where by the polyline is offset in a single direction).

Also, it seems that with the above method NetTopologySuite will "blow up" the polygon in both direction, and one needs to set the BufferParameters.IsSingleSided=true in order to have a single sided polygon offset, but it's quite unclear how to use this in conjunction with VariableBuffer.

Cavalier contours

Cavalier countours, unlike the majority of the library out there, can do polyline offsetting ( which is what I want) in one direction only so that no polygon is formed. This is what I want, but unfortunately, it can't do variable width offsetting.

What about adapting current libraries to suit my needs?

There seems to be no trivial way of doing just this. Any ideas how this can be done?

Any solutions built on top of libraries in C#, C++ or C are welcomed.

Answer 1

Indeed, the problem is more complicated with a variable offset. In the case with a single offset, the distance of a point p to the polyline is defined as the distance of the closest point of the polyline to p (see for example pointValidForOffset in https://github.com/jbuckmccready/CavalierContours/blob/master/include/cavc/polylineoffset.hpp )

The generalization to variable offset is not obvious.

A simple solution, in case of a simple polyline (no curves) is : Let F be the initial polyline.

• draw G, the polyline far from the variable offset (see detail after)
• connect the first point of F with the first point of G (creation of a segment A)
• connect the last point of F with the last point of G (creation of a segment B)
• we obtain a closed polygon P
• To manage the intersections, deletion of loops: calculate the union of P with itself, then keep the contour that is not F, nor the segments A and B.

To draw G, the polyline far from the variable offset : This code works if you put the code in http://paperjs.org/ "Sketch" Here is the result :

/* Computes a polyline with a fixed offset (red) 
 * and another with a variable size offset (green)
 */
    const points = [
        new Point(30, 40),
        new Point(100, 80),
        new Point(200, 60),
        new Point(250, 50),
        new Point(300, 70),
        new Point(350, 90),
        new Point(400, 60),
        new Point(450, 50),
        new Point(500, 70),
        new Point(550, 90),
        ];
    
    let poly1 = new Path();
    poly1.strokeColor = 'black';
    points.forEach(p =>  poly1.add(p));
    
    const fixOffs = 5;
    const offsets = [
        10, 20, 30, 20, 10, 10, 20, 20, 30, 30];
    
    let fix = [];
    let variable = [];
    
    const size = points.length;
    for(let i=0; i<size; ++i){
        let tangent;
        if(i===0){ // if first point
            tangent = points[1] - points[0];
        }else if(i+1===size){ // if last point
            tangent = points[i] - points[i-1];
        }else{ // mean of segment before and segment after point i
            tangent = (points[i] - points[i-1]) * 0.5 +
                      (points[i+1] - points[i]) * 0.5;
        }
        let normal = new Point(-tangent.y, tangent.x); // perpendicular vector
        normal = normal / normal.length; // normalize
        fix.push(points[i] + normal * fixOffs);
        variable.push(points[i] + normal * offsets[i]);
    }
    
    let polyFix = new Path();
    polyFix.strokeColor = 'red';
    fix.forEach(p =>  polyFix.add(p));
    
    let polyVar = new Path();
    polyVar.strokeColor = 'green';
    variable.forEach(p =>  polyVar.add(p));

Answer 2

A standard offsetting algorithm would work as follows:

1. Consider the line segments to be full lines. Offset all of them in the chosen direction by the given amount.
2. Find the intersection of each pair of neighboring lines. That will be the new positions of the vertices.
3. Check for vanishing segments and remove the respective vertices.

Note that Jerome's code offsets points, not segments. So you observed correctly that it fails to keep a fixed distance for very sharp angles. It also ignores the third step completely.

Now the difficult part is how to include a variable offset into this? If you had offset weights for each segment, it would be straight forward to integrate. But in your question you state that you have offset weights per vertex. Simply adding a 4th step that would move around the obtained vertices would invalidate the results of step 3. So I would rather search for a way to integrate the variable offset to the first step. In fact correct representation would require not only to offset the lines, but also rotating them. They would of course be no more parallel, but in my opinion this would represent the variable vertex offset nature the best. Again, if you want to reduce such difficulties, think about using per-segment weights which makes the whole problem much easier, since a weighted line offset can be easily integrated into step 1.

Update

I fixed and extended the example from Jerome's answer. @Jerome, thank you for introducing me to paper.js and for the initial inspiration. In my version I use variable widths per-segment, as a ratio of the fixed offset. Try it out here.

//the paper.js is really stupid: the search is hidden by the execution controls
//and once I rename this class to "Line" which would be more appropriate
//(but my original intent was indeed a Halfline), it throws errors, //so I keep the slightly misleading name "Halfline"
class Halfline {
    constructor(p, r)
    {
        const tangent = r - p;
        this.p = p;
        this.r = r;
        //implicit line equation
        this.a = -tangent.y;
        this.b = tangent.x;
        this.c = p.x * this.a + p.y * this.b;
        //I didn't normalize a and b, so here a unit normal
        this.n = new Point(this.a, this.b);
        this.n /= this.n.length;
    }
    //offset the line by t in the direction of its normal
    offset(t) {
        return new Halfline(this.p + this.n * t, this.r + this.n * t)
    }
    //line intersection (infinite lines)
    intersect(other) {
        const det = this.a * other.b - other.a * this.b;
        
        if (Math.abs(det) < 1e-5) //parallel
            return undefined;
        
        const x = (other.b * this.c - this.b * other.c) / det;
        const y = (this.a * other.c - other.a * this.c) / det;
        return new Point(x, y);
    }
}

//look at this great tutorial for details on helper functions: 
//https://algorithmtutor.com/Computational-Geometry/Check-if-two-Halfline-segment-intersect/
function fixOverlaps(polyline) {
    function on_segment(p1, p2, p) {
        return Math.min(p1.x, p2.x) <= p.x
               && p.x <= Math.max(p1.x, p2.x)
               && Math.min(p1.y, p2.y) <= p.y
               && p.y <= Math.max(p1.y, p2.y);
    }
    
    function cross_product(p1, p2) {
        return p1.x * p2.y - p2.x * p1.y;
    }
    
    function direction(p1, p2, p3) {
        return cross_product(p3 - p1, p2 - p1);
    }
    
    function segmentsIntersect(p1, p2, p3, p4) {
        d1 = direction(p3, p4, p1);
        d2 = direction(p3, p4, p2);
        d3 = direction(p1, p2, p3);
        d4 = direction(p1, p2, p4);

        return ( (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0))
                 && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
            || (d1 == 0 && on_segment(p3, p4, p1))
            || (d2 == 0 && on_segment(p3, p4, p2))
            || (d3 == 0 && on_segment(p1, p2, p3))
            || (d4 == 0 && on_segment(p1, p2, p4)) );
    }
    //search for self-intersections
        let intersectionsFound = true;
    while (intersectionsFound)
    {
        let result = [polyline[0]];
        for(let i = 1; i < polyline.length; ++i)
        {
            let anyIntersection = false;
            for(let j = i + 2; j < polyline.length; ++j)
                if (segmentsIntersect(polyline[i-1], polyline[i], polyline[j-1], polyline[j]))
                {
                    const s = new Halfline(polyline[i-1], polyline[i]);
                    const t = new Halfline(polyline[j-1], polyline[j]);
                    result.push(s.intersect(t))
                    anyIntersection = true;
                    i = j;
                    break;
                }
            result.push(polyline[i])
        }
        intersectionsFound = polyline.length > result.length;
        polyline = result;
    }
    
    return polyline;
}

const points = [
        new Point(30, 40),
        new Point(100, 200),
        new Point(200, 60),
        new Point(250, 50),
        new Point(300, 70),
        new Point(350, 250),
        new Point(400, 60),
        new Point(450, 50),
        new Point(500, 70),
        new Point(550, 90),
        ];
    
    let poly1 = new Path();
    poly1.strokeColor = 'black';
    points.forEach(p => poly1.add(p));
    
    const fixOffs = 10;
    const offsets = [1, 2, 3, 2, 1, 0.5, 2.5, 2, 3, 1].map(x => x * fixOffs);
    
    let fix = [];
    let variable = [];
    
    const size = points.length;
    for(let i = 0; i < size; ++i){
        let normal;
        if(i == 0 || i == size - 1) { // first or last
            const tangent = i == 0 ? points[i + 1] - points[i] : points[i] - points[i - 1];
            const normal = new Point(-tangent.y, tangent.x) / tangent.length;
            fix.push(points[i] + normal * fixOffs);
            variable.push(points[i] + normal * offsets[i]);
        } else {
            const prevSegment = new Halfline(points[i - 1], points[i]);
            const nextSegment = new Halfline(points[i], points[i + 1]);
            //CONSTANT
            const newConstVertex = prevSegment.offset(fixOffs).intersect(nextSegment.offset(fixOffs));
            fix.push(newConstVertex || (points[i] + prevSegment.n * fixOffs));
            //VARIABLE
            const newVarVertex = prevSegment.offset(offsets[i]).intersect(nextSegment.offset(offsets[i + 1]));
            variable.push(newVarVertex || (points[i] + prevSegment.n * offsets[i]));
        }
    }

    //Resolve vanishing segments
    const finalFix = fixOverlaps(fix);
    const finalVar = fixOverlaps(variable);
    
    let polyFix = new Path();
    polyFix.strokeColor = 'red';
    finalFix.forEach(p => polyFix.add(p));/**/

    let polyVar = new Path();
    polyVar.strokeColor = 'green';
    finalVar.forEach(p => polyVar.add(p));/**/

Note that it still does not handle all special cases. For example the corners of a non-closed polyline will produce strange shapes once the offset grows too large. Also note that the last two segments are parallel, an interesting choice of Jerome and good for debugging. I assigned them a different offset which forces the segments to give up their parallelity.

Answer 3

Offsetting a polyline can be done as follows:

1. First construct a rectangle containing initial polyline and extended in all direction on the maximum offset value.
2. Subdivide the rectangle on small pixels (with pixel size depending on the precision you need).
3. Compute the distance from each pixel center to your polyline considering additional weight of segments requiring larger offset. The distance has to be with sign: positive from one side of polyline and negative from another. 2D raster with distances in each pixel is named sometimes distance map.
4. Find the isoline of the distance field, which will give you the offset polyline.

For example, this C++ library provides most of the steps here: https://github.com/MeshRUs/MeshLib The only current limitation is that it computes distance map with signed distances only for closed polylines, but it can be solved in several ways (for example by extending the initial polyline beyond the containing rectangle).