Algorithm to create a polygon from points [closed]

Question

I want to find a good way to create a polygon from random points.

All the points should be used in the polygon, and so each point would have two neighbors connected by two edges. No edge should cross another.

Here is an example of an acceptable result:

Here is an example of what would not be acceptable, because there are edges that cross each other:

Is there an algorithm for this?

Answer 1

You could:

1. Determine some good point to start with, not necessary one of the given points. Use some heuristic. For instance, the "centre of mass" of the given points could be a useful choice. But any choice of a point within the convex hull will produce a polygon that will have non-intersecting edges. Depending on the choice, the polygon may be less or more "smooth".

2. Translate the coordinates of the given points to polar coordinates, where the point chosen in step one is the origin (0, 0).

3. Sort the points by their polar coordinates: first by polar angle, then by radius (or actually the square of the radius to omit using the square root function).

4. Draw the polygon using this ordering.

Here is an implementation in an interactive snippet:

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>