Алгоритм создания полигона

Question

Мне нужно создать многоугольник из заданного набора точек, какой алгоритм я должен использовать для этой цели. Края многоугольника не должны перекрывать друг друга. Нет. Пониты могут быть огромными. Например 1000

Answer 1

Простым решением было бы

1. вычислить барицентр (т. Е. Среднее значение x и y для всех точек)
2. сортировать по углу относительно центра (т.е. atan2(p.y-center.y, p.x-center.x))
3. соединить точки

В результате будет получен правильный звездообразный многоугольник без наложения ребер.

В Javascript, например:

// Generate random points
let pts = [];
for (let i=0; i<100; i++) {
    pts.push({x:Math.random()*300,
              y:Math.random()*300});
}

// Compute the barycenter
let center = {x:0, y:0};
pts.forEach(p=>{
    center.x += p.x;
    center.y += p.y;
});
center.x /= pts.length
center.y /= pts.length;

// Sort points on the angle of the
// line connecting to the center
pts.sort((a, b) => Math.atan2(a.y - center.y,
                              a.x - center.x)
                   -
                   Math.atan2(b.y - center.y,
                              b.x - center.x));

// Draw result
let canvas = document.createElement("canvas");
let ctx = canvas.getContext("2d");
canvas.width = canvas.height = 300;
document.body.appendChild(canvas);
ctx.beginPath();
ctx.moveTo(pts[0].x, pts[0].y);
pts.forEach(p=>ctx.lineTo(p.x, p.y));
ctx.fillStyle = "#F00";
ctx.fill();