Fuzzy-Algorithmus für die am wenigsten grobe gemeinsame Partition

Wie kann ich bei zwei verschiedenen Partitionen einer Form (aus Gründen der Argumentation zwei verschiedene administrative Abteilungen eines Landes) eine neue Partition finden, in die beide Partitionen passen, um Fehler zuzulassen (und zu optimieren)?

Wenn ich zum Beispiel den Fehler ignoriere, möchte ich einen Algorithmus, der dies tut:

Vielleicht hilft es, dies in festgelegten Begriffen auszudrücken. Verwenden Sie die folgende Nummerierung:

Ich kann die obigen Partitionen wie folgt ausdrücken:

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

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

und der Algorithmus zum Erzeugen von A-Punkt B scheint unkompliziert zu sein (so etwas wie, wenn zwei Elemente in einer Partition in A (B) zusammengeführt werden, die Partitionen, in denen sie sich in B (A) befinden, zusammenführen - wiederholen, bis A und B gleich sind).

Stellen Sie sich nun vor, dass einige dieser Zeilen zwischen den beiden Partitionen geringfügig voneinander abweichen, sodass diese perfekte Antwort nicht möglich ist. Stattdessen möchte ich die optimale Antwort, sofern ein Fehlerkriterium minimiert wird.

Nehmen Sie ein neues Beispiel:

Hier in der linken Spalte haben wir zwei Partitionen ohne gemeinsame Linien (abgesehen vom äußeren Rand selbst). Die einzig mögliche Lösung der oben genannten Art ist die triviale, die rechte Spalte. Wenn wir jedoch "unscharfe" Lösungen zulassen, ist möglicherweise die mittlere Spalte zulässig, wobei beispielsweise 5% der Gesamtfläche angefochten werden (dh in jeder vergröberten Partition einem anderen Teilbereich zugeordnet sind). Wir könnten also die mittlere Spalte als die "am wenigsten grobe gemeinsame Partition mit <= 5% Fehler" beschreiben.

Ob die eigentliche Antwort dann die Partition in der oberen Zeile, mittleren Spalte oder mittleren Zeile, mittleren Spalte - oder etwas dazwischen - ist, ist weniger wichtig.

Sie können dies tun, indem Sie die Differenz der Grenze eines Polygons zur symmetrischen Differenz zwischen ihren Grenzen auswerten oder symbolisch ausgedrückt als:

Difference(a, SymDifference(a, b))

Nehmen Sie die Geometrien a und b , ausgedrückt als MultiLinestrings, über die nächsten beiden Linien und Bilder:

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

Der symmetrische Unterschied, bei dem sich Teile von a und b nicht schneiden, ist:

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

Und schließlich bewerten Sie den Unterschied zwischen a oder b und den symmetrischen Unterschied:

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

Sie können diese Logik in GEOS (Shapely, PostGIS usw.), JTS und anderen implementieren. Beachten Sie, dass wenn die Eingabegeometrien Polygone sind, ihre Grenzen extrahiert werden müssen und das Ergebnis polygonisiert werden kann. Nehmen Sie beispielsweise mit PostGIS zwei MultiPolygons und erhalten Sie ein MultiPolygon-Ergebnis:

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

Beachten Sie, dass ich diese Methode nicht ausführlich getestet habe. Nehmen Sie diese als Ideen als Ausgangspunkt.

Fehlerfreier Algorithmus.

Erster Satz: Zweiter Satz:

Füge 2 Sätze zusammen und sortiere in absteigender Reihenfolge nach Bereich. Wählen Sie die Zeilen in der Tabelle aus (oben => unten), bis die Gesamtzahl der Flächen = Gesamtfläche (in diesem Fall 16) erreicht ist:

Ausgewählte Zeilen geben Ihre Antwort:

Das Kriterium wird ein Unterschied zwischen den angesammelten Flächen und der tatsächlichen Gesamtsumme sein.