algorithm - 我如何错误地实现此算法以对螺旋中的点列表进行排序？

Question

我正在尝试以一致的螺旋方式对点列表进行排序。

这里的算法简直超出了我的范围；见this jsbin举个我在做什么的例子。

您将看到的图表应该尽可能接近螺旋形，目前不是，即使我遵循概述的算法 on this other answer以及愚蠢的“中心距离”排序。

在 jsbin 中有一个我当前失败的仅点可视化；如果您取消注释对 drawPoints 的调用，并在“sortByStackOverflow”和“sortByCenterDistance”之间切换，您应该可以看到我的两次解决尝试。

我做错了什么？我应该在哪里寻找这个？

我在 JS 中这样做的主要原因是为了便于可视化，如果 JS 不是您的首选语言，则没有真正要求您帮助我。

Answer 1

您所做的两次尝试是按到中心的距离和角度位置对点进行排序，但它们都不会构建螺旋。

这是一个伪代码算法，应该产生更螺旋的东西:

point = farthest_from_center(points)
result = [point]
points.remove(point)
//choose a previous point so that previous_point->point is perpendicular to point->center
previous = {x: point.x-point.y+center.y , y: point.x+point.y-center.x}
while(points is not empty){
  next=least_angled_point(previous,point,points) //see below for details
  result.push(next)
  points.remove(next)
  previous=point
  point=next
}
return result

我们希望在每次迭代中选择与当前行进方向偏差最小的点。当从离中心最远的点开始并垂直方向时，这应该会产生一个螺旋。

选择 least_angled_point 可以通过计算点中所有可能的下一个点的向量 previous->point 和 point->next 之间的点积来完成，并选择最大值(点积给出向量之间角度的余弦，较高的余弦对应于较低的角度)。这个点积可以通过以下方式计算:

function dot_product(previous,point,next){
  return (point.x-previous.x)*(next.x-point.x)+(point.y-previous.y)*(next.y-point.y)

该算法的点数复杂度为 n^2，因为它需要计算从每个点到所有剩余点的点积以进行连接，但如果您不需要对数千个点进行计算点它应该没问题。

我还没有实现和测试它，所以如果您这样做并发现任何错误，请告诉我，我会尽力提供帮助!