How to draw an arbitrary irregular polygon with n sides?

Question

I am trying to find an algorithm of how to draw a simple (no lines are allowed to intersect), irregular polygon.

The number of sides should be defined by the user, n>3.

Here is an intial code which only draws a complex polygon (lines intersect):

var ctx = document.getElementById('drawpolygon').getContext('2d');

var sides = 10;

ctx.fillStyle = '#f00';
ctx.beginPath();
ctx.moveTo(0, 0);

for(var i=0;i<sides;i++)
{
    var x = getRandomInt(0, 100);
    var y = getRandomInt(0, 100);
    ctx.lineTo(x, y);
}
ctx.closePath();
ctx.fill();

// https://stackoverflow.com/a/1527820/1066234
function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

JSFiddle: https://jsfiddle.net/kai_noack/op2La1jy/6/

I do not have any idea how to determine the next point for the connecting line, so that it does not cut any other line.

Further, the last point must close the polygon.

Here is an example of how one of the resulting polygons could look like:

Edit: I thought today that one possible algorithm would be to arrange the polygon points regular (for instance as an rectangle) and then reposition them in x-y-directions to a random amount, while checking that the generated lines are not cut.

This study can help: http://cglab.ca/~sander/misc/ConvexGeneration/convex.html . It tackles only convex polygons though. Without convex requirement it's probably even easier — Andrey, Mar 26 '19 at 15:28
Does this help? https://stackoverflow.com/questions/14263284/create-non-intersecting-polygon-passing-through-all-given-points — georg, Mar 26 '19 at 15:54
There was the same question but in matlab: https://stackoverflow.com/questions/8997099/algorithm-to-generate-random-2d-polygon — Andrey, Mar 26 '19 at 16:26
Possible duplicate of [Create non-intersecting polygon passing through all given points](https://stackoverflow.com/questions/14263284/create-non-intersecting-polygon-passing-through-all-given-points) — Prune, Mar 26 '19 at 17:07

Andrey · Answer 1 · 2019-03-26T16:23:28.350

I ported this solution to Javascript 1 to 1. Code doesn't look optimal but produces random convex(but still irregular) polygon.

//shuffle array in place
function shuffle(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
}

/** Based on Sander Verdonschot java implementation **/

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y
  }
}

function generateRandomNumbersArray(len) {
  const result = new Array(len);
  for (let i = 0; i < len; ++i) {
    result[i] = Math.random();
  }
  return result;
}

function generateRandomConvexPolygon(vertexNumber) {
  const xPool = generateRandomNumbersArray(vertexNumber);
  const yPool = generateRandomNumbersArray(vertexNumber);

//   debugger;
  xPool.sort();
  yPool.sort();

  const minX = xPool[0];
  const maxX = xPool[xPool.length - 1];
  const minY = yPool[0];
  const maxY = yPool[yPool.length - 1];

  const xVec = []
  const yVec = [];

  let lastTop = minX;
  let lastBot = minX;

  xPool.forEach(x => {
    if (Math.random() >= 0.5) {
      xVec.push(x - lastTop);
      lastTop = x;
    } else {
      xVec.push(lastBot - x);
      lastBot = x;
    }
  });

  xVec.push(maxX - lastTop);
  xVec.push(lastBot - maxX);

  let lastLeft = minY;
  let lastRight = minY;

  yPool.forEach(y => {
    if (Math.random() >= 0.5) {
      yVec.push(y - lastLeft);
      lastLeft = y;
    } else {
      yVec.push(lastRight - y);
      lastRight = y;
    }
  });

  yVec.push(maxY - lastLeft);
  yVec.push(lastRight - maxY);

  shuffle(yVec);
  
  vectors = [];
  for (let i = 0; i < vertexNumber; ++i) {
    vectors.push(new Point(xVec[i], yVec[i]));
  }
  
  vectors.sort((v1, v2) => {
    if (Math.atan2(v1.y, v1.x) > Math.atan2(v2.y, v2.x)) {
      return 1;
    } else {
      return -1;
    }
  });
  
  let x = 0, y = 0;
  let minPolygonX = 0;
  let minPolygonY = 0;
  let points = [];
  
  for (let i = 0; i < vertexNumber; ++i) {
    points.push(new Point(x, y));
    x += vectors[i].x;
    y += vectors[i].y;
    
    minPolygonX = Math.min(minPolygonX, x);
    minPolygonY = Math.min(minPolygonY, y);
  }
  
          // Move the polygon to the original min and max coordinates
  let xShift = minX - minPolygonX;
  let yShift = minY - minPolygonY;

  for (let i = 0; i < vertexNumber; i++) {
    const p = points[i];
    points[i] = new Point(p.x + xShift, p.y + yShift);
  }
  
  return points;
}


function draw() {
  const vertices = 10;
  const _points = generateRandomConvexPolygon(vertices);
  
  //apply scale
  const points = _points.map(p => new Point(p.x * 300, p.y * 300));

  const ctx = document.getElementById('drawpolygon').getContext('2d');


  ctx.fillStyle = '#f00';
  ctx.beginPath();
  ctx.moveTo(points[0].x, points[0].y);

  for(let i = 1; i < vertices ; ++i)
  {
    let x = points[i].x;
    let y = points[i].y;
    ctx.lineTo(x, y);
  }
  ctx.closePath();
  ctx.fill();
}

draw();

<canvas id="drawpolygon"></canvas>

Thanks a lot! This is the solution for **convex polygons**. Now the creation of **concave polygons** (see my example graphic) is only missing. I guess this is the answer: https://stackoverflow.com/a/47410079/1066234 (in Python). — Avatar, Mar 27 '19 at 05:37

score 0 · Answer 2 · answered Mar 26 '19 at 15:42

0

You could generate random points and then connect them with an approximate traveling salesman tour. Any tour that cannot be improved by 2-opt moves will not have edge crossings.

answered Mar 26 '19 at 15:42

David Eisenstat

64,237
7
60
120

score 0 · Answer 3 · answered Mar 26 '19 at 19:27

If it doesn't need to be random, here's a fast irregular n-point polygon:

Points are:
(0,0)
((i mod 2)+1, i) for 0 <= i <= n-2

Lines are between (0,0) and the two extreme points from the second row, as well as points generated by adjacent values of i.

How to draw an arbitrary irregular polygon with n sides?

3 Answers3

Linked