Methode zum Finden von benachbarten "Ländern"

[lustig]

Du hast hier 2 Probleme: Eine Grenze ablaufen und den Nachbarn finden.

Wenn du um ein Land herum läufts kann es vorkommen (das ist bei dir ja meistens so), dass du mehrere Pixel zur Auswahl hast um fortzufahren. Du weisst, von welchem du gekommen bist und solltest dann mit dem Pixel fortfahren, das den minimalen Winkel zum vorherigen hat (je nach dem, wie du die Winkel definierst, gehst du rechts oder links herum):

#
AB#
 #

Du kommst von A nach B. Die Winkel sind:
Oben 90 (oder 270)
Rechts 180
Unten 270 (oder 90)

Wenn du also Links herum gehst, wählst du das Feld oben als nächstes. Das machst du immer so und gehst deshalb am inneren Rand entlang.
Das zweite Problem ist jetzt, die Nachbarfarben zu finden. Da ist es jetzt so, dass sie auch 2 pixel weit entfernt sein können, weil deine Linien 2 Pixel breit sind. Da musst du dir mal überlegen, wie du das am besten machst.

[OliverKohl]

...hat mich zwar weitergebracht, aber in manchen Fällen klappt es m.E. einfach nicht.
leider kann ich kein Bild hochladen, daher ist es etwas schwierig zu beschreiben...
._
/ \______
X |\........|
\/ \___/
Land Land
A B

(Die Punkte dienen nur als Platzhalter)

In diesem - zugegeben sehr einfach skizzierten - Fall laufe ich an Position X los, entscheide mich für den Uhrzeigersinn, laufe nach oben, dann horizontal nach rechts, knicke nach unten ab, doch dann ist der kleinste Winkel 0 - nämlich geradeaus! Schon habe ich die Grenzen von A verlassen und wandle auf B's. Wenn ich "immer wenn möglich abbiege, dann aber mit kleinstem Winkel" klappt es in diesem Fall, generell aber m.E. auch nicht.

Was mache ich falsch?

Oliver

[SeppJ]

Nein. Geradeaus wäre in deinem Beispiel 180 Grad, der Winkel der richtigen Grenze ist kleiner.

edit: Und noch ein Tipp: Code-Tags

_  _____
/ \|    |
X |\    /
\_/ \__/

[Gregor]

Hi.

Ich würde es völlig anders machen.

Ich würde das Bild einmal horizontal Zeile für Zeile durchscannen und einmal vertikal Spalte für Spalte. Und dann würde ich gucken, ob ich eine Pixelkonstellation wie folgende finde:

a
   x     oder     axb
   b

Wobei x eine Ländergrenze ist und a und b jeweils Länder. Wenn so eine Konstellation vorhanden ist, dann sind a und b benachbart. Entsprechend würde ich eine passende Kante in einem dazu gehörenden Graphen erzeugen.

[Gregor]

OliverKohl schrieb:

Ich habe mittels einer selbstgeschriebenen FloodFill-Methode bereits die Länder zuverlässig markiert und in eine Liste gespechert.

Das macht man eigentlich so:

http://en.wikipedia.org/wiki/Connected-component_labeling

Aber gut, Du hast ja schon funktionierenden Code.

[knivil]

Das bringt mich auf die Idee, einfach alle Grenzpixel zu extrahieren. Dann in einer kleinen Umgebung die Laender ansehen. Diese sind dann benachbart.

[SeppJ]

knivil schrieb:

Das bringt mich auf die Idee, einfach alle Grenzpixel zu extrahieren. Dann in einer kleinen Umgebung die Laender ansehen. Diese sind dann benachbart.

Ich fürchte, dann würde Lichtenstein ein Nachbar von Deutschland werden oder Sachsen-Anhalt ein Nachbar von Mecklenburg-Vorpommern.

Oder Colorado ein Nachbar von Arizona, wobei das sowieso eine gute Frage ist, wie man Nachbarn bei einem Vierländereck definiert.

[knivil]

Die kleine Umgebung ist natuerlich entsprechend zu waehlen.

[SeppJ]

knivil schrieb:

Die kleine Umgebung ist natuerlich entsprechend zu waehlen.

Dann musst du sagen, wie. Bei jedem endlichen Abstand kannst du Gegenbeispiele mit nahe aneinander liegenden Dreiländerecken finden. Und unendlich klein geht im Computer nicht. Und auch bei unendlich klein würdest du Probleme mit Vierländerecken bekommen. Wobei man da definieren könnte, dass Diagonale Nachbarn auch benachbart sind, was ich mit [SPD}Bauchschwerzen[/SPD] akzeptieren würde. Das Problem mit den Dreiländerecken besteht aber weiter.

[Bashar]

Bei Pixellandkarten kann man das Problem sowieso nicht exakt lösen.