Hallo allerseits,

ich stehe gerade vor einem kleinen Problem und komme nicht mehr weiter. Gegeben ist ein zweidimensionales int-Array variabler Größe mit den Werten 0 und 1. Ziel ist es nun zusammenhängende Gebiete aus 0en und 1en zu finden.

Beispiel:

Code :

1 2 3 4 5

int[][] entry = {             {1,0,0},             {1,1,1},             {0,0,0}                     };

Als Ergebnis würde hier in etwa Folgendes erwartet:

Code :

1 2 3 4 5 6 7 8

int[][][] zero= {             {{0,1},{0,2}},             {{2,0},{2,1},{2,2}}                     };   int[][][] one= {             {{0,0},{0,1},{1,1},{2,1}}                   };

Gibt es Algorithmen o.ä. die das effizient machen können bzw. kann mir jemand dabei helfen?

Gruß,
Trench

Koordinaten werden oftmals in einem http://en.wikipedia.org/wiki/R-tree gehalten zur effizienteren spartialen Suche vorgehalten. Allerdings scheint das für deine Aufgabe mit Kanonen auf Spatzen geschossen?

Hallo,

such mal nach den Begriffen strongly Connected Components bzw. starke Zusammenhangskomponenten.

Schau mal hier:
http://en.wikipedia.org/wiki/Connect...raph_theory%29
http://de.wikipedia.org/wiki/Algorit...ngskomponenten

Gruß Tom

Zitat von Thomas Darimont

such mal nach den Begriffen strongly Connected Components bzw. starke Zusammenhangskomponenten.

Wenn ich das Problem richtig verstanden habe, muss man nur die Zusammenhangskomponenten in einem ungerichteten Graphen bestimmen. Dazu reicht eine einfache Breiten- oder Tiefensuche.

Grüße,
Matthias

Hallo,

Matthias hat natürlich recht
Schau mal hier ab Seite 47:
http://www.cs.princeton.edu/~rs/Algs...ctedGraphs.pdf

Gruß Tom

Hallo allerseits,

entschuldigt, dass ich mich erst jetzt melde. Die Idee mit den Graphen werde ich mir mal genauer anschauen, das was ich bis jetzt gelesen habe sieht schonmal vielversprechend aus, vielen Dank