Алгоритм нечеткого наименьшего грубого общего разбиения

9

Учитывая два разных раздела формы (ради аргумента, два разных административных деления страны), как мне найти новый раздел, в который вписываются оба этих раздела, допускающий (и оптимизирующий) некоторую ошибку?

Например, игнорируя ошибку, я хочу алгоритм, который делает это:

Нечеткая версия

Возможно, это поможет выразить это в установленные сроки. Используя следующую нумерацию:

Я могу выразить разделы выше как:

A = {{1}, {2}, {3,4,7,8}, {5}, {6}, {9,10,13,14}, {11}, {12}, {15} , {16}}

B = {{1,2,5,6}, {3}, {4}, {7}, {8}, {9}, {10}, {13}, {14}, {11,15} , {12,16}}

Точка B = {{1,2,5,6}, {3,4,7,8}, {9,10,13,14}, {11,15}, {12,16}}

и алгоритм для создания точки B кажется простым (что-то вроде, если два элемента находятся в разделе вместе в A (B), объединить разделы, в которых они находятся в B (A) - повторять до тех пор, пока A и B не будут равны).

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

Возьмите новый пример:

Здесь, в левом столбце, у нас есть два раздела без общих линий (кроме самой внешней границы). Единственное возможное решение вышеупомянутого вида - тривиальное, правый столбец. Но если мы допустим «нечеткие» решения, тогда может быть допустим средний столбец, скажем, 5% от общей площади оспариваемых (то есть выделенных для разных подрайонов в каждом укрупненном разделе). Таким образом, мы могли бы описать средний столбец как представляющий «наименее грубый общий раздел с ошибкой <= 5%».

Независимо от того, является ли фактический ответ разделом в верхнем ряду, среднем столбце или среднем ряду, среднем столбце - или чем-то промежуточным, менее важно.

EconAndrew
источник
Я не понимаю вашу операцию. Кажется, вы ищете общее огрубление двух разделов. Без дополнительных критериев, тем не менее, обычно будет много решений. Например, поскольку грубое (а не уточнение) является вашей целью, зачем останавливаться на достигнутом? Почему бы просто не нарисовать общий ограничительный квадрат?
whuber
1
Спасибо, я неправильно обозначил это. То, что я имею в виду, это лучший общий раздел, или, возможно, «наименее грубый».
EconAndrew
В этом случае результат будет сильно отличаться от того, что вы нарисовали. Это будет 4х4 шахматная доска из квадратов. Из этого одного примера я не смог вывести правило, которому вы хотите следовать. Может быть, вы пытаетесь сохранить все ребра, общие для всех входных функций? Какую реальную проблему вы пытаетесь решить? Не могли бы вы привести конкретный пример, чтобы помочь нам понять, каким должен быть ваш вопрос ?
whuber
Я разработал много - возможно, это поможет. Это правда, что в нечетком случае я не могу точно указать свой вопрос, но я думаю, что именно в этом случае я точно знаю, что имею в виду (даже если я не очень хорошо это выражаю).
EconAndrew
Спасибо за эти усилия (+1). С точкой зрения вашего теоретико-множественной записи, разбиение области образует частично упорядоченное множество : разбиение является уточнением из B , а B представляет собой огрубление из А , когда каждый набор в A есть подмножество одного в B . Ваша работа , как представляется , сочетающих быть лучшим общим огрубление A и B . Один из способов справиться с вашей нечеткой версией - использовать возможности ГИС для удаления зависаний и осколков, чтобы исправить небольшие расхождения между двумя слоями, а затем выполнить нечеткую операцию.
whuber

Ответы:

2

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

Difference(a, SymDifference(a, b))

Возьмем геометрию a и b , выраженную в виде нескольких строк для следующих двух строк и изображений:

MULTILINESTRING((0 300,50 300,50 250,0 250,0 300),(50 300,100 300,100 250,50 250,50 300),(0 250,50 250,50 200,0 200,0 250),(50 250,100 250,100 200,50 200,50 250),(100 300,200 300,200 200,100 200,100 300),(0 200,100 200,100 100,0 100,0 200),(100 200,150 200,150 150,100 150,100 200),(150 200,200 200,200 150,150 150,150 200),(100 150,150 150,150 100,100 100,100 150),(150 150,200 150,200 100,150 100,150 150))
MULTILINESTRING((0 300,100 300,100 200,0 200,0 300),(100 300,150 300,150 250,100 250,100 300),(150 300,200 300,200 250,150 250,150 300),(100 250,150 250,150 200,100 200,100 250),(150 250,200 250,200 200,150 200,150 250),(0 200,50 200,50 150,0 150,0 200),(50 200,100 200,100 150,50 150,50 200),(0 150,50 150,50 100,0 100,0 150),(50 150,100 150,100 100,50 100,50 150),(100 200,150 200,150 100,100 100,100 200),(150 200,200 200,200 100,150 100,150 200))

a б

