我想找到一种从随机点创建多边形的好方法。
所有点都应该在多边形中使用,因此每个点都有两个由两条边连接的邻居。任何边缘都不应交叉。
以下是可接受结果的示例:
这里是一个“不”可接受的示例,因为存在相互交叉的边缘:
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>