logo标签列表

将坐标(x,y)列表使用螺旋算法进行排序

phpsortingcoordinatesspiral
15

我有一组坐标需要用螺旋算法进行排序。我的需求是从区域的中心开始，“触摸”任何坐标。

简化表示未排序的坐标列表（x，y用以下图像上的“点”标记）。

可用CSV坐标列表在此处。
X从左到右增加
Y从上到下增加

unsorted list of coordinates 每个坐标与其后面的坐标不相邻，而是相距1或2个骰子（在某些情况下可能更多）。

从区域的中心开始，我需要使用螺旋运动触摸任何坐标：

spiral approach

为了解析每个坐标，我起草了这个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++;
 }

但由于坐标点彼此之间的距离不相等，我得到了以下输出结果：

sorted list of coordinates

如图所示，中间的移动是正确的，但是根据坐标位置，在某个瞬间，每个坐标之间的跳跃不再一致。

如何修改我的代码才能获得类似下图的结果呢?

expected sorted list of coordinates

为简化/减少问题:假设上述图片中的点表示一个推销员需要循环访问的城市。从区域中心的"城市"开始，下一个要访问的城市是靠近起点并位于东、南、西、北方向的城市。除非起点周围的所有相邻城市都已被访问，否则推销员不能访问任何其他城市。所有城市必须只被访问一次。

我觉得你的 CSV 文件不正确。 - Micromega
你如何将结果可视化？你确定在可视化步骤中没有错误吗？而且，“每个坐标不相邻，而是相隔1或2个骰子（在某些情况下可能更多）”这句话具体意思是什么？ - Fabian Kleiser
@StefanoRadaelli，你的问题从第三个正确列（从中心开始）开始，因为y被移位了，换句话说，这不是一个正常的螺旋，你不能在它上面应用正常的螺旋算法。 - tbc
@fakeller，上面网格中的每个坐标都与下一个相邻。正如您所看到的，每个正方形都由颜色（浅蓝色、黄色、绿色）进行标识。在绿色正方形上，有一个“黑点”标识我的附件的坐标。基本上，这意味着我需要以螺旋方式排序附件的坐标（表示上面显示的图像上的点）。红色部分的结果是通过图像编辑器手动“模拟”的。我不是要寻找完全相同的输出，而是类似的东西（我指描述螺旋运动的东西）。 - Stefano Radaelli
你必须先向上移动，然后才能转向左螺旋，这是一个限制吗？ - Fabian Kleiser
显示剩余3条评论
2个回答
10

算法设计

首先，放松你的思想，不要想象一个螺旋形！ :-) 接下来，我们来制定算法的约束条件（使用推销员的视角）：

我现在在一个城市，正在寻找下一步要去哪里。我必须找到一个城市：

  • 我以前没有去过
  • 尽可能靠近中心（保持螺旋形）
  • 尽可能接近我的当前城市

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

实现

首先，因为我们可以朝任何方向走，所以通常使用欧几里得距离来计算距离。

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

$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

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

为了理解它的工作原理，请考虑以下图片：

enter image description here

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

这应该能帮助你开始实现解决方案。

（正确性）优化

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

enter image description here

你现在不想去那些城市（为了保持螺旋形，你不应该往回走），所以甚至不要考虑它们的距离。虽然这可能有点难以理解，如果你的数据点不像你提供的示例那样均匀分布，这种优化应该能为更扰动的数据集提供健康的螺旋形。

更新：正确性

今天突然想到并重新思考了所提出的解决方案。我注意到一种情况，依靠两个欧几里得距离可能会产生不良行为：

enter image description here

可以很容易地构造一种情况，使得蓝线肯定比黄线短，从而得到首选。然而，这会破坏螺旋运动。为了消除这种情况，我们可以利用行进方向。考虑以下图像（我为手绘角度道歉）：

enter image description here

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

接下来，我们计算到我们考虑的每个城市的向量，并计算与前一个移动向量之间的角度。如果该向量<=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

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

1
城市起源于旅行推销员的隐喻，以简化语言和理解。如果你仔细观察网格，你会发现这些点并不均匀地分布（即在左上角有两个直接相邻的点）。在这个例子中，这些点只包含整数值作为坐标，但是这种方法并不局限于此。 - Fabian Kleiser
我理解，但他有一个包含点的csv文件，据我所知，csv文件中的点是均匀分布的？是这样吗？ - Micromega
销售员类比中，点被视为城市。算法需要连接这些点，例如销售员需要拜访这些城市。如果您不知道旅行推销员是什么，请参考旅行推销员问题。 - Fabian Kleiser
1
@Phpdna 我并不是在寻找解决旅行商问题的算法。只需想象图像上的点是城市，一个假设的旅行商必须按照循环方式访问每个城市（仅一次）。也许“旅行商”这个定义有误导性，但我的请求与解决我所面临的问题的TSP方法无关。 - Stefano Radaelli
1
@Stefano，我添加了一个部分，解释如何进一步确保正确性。 - Fabian Kleiser
显示剩余4条评论
1
问题似乎出在if条件语句中，当你漏掉一个坐标时，即因为圆角的四舍五入。一个else条件语句，反转先前计算的坐标，可以解决这个问题。
这是一个很好的起点。所示路由仅使用图像编辑器手动绘制，以显示“可能的预期输出”。我的请求是找到一种算法，即使坐标没有描述完美的螺旋形运动也能描述出来。预期的输出可能与所示输出不同，但在计算路由方面必须类似。 - Stefano Radaelli
@StefanoRadelli：你想得太多了。简单点，使用3D到2D的投影方法就可以了。 - Micromega
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接