从点创建多边形的算法

Question

我想找到一种从随机点创建多边形的好方法。

所有点都应该在多边形中使用，因此每个点都有两个由两条边连接的邻居。任何边缘都不应交叉。

以下是可接受结果的示例：

这里是一个“不”可接受的示例，因为存在相互交叉的边缘：

有这方面的算法吗？

Answer 1

确定一些好的开始点，不一定是给定的点之一。使用一些启发式方法。例如，给定点的“质心”可能是一个有用的选择。但是凸包内任何一个点的选择都会产生一个具有不相交边的多边形。根据选择，多边形可能更“平滑”或更“平滑”。
将给定点的坐标转换为极坐标，其中第一步选择的点是原点 (0, 0)。
按极坐标对点进行排序：首先按极角，然后按半径（或者实际上是半径的平方，以省略使用平方根函数）。
使用此顺序绘制多边形。
这是交互式片段中的实现：

function squaredPolar(point, centre) {
    return [
        Math.atan2(point[1]-centre[1], point[0]-centre[0]),
        (point[0]-centre[0])**2 + (point[1]-centre[1])**2 // Square of distance
    ];
}

// Main algorithm:
function polySort(points) {
    // Get "centre of mass"
    let centre = [points.reduce((sum, p) => sum + p[0], 0) / points.length,
                  points.reduce((sum, p) => sum + p[1], 0) / points.length];

    // Sort by polar angle and distance, centered at this centre of mass.
    for (let point of points) point.push(...squaredPolar(point, centre));
    points.sort((a,b) => a[2] - b[2] || a[3] - b[3]);
    // Throw away the temporary polar coordinates
    for (let point of points) point.length -= 2; 
}

let points = [];

// I/O management

let canvas = document.querySelector("canvas");
let ctx = canvas.getContext("2d");

function draw(points) {
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    if (!points.length) return;
    for (let [x, y] of points) {
        ctx.beginPath();
        ctx.arc(x, y, 3, 0, 2 * Math.PI, true);
        ctx.fill();
    }
    ctx.beginPath();
    ctx.moveTo(...points[0]);
    for (let [x, y] of points.slice(1)) ctx.lineTo(x, y);
    ctx.closePath();
    ctx.stroke();
}

canvas.onclick = function (e) {
    let x = e.clientX - this.offsetLeft;
    let y = e.clientY - this.offsetTop;
    let match = points.findIndex(([x0, y0]) => Math.abs(x0-x) + Math.abs(y0-y) <= 6);
    if (match < 0) points.push([x, y]);
    else points.splice(match, 1); // delete point when user clicks near it.
    polySort(points);
    draw(points);
};

canvas { border: 1px solid }

Click to draw points. Polygon will be drawn in real-time:<br>
<canvas></canvas>

Answer 2