Список координат (x, y) для сортировки по спиральному алгоритму
У меня есть список координат для сортировки по спиральному алгоритму. Мне нужно начать с середины области и «коснуться» любой координаты.
Для упрощения это представление (несортированного) списка координат (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++;
}
но так как координаты не равноудалены друг от друга, я получаю этот вывод:
Как ясно видно, движение в середине правильное, тогда как и в соответствии с положением координат, в определенный момент скачок между каждой координатой больше не является когерентным.
Как я могу изменить свой код, чтобы получить подход, подобный этому, вместо этого?
Чтобы упростить / уменьшить проблемуПредставьте, что точки на изображении выше — это города, которые продавец должен посещать почти всегда. Начиная с «города» в центре области, следующие города, которые нужно посетить, расположены рядом с начальной точкой и расположены на севере, востоке, южнее и западе от начальной точки. Продавец не может посетить еще один город, если все соседние города в раунде начальной точки не были посещены. Все города нужно посещать только один раз.
Решение
Алгоритм проектирования
Во-первых, освободите свой разум и не думайте о спирали! 🙂 Тогда, давайте сформулируем ограничения алгоритмов (давайте использовать точку зрения продавца):
Я в настоящее время нахожусь в городе и ищу, куда идти дальше. Я должен найти город:
- где я не был раньше
- это как можно ближе к центру (чтобы сохранить спираль)
- это как можно ближе к моему нынешнему городу
Теперь, учитывая эти три ограничения, вы можете создать детерминированный алгоритм, который создает спираль (по крайней мере, для данного примера, вы, вероятно, можете создать случаи, которые требуют больше усилий).
Реализация
Во-первых, потому что мы можем идти в любом направлении, давайте обычно использовать Евклидово расстояние рассчитать расстояния.
Затем найти следующий город для посещения:
$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
Обратите внимание, чтобы правильно рассчитать угол и векторы. Если вам нужна помощь в этом, я могу уточнить дальше или просто задать новый вопрос.
Другие решения
Кажется, проблема в условном условии, когда вы пропускаете перемещение по координате, т.е. из-за закругления углов. Еще одно условие, обратное предыдущему вычислению координаты, исправит это.