Учитывая несколько полигонов, которые перекрываются несколькими способами, я хотел бы экспортировать из этих объектов все полигоны, которые не перекрываются с другими, итеративно.
Продукт будет иметь ряд функций без каких-либо совпадений, которые при суммировании образуют оригинал.
Затем эти продукты можно использовать в качестве входных данных для зональной статистики, и это будет намного быстрее, чем итерация зональной статистики по каждому полигону.
Я пытался закодировать это в ArcPy без успеха.
Код для этого уже существует?
arcpy
algorithm
overlapping-features
ndimhypervol
источник
источник
Ответы:
Это проблема раскраски графа .
Напомним, что раскраска графа - это присвоение цвета вершинам графа таким образом, что никакие две вершины, которые имеют общее ребро, также не будут иметь одинаковый цвет. В частности, (абстрактными) вершинами графа являются многоугольники. Две вершины связаны с (ненаправленным) ребром, когда они пересекаются (как многоугольники). Если мы возьмем какое-либо решение проблемы - которое представляет собой последовательность (скажем, k ) непересекающихся наборов многоугольников - и назначим уникальный цвет каждому набору в последовательности, то мы получим k- раскраску графа. , Желательно найти маленький к .
Эта проблема довольно сложна и остается нерешенной для произвольных графов. Рассмотрим примерное решение, которое просто закодировать. Последовательный алгоритм должен сделать. Алгоритм Уэлша-Пауэлла является жадным решением, основанным на нисходящем упорядочении вершин по степени. В переводе на язык исходных полигонов, сначала отсортируйте полигоны в порядке убывания числа других полигонов, которые они перекрывают. Работая по порядку, дайте первому многоугольнику начальный цвет. На каждом последующем шаге попробуйте закрасить следующий многоугольник существующим цветом: выберите цвет, который не соответствуетуже используется любым из соседей этого многоугольника. (Есть много способов выбрать один из доступных цветов; попробуйте тот, который был наименее использован, или выберите один случайным образом.) Если следующий полигон не может быть окрашен существующим цветом, создайте новый цвет и закрасьте его этим.
Как только вы добились раскраски с небольшим количеством цветов, выполните зональную статистику цвет за цветом: по построению вы гарантируете, что никакие два многоугольника данного цвета не перекрываются.
Вот пример кода в
R
. (Код Python не будет сильно отличаться.) Во-первых, мы описываем перекрытия между семью показанными полигонами.То есть полигоны 1 и 2 перекрываются, как и полигоны 2 и 3, 3 и 4, ..., 1 и 7.
Сортировка вершин по убыванию:
Алгоритм последовательной раскраски (грубый) использует самый ранний доступный цвет, еще не использованный ни одним перекрывающимся многоугольником:
Инициализируйте структуры данных (
colors
иcolor.next
) и примените алгоритм:Разделите полигоны на группы по цвету:
Вывод в этом примере использует четыре цвета:
Он разделил полигоны на четыре непересекающиеся группы. В этом случае решение не является оптимальным ({{3,6,5}, {2,4}, {1,7}} является трехцветной для этого графа). В целом, решение, которое оно получает, не должно быть слишком плохим.
источник
Методология, рекомендованная #whuber, вдохновила меня на новое направление, и вот мое загадочное решение, состоящее из двух функций. Первый, называемый countOverlaps, создает два поля, «overlaps» и «ovlpCount», чтобы записывать для каждого poly, который перекрывается с polys, и сколько произошло перекрытий. Вторая функция, explodeOverlaps, создает третье поле «expl», которое дает уникальное целое число каждой группе непересекающихся полисов. Пользователь может затем экспортировать новые фк на основе этого поля. Процесс разбит на две функции, потому что я думаю, что инструмент countOverlaps может оказаться полезным сам по себе. Пожалуйста, извините за неряшливость кода (и небрежное соглашение об именах), так как он довольно предварительный, но он работает. Также убедитесь, что «idName» field представляет поле с уникальными идентификаторами (проверяется только с целочисленными идентификаторами). Спасибо, что предоставили мне основу, необходимую для решения этой проблемы!
источник
countOverlaps
соответствует двум строкамnbrhoods <- sapply(vertices, neighbors); degrees <- sapply(nbrhoods, length)
в моем коде:degrees
это количество совпадений. Конечно, ваш код длиннее, потому что он отражает большую часть анализа ГИС, который считается само собой разумеющимся в моем решении: а именно, что вы сначала идентифицируете, какие полигоны перекрываются, и что в конце вы используете решение для вывода наборов данных полигонов. Было бы неплохо инкапсулировать теоретико-графовые вычисления, поэтому, если вы когда-нибудь найдете лучший алгоритм раскраски, его будет легко подключить.Это было некоторое время, но я использовал этот код для своего собственного приложения, и он работал отлично - спасибо. Я переписал его часть, чтобы обновить, применить к строкам (с допуском) и значительно ускорить его (ниже - я запускаю его на 50 миллионах пересекающихся буферов, и это занимает всего пару часов).
источник
В этом случае я обычно использую следующий метод:
Я считаю, что результатом будет именно тот результат, который вы хотели получить, и вы даже можете подсчитать количество совпадений. Не знаю, будет ли это с точки зрения производительности лучше для вас или нет.
источник