业务实践篇4：不规则多边形的内部获取随机点

内容：描述一种在多边形内部随机取点的算法，通过对多边形划分三角形，使用面积权重获得随机的三角形，最后在三角形中随机取点。

绘制一个不规则多边形区域

<canvas id="myId" width={500} height={500}></canvas>

const canvas: any = document.querySelector('#myId')
if (canvas) {
  const ctx = canvas.getContext('2d')
  if (ctx) {
    ctx.fillStyle = '#fff';
    ctx.strokeStyle = '#000';
    ctx.fillRect(0, 0, 500, 500);
    ctx.beginPath();
    ctx.moveTo(...points[0])
    for (let i = 1; i < points.length; i++) {
      ctx.lineTo(...points[i])
    }
    ctx.closePath()
    ctx.stroke()
  }
}

划分三角形

这里选用了www.npmjs.com/package/ear… 来进行三角形的划分，同时我们计算三角形的面积和占总面积的比例。

const triangles = splitPolygon(points)
const ratioList = [];
const totalArea = triangles.reduce(
  (sum, triangle) => sum + getTriangleArea(triangle),
  0,
);
ctx.strokeStyle = 'green';
ctx.font = "16px Georgia";
for (let i = 0; i < triangles.length; i++) {
  ctx.moveTo(...triangles[i][0])
  ctx.lineTo(...triangles[i][1])
  ctx.lineTo(...triangles[i][2])
  ctx.closePath()
  ctx.stroke()
  const area = getTriangleArea(triangles[i])
  const ratio = Number((area / totalArea).toFixed(2))
  ratioList.push(ratio);
  ctx.strokeText(`${area} / ${ratio}`, (triangles[i][0][0] + triangles[i][1][0] + triangles[i][2][0]) / 3 - 20, (triangles[i][0][1] + triangles[i][1][1] + triangles[i][2][1]) / 3)
}

// 划分三角形
function splitPolygon(points: IPoint[]) {
  const data: any = points.flat(Infinity);
  const trianglesPoints: any = earcut(data);
  const triangles = [];
  const dimensions = 2;
  const len = 3;
  for (let i = 0; i < trianglesPoints.length; i += len) {
    triangles.push(
      trianglesPoints
      .slice(i, i + len)
      .map((idx: number) => [
        data[idx * dimensions],
        data[idx * dimensions + 1],
      ]),
    );
  }
  return triangles;
}

// 计算三角形面积
function getTriangleArea(triangle: ITriangle) {
  const [a, b, c] = triangle;
  return 0.5 * ((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]));
}

选取随机三角形

这里的选取要考虑到三角形面积的不同权重，比如比例为60%的面积有60%的机会选中。

首先随机数的选取在0-1之间，面积的比例也在0-1之间，只需要做一一对应即可。这里可以理解为将随机数划分对应的若干个相连的区间，分别对应不同的三角形面积比例，判断选中的随机数出现在哪个区间，即选择对应的三角形。

本文采取计算是用随机数依次减去前面n个区间的值知道为负数时，则能判断落在了第n个三角形。

function selectRandomTriangle(ratioList: number[], triangles: any[]) {
        const rnd = Math.random();
        let i = 0;
        let result = rnd - ratioList[i];
        while (result > 0) {
            i += 1;
            result = result - ratioList[i];
        }
        return triangles[i];
    }

三角形内随机取点

在随机选中的三角形中随机选点。

function calcRandomPoint(triangle: ITriangle) {
  let wb = Math.random();
  let wc = Math.random();

  // 点有可能落到外面，权值反转
  if (wb + wc > 1) {
    wb = 1 - wb;
    wc = 1 - wc;
  }

  const [a, b, c]: any = triangle.map((coords) => ({
    x: coords[0],
    y: coords[1],
  }));

  const rb_x = wb * (b.x - a.x);
  const rb_y = wb * (b.y - a.y);
  const rc_x = wc * (c.x - a.x);
  const rc_y = wc * (c.y - a.y);

  const r_x = rb_x + rc_x + a.x;
  const r_y = rb_y + rc_y + a.y;

  return [r_x, r_y];
}

实例

用下面的代码实际操作随机情况

ctx.strokeStyle = 'blue';
ctx.font = "10px Georgia";
const num = 20;
for (let i = 0; i < num; i++) {
  // 获取随机三角形
  const randomT = selectRandomTriangle(ratioList, triangles)
  if(randomT){
    const point = calcRandomPoint(randomT)
    ctx.strokeText('·', point[0], point[1])
  }
}

下面分别是20个点，100个点，500个点，1000个点的效果，可以看到点均匀随机分布在不规则多边形上。

实际使用背景举例：

1.可以作为一种在已知地图区域进行随机布局的算法，可用于分析布局密集程度之类。

参考资料：

clx. Random Point inside polygon

www.codenong.com/19481514