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

Question

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

为了简化这一点,表示(未排序的)坐标列表(x,y在后面的图像上标有"点").

此处提供CSV坐标列表.
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++;
 }

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

可以清楚地看到,中间的运动是正确的,而相应的坐标位置,在某个时刻,每个坐标之间的跳跃不再是连贯的.

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

简化/减少问题:想象一下,上图所示的点是推销员必须经常访问的城市.从该区域中间的"城市"开始,下一个要访问的城市是位于起点附近的城市,位于起点的北,东,南,西.除非在起点的所有相邻城市没有被访问过,否则销售员不能访问任何其他城市.所有城市必须只访问一次.

Answer 1

算法设计

首先,放开你的思想,不要想到螺旋!:-)然后,让我们制定算法约束(让我们使用销售员的观点):

我目前在一个城市,我正在寻找下一步去哪里.我要找一个城市:

• 以前我没去过的地方
• 尽可能靠近中心(保持螺旋式)
• 这与我目前的城市尽可能接近

现在,考虑到这三个约束,您可以创建一个创建螺旋的确定性算法(至少对于给定的示例,它应该可以创建需要更多努力的情况).

履行

首先,因为我们可以向任何方向行走,所以通常使用欧几里德距离来计算距离.

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

$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),则方向正常,否则不正确(图像中的情况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

注意正确计算角度和矢量.如果您需要帮助,我可以进一步详细说明或者只是提出一个新问题.