Zamazany najmniej zgrubny wspólny algorytm partycji

Biorąc pod uwagę dwie różne partycje kształtu (ze względu na argument, dwa różne podziały administracyjne kraju), jak mogę znaleźć nową partycję, w której pasują obie te partycje, dopuszczając (i optymalizując) jakiś błąd?

Na przykład ignorując błąd, chcę algorytm, który to robi:

Być może pomaga to wyrazić w ustalonych terminach. Używając następującej numeracji:

Mogę wyrazić powyższe partycje jako:

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}}

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

a algorytm do tworzenia kropki B wydaje się prosty (coś w stylu, jeśli dwa elementy znajdują się w partycji razem w A (B) łączą partycje, w których się znajdują w B (A) - powtarzaj, aż A i B będą równe).

Ale teraz wyobraź sobie, że niektóre z tych linii różnią się nieznacznie między dwiema partycjami, więc ta idealna odpowiedź nie jest możliwa, a zamiast tego chcę optymalnej odpowiedzi z zastrzeżeniem zminimalizowania pewnego kryterium błędu.

Weź nowy przykład:

Tutaj w lewej kolumnie mamy dwie partycje bez wspólnych linii (poza samą zewnętrzną ramką). Jedynym możliwym rozwiązaniem tego rodzaju jest trywialne, prawa kolumna. Ale jeśli pozwolimy na rozwiązania „rozmyte”, wówczas środkowa kolumna może być dopuszczalna, powiedzmy, że 5% całkowitej powierzchni jest kwestionowane (tj. Przydzielone do innego podobszaru w każdej zgrubnej partycji). Możemy więc opisać środkową kolumnę jako reprezentującą „najmniej zgrubną wspólną partycję z błędem <= 5%”.

Niezależnie od tego, czy rzeczywistą odpowiedzią jest podział w górnym rzędzie, środkowej kolumnie czy środkowym rzędzie, środkowej kolumnie - czy coś pomiędzy, jest mniej ważne.

Możesz to zrobić, oceniając różnicę granicy wielokąta względem symetrycznej różnicy między ich granicami lub wyrażonej symbolicznie jako:

Difference(a, SymDifference(a, b))

Weź geometrie a i b , wyrażone jako MultiLinestrings przez kolejne dwa wiersze i obrazy:

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))

Różnica symetryczna, gdzie porcje i b nie przecinają się, to:

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))

Na koniec oceń różnicę między a lub b a różnicą symetryczną:

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))

Możesz zaimplementować tę logikę w GEOS (Shapely, PostGIS itp.), JTS i innych. Zauważ, że jeśli geometriami wejściowymi są wielokąty, wówczas ich granice należy wyodrębnić, a wynik można poligonizować. Na przykład pokazano za pomocą PostGIS, weź dwa MultiPolygon i uzyskaj wynik MultiPolygon:

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)))

Zauważ, że nie testowałem dokładnie tej metody, więc weź je jako pomysły jako punkt wyjścia.

Algorytm bez błędów.

Pierwszy zestaw: Drugi zestaw:

Scal 2 zestawy i sortuj w kolejności malejącej według obszaru. Wybierz wiersze w tabeli (góra => dół), aż suma obszarów = całkowity obszar (w tym przypadku 16):

Wybrane wiersze stanowią odpowiedź:

Kryteria będą stanowić różnicę między skumulowanymi obszarami a rzeczywistą sumą.