CODEWITHSUNDEEP
algorithmgraphics
Anshul
Anshul

Reputation: 103

Algorithm to create polygon

I need to create a polygon from given set of points, which algorithm should i use for this purpose. The polygon edges should not overlap each other. No. Of ponits can be huge. For example 1000

Upvotes: 1

Views: 122

Answers (1)

6502
6502

Reputation: 114579

A simple solution would be to

  1. compute the barycenter (i.e. the average of x and y of all points)
  2. sort by angle in respect to the center (i.e. atan2(p.y-center.y, p.x-center.x))
  3. connect the points

The result will be a valid star-shaped polygon with no edge overlapping.

In Javascript for example:

// 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();

enter image description here

Upvotes: 2

Related Questions