Сортировка не упорядоченной последовательной координаты для получения контура зоны

Вход представляет собой последовательность, полученную, когда я нахожу контур из зоны. Эта последовательность состоит из пикселей, окружающих эту зону.Сортировка не упорядоченной последовательной координаты для получения контура зоны

Но эта последовательность не упорядочена из-за использования рекурсивного, когда я получил последовательность. Как я могу сортировать эту последовательность?

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

источник

2015-03-06 David

Вы забыли указать, что сгенерированная схема должна быть как можно меньше? Потому что тогда вы заново открываете [Проблема с продавцом] (https://en.wikipedia.org/wiki/Travelling_salesman_problem) – goncalopp

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

Является ли зона гарантированной выпуклостью? –

Если зона выпуклая, то все, что вам нужно сделать, это найти convex hull для набора пикселей. Если зона также может быть вогнутой, то вы не можете решить проблему - план можно реконструировать по-разному, и каждый из них будет равновероятен (если не будет предоставлена дополнительная информация).

источник

2015-03-06 11:09:38

Прошу прощения, что описание недостаточно подробно. Зона может быть вогнутой. Возможно, восстановление истинного контура невозможно. Но можем ли мы получить ближайший контур между ним и оригинальным контуром? – David

Но если зона может быть вогнутой, а точки случайным образом перетасовываются, то вы не можете даже приблизиться. Большинство перестановок точек будут действительным контуром вогнутой зоны. Поскольку у gou нет никакой дополнительной информации, вы не можете различить их, и любой контур будет выглядеть одинаково правдоподобным. –

Я думаю, что единственная информация заключается в том, что каждый контур является пикселем, поэтому каждый контурный пиксель всегда будет иметь один или несколько соседних пикселей. – David

Вы говорите, что эти ваши точки представляют собой контур какого-то региона. Если это действительно так, вы можете пойти и просто найти ближайших соседей.

Но это одно может быть довольно медленным, поэтому убедитесь, что вы реализуете некоторые эвристики, чтобы уменьшить количество расстояний между точками, которые нужно вычислить, чтобы найти ближайших соседей.

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

И если расстояние до всех точек, находящихся в одних и тех же ячейках сетки, больше, чем расстояние от точки начала до ближайшей границы ячейки, также проверяйте точки в соседней ячейке ячейки, которые имеют одну и ту же границу.

Самое большое преимущество этого подхода состоит в том, что ему не важно, является ли форма области выпуклой или вогнутой.

источник

2015-03-06 11:28:17 SilverWarior

Сортировка не упорядоченной последовательной координаты для получения контура зоны

ответ

Смежные вопросы