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

Question

I have a list of coordinate to be sorted with a spiral algorithm. My need is to start on the middle of the area and "touch" any coordinate.

To simplify this is the representation of the (unsorted) list of coordinates (x,y marked with a "dot" on following image).

CSV list of coordinates is available here.
X increase from left to right
Y increases from TOP to BOTTOM

Every coordinate is not adjacent to the following one but are instead distanciated by 1 or 2 dice (or more in certain case).

Starting from the center of the area, I need to touch any coordinate with a spiral movement:

to parse each coordinate I've drafted this PHP algorithm:

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

but as coordinate are not equidistant from each other, I obtain this output:

As is clearly visible, the movement in the middle is correct whereas and accordingly with the coordinate position, at a certain instant the jump between each coordinate are not anymore coherent.

How can I modify my code to obtain an approach like this one, instead?

To simplify/reduce the problem: Imagine that dots on shown above image are cities that the salesman have to visit cirurarly. Starting from the "city" in the middle of the area, the next cities to be visited are the ones located near the starting point and located on North, East, Soutch and West of the starting point. The salesman cannot visit any further city unless all the adjacent cities in the round of the starting point hadn't been visited. All the cities must be visited only one time.

Answer 1

Algorithm design

First, free your mind and don't think of a spiral! :-) Then, let's formulate the algorithms constraints (let's use the salesman's perspective):

I am currently in a city and am looking where to go next. I'll have to find a city:

• where I have not been before
• that is as close to the center as possible (to keep spiraling)
• that is as close as possible to my current city

Now, given these three constraints you can create a deterministic algorithm that creates a spiral (well at least for the given example it should, you probably can create cases that require more effort).

Implementation

First, because we can walk in any direction, lets generally use the Euclidean distance to compute distances.

Then to find the next city to visit:

$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

Just repeat this until there are no more cities to visit.

To understand how it works, consider the following picture:

I am currently at the yellow circle and we'll assume the spiral up to this point is correct. Now compare the length of the yellow, pink and blue lines. The length of those lines is basically what we compute using the distance functions. You will find that in every case, the next correct city has the smallest distance (well, at least as long as we have as many points everywhere, you probably can easily come up with a counter-example).

This should get you started to implement a solution for your problem.

(Correctness) Optimization

With the current design, you will have to compare the current city to all remaining cities in each iteration. However, some cities are not of interest and even in the wrong direction. You can further optimize the correctness of the algorithm by excluding some cities from the search space before entering the foreach loop shown above. Consider this picture:

You will not want to go to those cities now (to keep spiraling, you shouldn't go backwards), so don't even take their distance into account. Albeit this is a little more complicated to figure out, if your data points are not as evenly distributed as in your provided example, this optimization should provide you a healthy spiral for more disturbed datasets.

Update: Correctness

Today it suddenly struck me and I rethought the proposed solution. I noticed a case where relying on the two euclidean distances might yield unwanted behavior:

It is easily possible to construct a case where the blue line is definitely shorter than the yellow one and thus gets preferred. However, that would break the spiral movement. To eliminate such cases we can make use of the travel direction. Consider the following image (I apologize for the hand-drawn angles):

The key idea is to compute the angle between the previous travel direction and the new travel direction. We are currently at the yellow dot and need to decide where to go next. Knowing the previous dot, we can obtain a vector representing the previous direction of the movement (e.g. the pink line).

Next, we compute the vector to each city we consider and compute the angle to the previous movement vector. If that vector is <= 180 deg (case 1 in the image), then the direction is ok, otherwise not (case 2 in the image).

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

Pay attention to compute the angle and vectors correctly. If you need help on that, I can elaborate further or simply ask a new question.

Answer 2

The problem seems to be in the if-conditional when you missing traverse a co-ordinate, I.e because of rounding of the corners. A else conditional with a reverse to the previous calculation of the co-ordinate would fix it.