我有一个要用螺旋算法排序的坐标列表。我的需要是从该区域的中间开始并“触摸”任何坐标。

为了简化这是(未排序的)坐标列表的表示(x，y 在下图中用“点”标记)。

坐标的 CSV 列表可用 here .
X从左到右递增
Y 从 TOP 到 BOTTOM 增加

每个坐标都不与下一个坐标相邻，而是相距 1 或 2 个骰子(或在某些情况下更多)。

从区域的中心开始，我需要通过螺旋运动接触任何坐标:

为了解析每个坐标，我起草了这个 PHP 算法:

 //$missing is an associative array having as key the coordinate "x,y" to be touched
 $direction = 'top';
 $distance = 1;
 $next = '128,127';     //starting coordinate
 $sequence = array(
     $next;
 )
 unset($missing[$next]);
 reset($missing);
 $loopcount = 0;
 while ($missing) {
    for ($loop = 1; $loop <= 2; $loop++) {
        for ($d = 1; $d <= $distance; $d++) {
            list($x,$y) = explode(",", $next);
                if ($direction == 'top')    $next = ($x) . "," . ($y - 1);
            elseif ($direction == 'right')  $next = ($x + 1) . "," . ($y);
            elseif ($direction == 'bottom') $next = ($x) . "," . ($y + 1);
            elseif ($direction == 'left')   $next = ($x - 1) . "," . ($y);
            if ($missing[$next]) {
                unset($missing[$next]);     //missing is reduced every time that I pass over a coordinate to be touched
                $sequence[] = $next;
            }
        }
            if ($direction == 'top')    $direction = 'right';
        elseif ($direction == 'right')  $direction = 'bottom';
        elseif ($direction == 'bottom') $direction = 'left';
        elseif ($direction == 'left')   $direction = 'top';
    }
    $distance++;
 }

但由于坐标彼此不等距，我得到了这个输出:

可以清楚地看到，中间的移动是正确的，而相应的坐标位置，在某个瞬间，各个坐标之间的跳跃不再连贯。

我如何修改我的代码以获得类似这种方法？

为了简化/减少问题:假设上图中显示的点是销售员必须定期访问的城市。从区域中间的“城市”开始，接下来要访问的城市是位于起点附近且位于起点的北、东、南、西的城市。除非出发点这一轮的所有相邻城市都没有被访问过，否则销售员不能访问任何进一步的城市。所有城市必须只访问一次。

最佳答案

算法设计

首先，解放你的思想，不要想着螺旋上升! :-) 然后，让我们制定算法约束(让我们从销售员的角度来看):

我目前在一个城市，正在寻找下一步要去的地方。我必须找到一个城市:

• 我以前没去过的地方
• 尽可能靠近中心(以保持螺旋形)
• 尽可能靠近我现在所在的城市

现在，鉴于这三个约束条件，您可以创建一个确定性算法来创建螺旋(至少对于给定的示例应该如此，您可能可以创建需要更多努力的案例)。

实现

首先，因为我们可以朝任何方向行走，所以我们通常使用 Euclidean distance计算距离。

然后找到下一个要访问的城市:

$nextCost = INF;
$nextCity = null;
foreach ($notVisited as $otherCity) {
    $cost = distance($current_city, $other_city) + distance($other_city, $centerCity);
    if ($cost < $nextCost) {
        $nextCost = $cost;
        $nextCity = $otherCity;
    }
}
// goto: $nextCity

重复此操作，直到没有更多城市可供访问。

要了解其工作原理，请考虑下图:

我目前在黄色圆圈中，我们假设螺旋上升到这一点是正确的。现在比较黄色、粉色和蓝色线的长度。这些线的长度基本上是我们使用距离函数计算的。你会发现在每一种情况下，下一个正确的城市都有最小的距离(好吧，至少只要我们到处都有尽可能多的点，你可能很容易想出一个反例)。

这应该让您开始为您的问题实现解决方案。

(正确性)优化

在当前设计中，您必须在每次迭代中将当前城市与所有剩余城市进行比较。但是，有些城市并不感兴趣，甚至方向错误。在进入上面所示的 foreach 循环之前，您可以通过从搜索空间中排除一些城市来进一步优化算法的正确性。考虑这张图片:

你现在不想去那些城市(继续螺旋上升，你不应该倒退)，所以甚至不要考虑它们的距离。尽管弄清楚这一点有点复杂，但如果您的数据点分布不如您提供的示例中那样均匀，则此优化应该为您提供一个健康的螺旋式增长以应对更多受干扰的数据集。

更新:正确性

今天我突然想到了，我重新考虑了提议的解决方案。我注意到依赖两个欧氏距离可能会产生不需要的行为的情况:

可以很容易地构建蓝线肯定比黄线短的情况，从而成为首选。然而，这会打破螺旋运动。为了消除这种情况，我们可以使用行进方向。考虑下图(我为手绘角度道歉):

关键思想是计算先前行进方向与新行进方向之间的角度。我们目前处于黄点，需要决定下一步去哪里。知道之前的点，我们可以获得代表之前运动方向的向量(例如粉红色的线)。

接下来，我们计算我们考虑的每个城市的向量，并计算与前一个移动向量的角度。如果该矢量 <= 180="" 度(图中的情况="" 1)，则方向正确，否则方向不正确(图像中的情况="">

// initially, you will need to set $prevCity manually
$prevCity = null;

$nextCost = INF;
$nextCity = null;
foreach ($notVisited as $otherCity) {
    // ensure correct travel direction
    $angle = angle(vectorBetween($prevCity, $currentCity), vectorBetween($currentCity, $otherCity));
    if ($angle > 180) {
        continue;
    }

    // find closest city
    $cost = distance($current_city, $other_city) + distance($other_city, $centerCity);
    if ($cost < $nextCost) {
        $nextCost = $cost;
        $nextCity = $otherCity;
    }
}
$prevCity = $currentCity;
// goto: $nextCity

注意正确计算角度和向量。如果您需要这方面的帮助，我可以进一步详细说明或直接提出一个新问题。

关于php - 要使用螺旋算法排序的坐标 (x,y) 列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28323023/