我如何错误地实现这个算法来排序螺旋中的点列表？

Question

我想排列一个螺旋点的列表。

这里的算法简直超出了我;有关我正在做什么的示例，请参阅this jsbin。

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

在jsbin中，我只能看到目前失败的可视化点;如果您取消对drawPoints的呼叫，并且在“sortByStackOverflow”和“sortByCenterDistance”之间切换应该让您看到我的两个尝试。

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

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

Answer 1

你所做的两个尝试是按照到中心的距离和角位置排序点，但它们都不会构建螺旋。

这是伪代码的算法应该更spiraly生产的东西：

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的复杂点的数量，因为它需要计算所有其余点从每个点的点积连接，但如果你不需要在成千上万的点上工作，它应该没问题。

我还没有实施和测试它，所以如果你这样做，并发现任何错误让我知道，我会尽力帮助！

Answer 2

我玩过一些代码和链接的其他帖子。这不是一个完整的答案，但有一点我认为你缺少的是：

首先计算中心点

在sortByStackoverflow你这样做：

var center = {x: window.innerWidth/2, y:window.innerHeight/2}; 

我将建议改变这到所有点的中心点（即非静态的点）。一种选择可以是加权平均（所有点具有相同的权重）来计算所有点的“质量中心”。

function sortByStackoverflow(points){ 
    … 
    var center = {x: 0, y:0}; 
    for (var i = 0; i < points.length; i++) { 
     center.x += points[i].x; 
     center.y += points[i].y; 
    } 
    center.x /= points.length; 
    center.y /= points.length; 
    … 
}