3. Methode zum Finden von benachbarten "Ländern"

Methode zum Finden von benachbarten "Ländern"

  • K

    Voraussetzung ist, dass Laender zusammenhaengend sind, durch eine zusammenhaengende Grenze eingeschlossen sind und sie sich nicht selbst schneidet:

    Fuer jedes Land x tue:
  - finde einen Punkt der Laendergrenze
  - laufe entlang der Laendergrenze und merke dir jedes angrenzende Land
  - Stoppe, wenn du am gleichen Pixel wieder angekommen bist
  - entferne doppelte Eintraege
    0
  • ?

    Vielen Dank für die Hilfe.
    Ich werde es probieren.

    Oliver

    0
  • ?

    Hallo nochmals,

    ich habe angegebenen Lösungsweg versucht umzusetzen - mit Teilerfolg.
    Ich finde tatsächlich einige Nachbarn, wenn ich einen einzelnen Punkt eine Schrittweite langgehe und die Nachbarn suche.
    Sobald ich aber rekursiv die Methode aufrufe laufe ich regelmäßig in Endlosschleifen, da ich an manchen "Wegpunkten" nicht weiss, wo ich weitergehen soll. Nämlich dort, wo besagte Dreiländerecken sind. Es kann also sein, dass ich die Grenze meines Landes verlasse ohne es zu merken und an einer Grenze des Nachbarlands weiterlaufe...

    Ferner verstehe ich die besagte Einschränkung nicht wirklich "es darf keine sich selbst schneidende Grenze sein". Ist das nicht immer der Fall, wenn mehr als 3 Länder zusammenstoßen? Vielleicht verstehe ich das aber mathematisch auch nicht 😉

    Auch problematisch ist die Grenzbreite von 2 Pixeln, die ein Ablaufen der Grenze recht kompliziert macht...

    Gibt es mehr oder andere Tipps?

    Danke nochmals,

    Oliver

    0
  • L

    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.

    0
  • ?

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

    0
  • Mod

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

    edit: Und noch ein Tipp: Code-Tags

    _  _____
/ \|    |
X |\    /
\_/ \__/
    0
  • G

    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.

    0
  • G

    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.

    0
  • K

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

    0
  • Mod

    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.

    0
  • K

    Die kleine Umgebung ist natuerlich entsprechend zu waehlen.

    0
  • Mod

    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.

    0
  • B

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

    0
Anmelden zum Antworten