按顺时针方向对点进行排序

Question

如果我有一个点列表 [(x1,y1), (x2,y2), (x3,y3)...]，是否有任何方法可以将它们排列成顺时针方向？

顺时针方向是指相对于形状中心的顺时针方向。

- Bob Timmon

---

是的，在编程中通常有很多种方法来完成某件事情 - 第一步通常是尝试编写一些代码。请发布您迄今为止尝试过的内容。 - CertainPerformance

您可能需要更详细地说明这些要点。例如，一系列要点可以形成一个1D线而不是2D形状。在这种情况下，顺时针方向不清楚指的是什么。您可能需要查找以下内容：1）找到平均x、y。2）对于每个点，使用x-x中心，y-y中心，并将值插入atan2以获得角度。3）按角度对点进行排序。 - Mike Wodarczyk

这个有限制吗？如果我有点（1,1），它会给出与（-1，-1）相同的角度，因为当得到斜率时，斜率的负号会抵消。 - Bob Timmon

你的形状总是凸的吗？如果不是，那么你如何知道哪些点被认为是相邻的？ - trincot

@trincot，我认为凸性在这里不是问题，因为只要你能计算出点组的质心，就可以从该质心向每个点绘制线条，并获得它们与x轴形成的角度。然后你就可以对点进行排序了。 - jo_va

Answer 1

首先，你需要找到由你的点定义的形状的中心，因为旋转将相对于该点进行定义。

然后，你需要计算点与中心以及 x 轴之间的角度。 要计算角度，可以使用 Math.atan2(y - center.y, x - center.x)。

接下来，使用 Array.sort 按角度对点进行排序。

一旦点正确排序，你应该能够绘制连接点且不相交的线。我使用画布制作了一个演示。起始点用正方形表示。我已经绘制了以你的点质心为原点的 x/y 轴。我还添加了连接点到质心的线条，以显示它们的角度。

Original Answer 翻译成 "最初的回答"。

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>

最初的回答。希望这能帮到你！

- jo_va