Sorting points in a clockwise direction

Question

If I have a list of points [(x1,y1), (x2,y2), (x3,y3)...] is there any way I can arrange them so that they are in a clockwise direction?

By clockwise direction I mean clockwise relative to the center of the shape.

Answer 1

First, you have to find the center of the shape defined by your points, since the rotation will be defined with respect to this point.

Then you have to calculate the angle the points have with respect to the center and the x axis. To calculate the angle, you can use Math.atan2(y - center.y, x - center.x).

Then you order the points by angle using Array.sort.

Once the points are correctly ordered you should be able to draw a line that connects the points and does not intersect itself. I made a demo using a canvas. The starting point is shown with a square. I have drawn the x/y axis translated to the centroid of your points. I also added lines connecting the points to the centroid to materialize their angles.

const width = 250;
const height = 250;

// Random points
const points = Array.from({ length: 20 }, () =>
  ({ x: Math.random() * width, y: Math.random() * height })
);

// Get the center (mean value) using reduce
const center = points.reduce((acc, { x, y }) => {
  acc.x += x / points.length;
  acc.y += y / points.length;
  return acc;
}, { x: 0, y: 0 });

// Add an angle property to each point using tan(angle) = y/x
const angles = points.map(({ x, y }) => {
  return { x, y, angle: Math.atan2(y - center.y, x - center.x) * 180 / Math.PI };
});

// Sort your points by angle
const pointsSorted = angles.sort((a, b) => a.angle - b.angle);

// Draw them
const canvas = document.querySelector('canvas');
canvas.width = width;
canvas.height = height;
const ctx = canvas.getContext("2d");
let lastPoint = pointsSorted[0];

ctx.fillRect(lastPoint.x, lastPoint.y, 5, 5);

ctx.beginPath();
ctx.moveTo(0, center.y);
ctx.lineTo(width, center.y);
ctx.strokeStyle = 'black';
ctx.stroke();

ctx.beginPath();
ctx.moveTo(center.x, 0);
ctx.lineTo(center.x, height);
ctx.strokeStyle = 'black';
ctx.stroke();  

pointsSorted.forEach(({ x, y }) => {
  ctx.beginPath();
  ctx.moveTo(lastPoint.x, lastPoint.y);
  ctx.lineTo(x, y);
  ctx.strokeStyle = 'red';
  ctx.stroke();  
  
  ctx.fillRect(x, y, 2, 2);
  
  ctx.beginPath();
  ctx.moveTo(center.x, center.y);
  ctx.lineTo(x, y);
  ctx.strokeStyle = 'grey';
  ctx.stroke();  
  
  lastPoint = { x, y };
});

canvas {
  border: 1px solid black;
}

<canvas></canvas>

Hope that helps!