How to draw an arbitrary irregular polygon with n

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.

Answer 1

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>

Answer 2

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.

Answer 3

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.