Scale a polygon so the edges match up

Question

I'm working on a project using a JavaScript canvas and need to be able to snap the cursor to a certain distance from a polygon. I can already snap to the polygon itself, but I need to have the cursor farther away.

As far as I can tell the best way to go about this is to scale the polygon and snap to that, but when I scale the polygon the distance between the edges of the old polygon and the edges of the new polygon don't always match up.

here is an example of the problem:

Edit: The grey represents the original polygon, the red is what I am getting if I scale the polygon normally, and the green is what I'm trying to accomplish

I've already tried translating the polygon to the origin and multiplying by a scale factor, but can't seem to scale each edge by a specific distance.

Answer 1

I made a jsFiddle that for a given polygon, calculates an outer polygon that I hope meets your requirement. I have put the math behind it in this pdf document.

Update: code has been made to deal with vertical lines.

function Vector2(x, y)
{
    this.x = x;
    this.y = y;
}

function straight_skeleton(poly, spacing)
{
    // http://stackoverflow.com/a/11970006/796832
    // Accompanying Fiddle: http://jsfiddle.net/vqKvM/35/

    var resulting_path = [];
    var N = poly.length;
    var mi, mi1, li, li1, ri, ri1, si, si1, Xi1, Yi1;
    for(var i = 0; i < N; i++)
    {
        mi = (poly[(i+1) % N].y - poly[i].y)/(poly[(i+1) % N].x - poly[i].x);
        mi1 = (poly[(i+2) % N].y - poly[(i+1) % N].y)/(poly[(i+2) % N].x - poly[(i+1) % N].x);
        li = Math.sqrt((poly[(i+1) % N].x - poly[i].x)*(poly[(i+1) % N].x - poly[i].x)+(poly[(i+1) % N].y - poly[i].y)*(poly[(i+1) % N].y - poly[i].y));
        li1 = Math.sqrt((poly[(i+2) % N].x - poly[(i+1) % N].x)*(poly[(i+2) % N].x - poly[(i+1) % N].x)+(poly[(i+2) % N].y - poly[(i+1) % N].y)*(poly[(i+2) % N].y - poly[(i+1) % N].y));
        ri = poly[i].x+spacing*(poly[(i+1) % N].y - poly[i].y)/li;
        ri1 = poly[(i+1) % N].x+spacing*(poly[(i+2) % N].y - poly[(i+1) % N].y)/li1;
        si = poly[i].y-spacing*(poly[(i+1) % N].x - poly[i].x)/li;
        si1 = poly[(i+1) % N].y-spacing*(poly[(i+2) % N].x - poly[(i+1) % N].x)/li1;
        Xi1 = (mi1*ri1-mi*ri+si-si1)/(mi1-mi);
        Yi1 = (mi*mi1*(ri1-ri)+mi1*si-mi*si1)/(mi1-mi);
        // Correction for vertical lines
        if(poly[(i+1) % N].x - poly[i % N].x==0)
        {
            Xi1 = poly[(i+1) % N].x + spacing*(poly[(i+1) % N].y - poly[i % N].y)/Math.abs(poly[(i+1) % N].y - poly[i % N].y);
            Yi1 = mi1*Xi1 - mi1*ri1 + si1;
        }
        if(poly[(i+2) % N].x - poly[(i+1) % N].x==0 )
        {
            Xi1 = poly[(i+2) % N].x + spacing*(poly[(i+2) % N].y - poly[(i+1) % N].y)/Math.abs(poly[(i+2) % N].y - poly[(i+1) % N].y);
            Yi1 = mi*Xi1 - mi*ri + si;
        }

        //console.log("mi:", mi, "mi1:", mi1, "li:", li, "li1:", li1);
        //console.log("ri:", ri, "ri1:", ri1, "si:", si, "si1:", si1, "Xi1:", Xi1, "Yi1:", Yi1);

        resulting_path.push({
            x: Xi1,
            y: Yi1
        });
    }

    return resulting_path;
}


var canvas = document.getElementById("Canvas");
var ctx = canvas.getContext("2d");

var poly = [
    new Vector2(150, 170),
    new Vector2(400, 120),
    new Vector2(200, 270),
    new Vector2(350, 400),
    new Vector2(210, 470)
];

draw(poly);
draw(straight_skeleton(poly, 10));

function draw(p) {
    ctx.beginPath();
    ctx.moveTo(p[0].x, p[0].y);
    for(var i = 1; i < p.length; i++)
    {
        ctx.lineTo(p[i].x, p[i].y);
    }
    ctx.strokeStyle = "#000000";
    ctx.closePath();
    ctx.stroke();
}

A polygon is put into an array of point objects.

The function draw(p) draws the polygon p on the canvas.

The given polygon is in array poly, the outer in the array poly.

spacing is the distance between the polygons (as along the arrows in your green diagram)

---

Following Angus Johnson's comment, I have produced some more fiddles to show the issues he raises. This problem is much more difficult problem than I first thought.

• http://jsfiddle.net/vqKvM/5/
• http://jsfiddle.net/vqKvM/6/
• http://jsfiddle.net/vqKvM/7/

Answer 2

I made a javascript port of Clipper and with it you can do the scaling in the way you want.

This is an example of inflating polygon:

Check the LIVE DEMO of Javascript Clipper.

and get the clipper.js file from https://sourceforge.net/projects/jsclipper/ .

Full code example of how to offset polygons and and draw them on html5 canvas.

The opposite (deflating) is also possible, if needed:

Answer 3

ISTM that what you're after is a polygon offsetting algorithm or library.
See An algorithm for inflating/deflating (offsetting, buffering) polygons

Answer 4

One way is to find the distance between every edge of the polygon and the cursor point, and keep the smallest.

To compute the distance between a point and a line segment, project the point onto the supporting line; if the projection falls between the endpoints, the solution is the point-to-line distance; otherwise, the solution is the distance to the closest endpoint.

This is easily computed using vector calculus.

Answer 5

I can offer a solution using JSTS library (JavaScript port of JTS). The library has methods for inflating/deflating (offsetting) of polygons.

You can set the cap and join styles if you want to get the inflated polygon with different type of edges. The only thing you have to do is to convert you polygon coordinates to a JSTS coordinate which is really simple:

function vectorCoordinates2JTS (polygon) { var coordinates = []; for (var i = 0; i < polygon.length; i++) { coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y)); } return coordinates; }

Once you have converted the coordinates you can inflate your polygon:

function inflatePolygon(poly, spacing) {
  var geoInput = vectorCoordinates2JTS(poly);
  geoInput.push(geoInput[0]);

  var geometryFactory = new jsts.geom.GeometryFactory();

  var shell = geometryFactory.createPolygon(geoInput);
  var polygon = shell.buffer(spacing);
  //try with different cap style
  //var polygon = shell.buffer(spacing, jsts.operation.buffer.BufferParameters.CAP_FLAT);

  var inflatedCoordinates = [];
  var oCoordinates;
  oCoordinates = polygon.shell.points.coordinates;

  for (i = 0; i < oCoordinates.length; i++) {
    var oItem;
    oItem = oCoordinates[i];
    inflatedCoordinates.push(new Vector2(Math.ceil(oItem.x), Math.ceil(oItem.y)));
  }
  return inflatedCoordinates;
}

With code I've posted on jsFiddle you will get something like this:

Additional info: I usually use this type of inflating/deflating (a little changed) for setting boundaries with radius on polygons that are drawn on a map (with Leaflet or Google maps). You just convert lat,lng pairs to JSTS coordinates and everything else is the same. Example: