如何绘制具有n个边的任意不规则多边形? [英] How to draw an arbitrary irregular polygon with n sides?

问题描述

我正在尝试找到一种算法，用于绘制简单的(不允许线相交)不规则多边形.

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

边数应由用户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/

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:

我今天认为，一种可行的算法是将多边形点规则排列(例如，以矩形的形式)，然后在xy方向上将它们重新定位为随机量，同时检查所生成的线是否被切割.

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.

推荐答案

我移植了此解决方案到Javascript 1到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>

这篇关于如何绘制具有n个边的任意不规则多边形?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！