要使用螺旋算法排序的坐标 (x,y) 列表

Question

我有一个要用螺旋算法排序的坐标列表。我的需要是从区域的中间和 "touch" 任何坐标开始。

为了简化这是（未排序的）坐标列表的表示（x，y 在下图中标有 "dot"）。

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++;
 }

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

很明显，中间的移动是正确的，而相应的坐标位置，在某一时刻，各个坐标之间的跳跃不再连贯。

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

对simplify/reduce问题: 假设上图中的点是销售员必须经常访问的城市。从区域中间的"city"开始，下一个要访问的城市是位于起点附近的城市，位于起点的北、东、南、西。除非出发点这一轮的所有相邻城市都没有被访问过，否则销售员不能访问任何进一步的城市。所有城市必须只参观一次。

Answer 1

当您缺少遍历坐标时，问题似乎出在 if 条件中，即因为圆角。与先前的坐标计算相反的 else 条件将修复它。

Answer 2

算法设计

首先，解放思想，不要想着螺旋上升！ :-) 然后，让我们制定算法约束（让我们使用销售员的视角）：

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

我没去过的地方
尽可能靠近中心（以保持螺旋形）
离我现在的城市越近越好

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

实施

首先，因为我们可以朝任何方向行走，所以我们通常使用 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

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

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

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

这应该可以让您开始针对您的问题实施解决方案。

（正确性）优化

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

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

更新：正确性

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

很容易构造出蓝线肯定比黄线短的情况，从而成为首选。然而，这会打破螺旋运动。为了消除这种情况，我们可以使用行进方向。考虑下图（我为 hand-drawn 角度道歉）：

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

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

// 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

注意正确计算角度和向量。如果您需要这方面的帮助，我可以进一步阐述或简单地提出一个新问题。

要使用螺旋算法排序的坐标 (x,y) 列表

Coordinate (x,y) list to be sort with a spiral algorithm

php

sorting

spiral

coordinates