Координаты (x, y) сортируются по спиральному алгоритму

Question

У меня есть список координат, который нужно сортировать по спиральному алгоритму. Моя потребность - начать посередине области и «коснуться» любой координаты.

Для упрощения это представление (несортированный) список координат (x, y, отмеченный «точкой» на следующем изображении).

Список координат CSV доступен here.
Х увеличение слева направо
Y увеличивается от верха до низа

Каждая координата не прилегает к следующей, но вместо того, чтобы distanciated 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++; 
} 

, но поскольку координаты не являются равноудаленными друг от друга, я получаю этот выход:

Как ясно видно, движение в середине правильное, тогда как, соответственно, с координатным положением, в определенный момент прыжок между каждой координатой больше не является когерентным.

Как я могу изменить свой код, чтобы получить такой подход, как этот?

Чтобы упростить/уменьшить проблему: Представьте себе, что точки на показанные выше изображения города, которые продавец должны посетить cirurarly. Начиная с «города» в центре области, следующие города, которые нужно посетить, расположены вблизи начальной точки и расположены на севере, востоке, юго-востоке и западе от начальной точки. Продавец не может посещать какой-либо другой город, если не были посещены все прилегающие города в районе начальной точки. Все города должны посещаться только один раз.

Answer 1

дизайн Алгоритм

Во-первых, освободить свой ум и не думать о спирали! :-) Затем давайте сформулируем ограничения алгоритмов (давайте использовать точку зрения продавца):

Я в настоящее время в городе и ищу, куда идти дальше.Я должен найти город:

• , где я не был до того
• , который как можно ближе к центру, как это возможно (чтобы спиралевидные)
• , который как можно ближе к моему тока город

Теперь, учитывая эти три ограничения, вы можете создать детерминированный алгоритм, который создает спираль (ну, по крайней мере, для данного примера он должен, вы, вероятно, можете создавать случаи, требующие большего усилия).

Реализация

Во-первых, потому что мы можем идти в любом направлении, позволяет в целом использовать 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 

Просто повторите это до тех пор, пока не останется больше городов для посещения.

Чтобы понять, как это работает, рассмотрим следующую картину:

Я нахожусь в настоящее время в желтом круге и мы предполагаем, что спираль до этой точки является правильным. Теперь сравните длину желтой, розовой и синей линий. Длина этих строк в основном вычисляется с использованием функций расстояния. Вы обнаружите, что в каждом случае следующий правильный город имеет наименьшее расстояние (ну, по крайней мере, пока у нас столько точек, вы, вероятно, можете легко встретить встречный пример).

Это должно заставить вас приступить к реализации решения проблемы.

(Корректность) Оптимизация

С текущим дизайном, вы должны сравнить текущий город для всех остальных городов в каждой итерации. Однако некоторые города не представляют интереса и даже в неправильном направлении. Вы можете дополнительно оптимизировать правильность алгоритма, исключив некоторые города из пространства поиска, прежде чем вводить петлю foreach, показанную выше. Рассмотрим эту картину:

Вы не хотите идти в эти города в настоящее время (чтобы спиралью, вы не должны идти в обратном направлении), так что даже не принимать их во внимание расстояние. Хотя это немного сложнее выяснить, если ваши данные не так распределены, как в приведенном примере, эта оптимизация должна обеспечить вам здоровую спираль для более тревожных наборов данных.

Update: Корректность

Сегодня вдруг ударил меня, и я переосмыслила предложенное решение.Я заметил, что случай, когда, опираясь на двух евклидовых расстояний может дать нежелательное поведение:

Это легко можно построить случай, когда синяя линия, безусловно, короче желтого цвета и, таким образом, становится предпочтительным. Однако это нарушит движение спирали. Чтобы устранить такие случаи, мы можем использовать направление движения. Рассмотрят следующий образ (я извиняюсь за рисованными углы):

Ключевой идея заключается в том, чтобы вычислить угол между предыдущим направлением движения и новым направлением движения. Сейчас мы находимся на желтой точке и должны решить, куда идти дальше. Зная предыдущую точку, мы можем получить вектор, представляющий предыдущее направление движения (например, розовую линию).

Далее мы вычисляем вектор в каждом городе, который мы рассматриваем, и вычисляем угол до предыдущего вектора движения. Если этот вектор равен < = 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 

Обращайте внимание на правильность расчета угла и векторов. Если вам нужна помощь в этом, я могу подробнее или просто задать новый вопрос.

Answer 2

Проблема, по-видимому, в условии if-condition, когда вы отсутствуете, пересекая координату, I. из-за округления углов. А еще условное с обратным к предыдущему вычислению координаты зафиксировало бы это.