我有一组坐标需要用螺旋算法进行排序。我的需求是从区域的中心开始,“触摸”任何坐标。
简化表示未排序的坐标列表(x,y用以下图像上的“点”标记)。
可用CSV坐标列表在此处。
X从左到右增加
Y从上到下增加
每个坐标与其后面的坐标不相邻,而是相距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++;
}
但由于坐标点彼此之间的距离不相等,我得到了以下输出结果:
如图所示,中间的移动是正确的,但是根据坐标位置,在某个瞬间,每个坐标之间的跳跃不再一致。
如何修改我的代码才能获得类似下图的结果呢?
为简化/减少问题:假设上述图片中的点表示一个推销员需要循环访问的城市。从区域中心的"城市"开始,下一个要访问的城市是靠近起点并位于东、南、西、北方向的城市。除非起点周围的所有相邻城市都已被访问,否则推销员不能访问任何其他城市。所有城市必须只被访问一次。