Как нарисовать произвольный неправильный многоугольник с n сторонами?

Question

Я пытаюсь найти алгоритм рисования простого (не допускается пересечение линий) неправильного многоугольника.

Количество сторон должно быть задано пользователем, n>3.

Вот начальный код, который рисует только сложный многоугольник (линии пересекаются):

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/

Я понятия не имею, как определить следующая точка для соединительной линии , чтобы она не пересекала никакую другую линию.

Кроме того, последняя точка должна закрывать многоугольник.

Вот примертого, как может выглядеть один из полученных многоугольников:

Редактировать: Сегодня я подумал, что одним из возможных алгоритмов будет расположение правильных точек многоугольника (например, в виде прямоугольника), а затем переместите их в случайном порядке в xy-направлениях, проверяя, чтобы сгенерированные линии не обрезались.

Answer 1

Я перенес это решение на Javascript 1 к 1. Код не выглядит оптимальным, но выдает случайный выпуклый (но все же неправильный) многоугольник.

//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

Если оно не должно быть случайным, вот быстрый нерегулярный n-точечный многоугольник:

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

Вы можете сгенерировать случайные точки, а затем соединить их с приблизительным туром коммивояжера. Любой тур, который нельзя улучшить ходами 2-opt , не будет пересекать края.