Algorithm to create a polygon from points

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?

Start at one point. Connect that one with another point. Repeat until one line crosses another. Delete the currebt line and try another point. If all left points were taken already, go back one step. That'll be O(n!) worst case. — Jonas Wilms, Dec 11 '19 at 14:31
Does this answer your question? [How to draw a polygon from a set of unordered points](https://stackoverflow.com/questions/14392072/how-to-draw-a-polygon-from-a-set-of-unordered-points) — Prune, Dec 11 '19 at 22:21
That dupe-reference is really about finding the convex hull.... — trincot, Apr 04 '21 at 12:18

trincot · Answer 1 · 2019-12-19T16:34:33.790

You could:

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".
Translate the coordinates of the given points to polar coordinates, where the point chosen in step one is the origin (0, 0).
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).
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>

This is a very cool algorithm! I like the way it uses polar coordinates to mimic human intuition about starting at one point and then moving clockwise/counter-clockwise. What is this algorithm called if I wanted to read about this further? :-) — Madhav Malhotra, Apr 05 '23 at 13:22
Not sure if it has a name, but the rotational aspect is a sort of [Sweep line](https://en.wikipedia.org/wiki/Sweep_line_algorithm) algorithm, but applied to polar coordinates. — trincot, Apr 05 '23 at 13:28

Algorithm to create a polygon from points

1 Answers1

Linked