Учитывая два разных раздела формы (ради аргумента, два разных административных деления страны), как мне найти новый раздел, в который вписываются оба этих раздела, допускающий (и оптимизирующий) некоторую ошибку?
Например, игнорируя ошибку, я хочу алгоритм, который делает это:
Возможно, это поможет выразить это в установленные сроки. Используя следующую нумерацию:
Я могу выразить разделы выше как:
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%».
Независимо от того, является ли фактический ответ разделом в верхнем ряду, среднем столбце или среднем ряду, среднем столбце - или чем-то промежуточным, менее важно.
Ответы:
Вы можете сделать это, оценивая разницу границ многоугольника с симметричной разницей между их границами или символически выраженную в виде:
Возьмем геометрию a и b , выраженную в виде нескольких строк для следующих двух строк и изображений:
Симметричная разность, где части a и b не пересекаются, составляет:
И, наконец, оцените разницу между a или b и симметричной разностью:
Вы можете реализовать эту логику в GEOS (Shapely, PostGIS и т. Д.), JTS и других. Обратите внимание, что если входные геометрии являются полигонами, то их границы должны быть извлечены, и результат может быть полигонизирован. Например, показано с помощью PostGIS, возьмите два мультиполигона и получите результат мультиполигона:
Обратите внимание, что я не тестировал этот метод всесторонне, поэтому примите его как отправную точку.
источник
Алгоритм без ошибок.
Первый набор: второй набор:
Объединить 2 комплекта и отсортировать в порядке убывания по площади. Выбирайте строки в таблице (сверху => вниз), пока не будет достигнуто общее количество областей = общая площадь (в данном случае 16):
Выбранные строки делают ваш ответ:
Критериями будет разница между накопленными площадями и фактическим итогом.
источник