Methode zum Finden von benachbarten "Ländern"

Hallo zusammen.

Ich stehe vor einem Problem, bei dem ich nicht weiss, wie ich anfangen soll.
Gegeben ist eine Landkarte, weißer Hintergrund, Ländergrenzen in schwarz(umrandet).
Nun soll daraus eine Liste von Ländern erstellt werden, IDs erzeugt und deren Nachbarschaften festgehalten werden.

Ich habe mittels einer selbstgeschriebenen FloodFill-Methode bereits die Länder zuverlässig markiert und in eine Liste gespechert. Nun habe ich eine Karte mit bunten Ländern, jeweils einzigartige Farben für jedes Land. Die Landesgrenzen sind weiterhin schwarz (2px breit). So gehts m.E. nach:

int r=0,g=0,b=0 ;
   TColor farbe;
   int x = 2,y =2;
   LandNeu* neuesLand;

   for (int x=2; x<Bild->Width-2; x++)
   {
      for (int y=2; y<Bild->Height-2; y++)
      {
         if (Bild->Picture->Bitmap->Canvas->Pixels[x][y] == clWhite)
         {
            neuesLand = new LandNeu();

            r = random(255);
            g = random(255);
            b = random(255);
            farbe = RGB(r,g,b);

            flaecheFuellen(x,y, clWhite, farbe, neuesLand);

            neuesLand->setID(farbe);
            laenderliste->Add(neuesLand);
      }
   }

Hier die eigene FloodFill-Methode:

void TForm1::flaecheFuellen(int x, int y, TColor alteFarbe, TColor neueFarbe, LandNeu* land)
{
  if (Bild->Picture->Bitmap->Canvas->Pixels[x][y] == alteFarbe)
  {
     Bild->Picture->Bitmap->Canvas->Pixels[x][y] = neueFarbe;
     //rueck.koordinaten += IntToStr(x) + "/" + IntToStr(y) + ";";
     //rueck.anzahlPixel++;
     TPoint* neuerPunkt = new TPoint();
     neuerPunkt->x = x; neuerPunkt->y = y;
     land->koordinateHinzufuegen(neuerPunkt);
     land->groesseVergroessern();
     flaecheFuellen(x, y + 1, alteFarbe, neueFarbe, land); // unten
     flaecheFuellen(x - 1, y, alteFarbe, neueFarbe, land); // links
     flaecheFuellen(x, y - 1, alteFarbe, neueFarbe, land); // oben
     flaecheFuellen(x + 1, y, alteFarbe, neueFarbe, land); // rechts
  }
  return;
}

Wie ich deren Nachbarländer identifizieren soll, weiss ich jedoch absolut nicht.
Meine Idee war, für jede gespeicherte Koordinate innerhalb jeden Landes eine geschachtelte "for-Schleife" zu durchlaufen und zu prüfen, ob der Pixel die Farbe des Ausgangslandes hat. Wenn nicht, habe ich ein Nachbar gefunden.
Nachteil: Ich weiss nicht, an welcher Stelle ich dann das Schleifenkonstrukt abbrechen muss und performant ist mit Abstand was anderes...

Kann mir jemand einen tollen Tipp geben?
Bevor jemand fragt - ja, ich habe gesucht. Aber ich wurde nicht wirklich fündig.

Danke im Voraus,

Oliver

audacia

Ich würde den Floodfill nicht mit Rekursion, sondern lieber mit einer Stack- oder Queue-Struktur implementieren. Auch wenn der Stack für die meisten Fälle groß genug ist, würde ich's nicht riskieren: ein Stack-Overflow ist weitaus kritischer als ein Out-of-memory-Error bei Heap-Allokation.

Was dein Problem anbelangt, so würde ich nach dem Erfassen deines "Staatsgebietes" die Ländergrenze bereisen; etwa so:
- Du suchst, von irgendeinem Punkt deines Staatsgebietes ausgehend, eine Ländergrenze auf, indem du einfach in irgendeine Richtung losmarschierst.
- Von dort aus gehst du am Rand entlang, schaust, zu welchem Land der nächste weiße Pixel auf der anderen Seite der Grenze gehört, und merkst dir dessen ID.
- Wenn während deines Grenzmarsches ein benachbarter Pixel einem anderen Land angehört, mußt du an einem Dreiländereck vorbeigekommen sein; dann speicherst du das Land, dessen ID du dir gemerkt hast, als bekanntes Nachbarland ab und merkst dir die ID des nächsten Nachbarn.
- So verfährst du, bis du wieder am Ausgangspunkt ankommst.

Übrigens ist der Zugriff mit TCanvas::Pixels[][] vergleichsweise langsam; ich würde TBitmap::ScanLine benutzen.

Vielleicht sähe sich ein Moderator geneigt, den Thread nach "Rund um die Programmierung" zu verschieben, da das Problem nicht C++Builder-spezifisch ist.

C++ Forumbot

Dieser Thread wurde von Moderator/in akari aus dem Forum VCL (C++ Builder) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

knivil

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

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

Oliver

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

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.

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

Methode zum Finden von benachbarten &quot;Ländern&quot;

Methode zum Finden von benachbarten "Ländern"