Симметричная разность, где части a и b не пересекаются, составляет:

MULTILINESTRING((50 300,50 250),(50 250,0 250),(100 250,50 250),(50 250,50 200),(150 150,100 150),(200 150,150 150),(150 300,150 250),(150 250,100 250),(200 250,150 250),(150 250,150 200),(50 200,50 150),(50 150,0 150),(100 150,50 150),(50 150,50 100))

symdiff

И, наконец, оцените разницу между a или b и симметричной разностью:

MULTILINESTRING((0 300,50 300),(0 250,0 300),(50 300,100 300),(100 300,100 250),(50 200,0 200),(0 200,0 250),(100 250,100 200),(100 200,50 200),(100 300,150 300),(150 300,200 300,200 250),(200 250,200 200),(200 200,150 200),(150 200,100 200),(100 200,100 150),(100 150,100 100),(100 100,50 100),(50 100,0 100,0 150),(0 150,0 200),(150 200,150 150),(200 200,200 150),(150 150,150 100),(150 100,100 100),(200 150,200 100,150 100))

diff_symdiff

Вы можете реализовать эту логику в GEOS (Shapely, PostGIS и т. Д.), JTS и других. Обратите внимание, что если входные геометрии являются полигонами, то их границы должны быть извлечены, и результат может быть полигонизирован. Например, показано с помощью PostGIS, возьмите два мультиполигона и получите результат мультиполигона:

SELECT
  ST_AsText(ST_CollectionHomogenize(ST_Polygonize(
    ST_Difference(ST_Boundary(A), ST_SymDifference(ST_Boundary(A), ST_Boundary(B)))
  ))) AS result
FROM (
  SELECT 'MULTIPOLYGON(((0 300,50 300,50 250,0 250,0 300)),((50 300,100 300,100 250,50 250,50 300)),((0 250,50 250,50 200,0 200,0 250)),((50 250,100 250,100 200,50 200,50 250)),((100 300,200 300,200 200,100 200,100 300)),((0 200,100 200,100 100,0 100,0 200)),((100 200,150 200,150 150,100 150,100 200)),((150 200,200 200,200 150,150 150,150 200)),((100 150,150 150,150 100,100 100,100 150)),((150 150,200 150,200 100,150 100,150 150)))'::geometry AS a,
    'MULTIPOLYGON(((0 300,100 300,100 200,0 200,0 300)),((100 300,150 300,150 250,100 250,100 300)),((150 300,200 300,200 250,150 250,150 300)),((100 250,150 250,150 200,100 200,100 250)),((150 250,200 250,200 200,150 200,150 250)),((0 200,50 200,50 150,0 150,0 200)),((50 200,100 200,100 150,50 150,50 200)),((0 150,50 150,50 100,0 100,0 150)),((50 150,100 150,100 100,50 100,50 150)),((100 200,150 200,150 100,100 100,100 200)),((150 200,200 200,200 100,150 100,150 200)))'::geometry AS b
) AS f;
                               result
--------------------------------------------------------------------------------
MULTIPOLYGON(((0 300,50 300,100 300,100 250,100 200,50 200,0 200,0 250,0 300)),((100 250,100 300,150 300,200 300,200 250,200 200,150 200,100 200,100 250)),((0 200,50 200,100 200,100 150,100 100,50 100,0 100,0 150,0 200)),((150 200,200 200,200 150,200 100,150 100,150 150,150 200)),((100 200,150 200,150 150,150 100,100 100,100 150,100 200)))

Обратите внимание, что я не тестировал этот метод всесторонне, поэтому примите его как отправную точку.

Майк Т
источник
Не могли бы вы рассказать о том, как этот алгоритм обрабатывает нечеткую версию проблемы, о которой идет речь, или как его можно адаптировать к этой версии?
whuber
0

Алгоритм без ошибок.

Первый набор: введите описание изображения здесь второй набор: введите описание изображения здесь

Объединить 2 комплекта и отсортировать в порядке убывания по площади. Выбирайте строки в таблице (сверху => вниз), пока не будет достигнуто общее количество областей = общая площадь (в данном случае 16):

введите описание изображения здесь

Выбранные строки делают ваш ответ:

введите описание изображения здесь

Критериями будет разница между накопленными площадями и фактическим итогом.

FelixIP
источник
Похоже, что он будет работать правильно только в особых случаях. Как вы гарантируете, что в итоге вы получите непересекающийся, исчерпывающий раздел общего региона?
whuber
Правильный. Дополнительные шаги a) Объединение наборов данных в терминах Arcgis Union tool b) взять первый по величине из объединенной таблицы и проверить долю других внутри c) удалить другие с порогом большей доли, например, 90%. Как это?
FelixIP
Я не знаю, потому что я еще не понял, что на самом деле задает вопрос.
whuber
Составьте область, используя самые большие возможные блоки. Это мое понимание вопроса
FelixIP
Решением этой проблемы является использование одного блока (объединение их всех)!
whuber