Bezüglich 3D verstehe ich gar nicht, warum hier überhaupt so viel debattiert wird? Das Problem ist in 3D doch viel einfacher, als in 2D:
Wenn ein Haus Fenster oder Türen hat, dann muss man nichts anderes tun als bei der Außenwand in Z-Koordinate (von oben nach unten oder umgekehrt) jede x/y Koordinate als Mauerstück zu markieren, die für ein gegebenes z zwar frei, in einem anderen z aber als Mauer bereits markiert ist. Schließlich hat jede Tür, Fenster, Guckloch, Garagenöffnung, ... über oder unter sich wieder ein Mauerstück.
In 3D lässt sich schließlich immer ein Teilstück des Hauses finden, bei dem man den kompletten Grundriss einmal rundherum ablaufen kann. Das ginge nur dann nicht, wenn abgesehen von Fenster und Türen noch andere Löcher auftreten, die für ein gegebenes x/y die komplette z-Dimension freilassen. Etwa wenn eine ganze Wand in einer Ruine einfach eingestürzt ist.
Selbst bei diversen Innenräumen ergeben sich nur mehrere Wege, wobei aber der Weg mit größtmöglichem innerem Volumen stets die korrekte Lösung darstellt.
Bezüglich 2D würde ich ebenfalls einen Algorithmus wählen, der direkt auf der gegebenen Struktur arbeitet, das liefert genauere Ergebnisse als Closing/Opening.
Da bisher von einem Grundriss (also einem Haus?) ausgegangen wird, kann man den Ansatz von @blöderidiot auch noch einfacher gestalten, ein komplettes sortieren der Teilstücke ist in diesem Fall nämlich gar nicht nötig:
* man sucht einen beliebigen Mauer-Startpunkt
* man initialisiert für jedes Mauer-Teilstück eine Liste
* man läuft in der gegebenen Anfangsmatrix entweder immer aufsteigend oder immer absteigend in beiden Dimensionen die Nachbarn ab, bis man ein Ende des Mauer-Teilstücks gefunden hat
* nun fügt man der Liste sequentiell alle Punkte des Mauer-Teilstücks hinzu
* wiederholen für jedes Teilstück
Als Ergebnis hat man Anfangs- und Endpunkt jedes Mauer-Teilstücks sowie die dazugehörigen Punkte dazwischen markiert.
Für ein T-Stück, um das noch offensichtlich zu erwähnen, man schlicht zwei verschiedene Listen anlegen, eine für jede Abzweigung: die Endstücke würden nie fälschlicherweise miteinander verbunden, da sie bei einem T-Stück eine hohe euklidische Distanz zueinander aufweisen.
Nun muss man nur noch für jeden Anfangs- und Endpunkt in jeder Liste feststellen, ob in geringer euklidischer Distanz ein anderer Punkt aufzufinden ist.
Eine Kurve, ein "Schlenker", ein U-Abschnitt in einer Mauer o.Ä. würde so nie zu "false positives" führen, weil nur zwischen Anfangs- und Endpunkten gesucht wird, nicht aber zwischen allen Punkten.
Wenn ein Haus Fenster oder Türen hat, dann muss man nichts anderes tun als bei der Außenwand in Z-Koordinate (von oben nach unten oder umgekehrt) jede x/y Koordinate als Mauerstück zu markieren, die für ein gegebenes z zwar frei, in einem anderen z aber als Mauer bereits markiert ist. Schließlich hat jede Tür, Fenster, Guckloch, Garagenöffnung, ... über oder unter sich wieder ein Mauerstück.
In 3D lässt sich schließlich immer ein Teilstück des Hauses finden, bei dem man den kompletten Grundriss einmal rundherum ablaufen kann. Das ginge nur dann nicht, wenn abgesehen von Fenster und Türen noch andere Löcher auftreten, die für ein gegebenes x/y die komplette z-Dimension freilassen. Etwa wenn eine ganze Wand in einer Ruine einfach eingestürzt ist.
Selbst bei diversen Innenräumen ergeben sich nur mehrere Wege, wobei aber der Weg mit größtmöglichem innerem Volumen stets die korrekte Lösung darstellt.
Bezüglich 2D würde ich ebenfalls einen Algorithmus wählen, der direkt auf der gegebenen Struktur arbeitet, das liefert genauere Ergebnisse als Closing/Opening.
Da bisher von einem Grundriss (also einem Haus?) ausgegangen wird, kann man den Ansatz von @blöderidiot auch noch einfacher gestalten, ein komplettes sortieren der Teilstücke ist in diesem Fall nämlich gar nicht nötig:
* man sucht einen beliebigen Mauer-Startpunkt
* man initialisiert für jedes Mauer-Teilstück eine Liste
* man läuft in der gegebenen Anfangsmatrix entweder immer aufsteigend oder immer absteigend in beiden Dimensionen die Nachbarn ab, bis man ein Ende des Mauer-Teilstücks gefunden hat
* nun fügt man der Liste sequentiell alle Punkte des Mauer-Teilstücks hinzu
* wiederholen für jedes Teilstück
Als Ergebnis hat man Anfangs- und Endpunkt jedes Mauer-Teilstücks sowie die dazugehörigen Punkte dazwischen markiert.
Für ein T-Stück, um das noch offensichtlich zu erwähnen, man schlicht zwei verschiedene Listen anlegen, eine für jede Abzweigung: die Endstücke würden nie fälschlicherweise miteinander verbunden, da sie bei einem T-Stück eine hohe euklidische Distanz zueinander aufweisen.
Nun muss man nur noch für jeden Anfangs- und Endpunkt in jeder Liste feststellen, ob in geringer euklidischer Distanz ein anderer Punkt aufzufinden ist.
Eine Kurve, ein "Schlenker", ein U-Abschnitt in einer Mauer o.Ä. würde so nie zu "false positives" führen, weil nur zwischen Anfangs- und Endpunkten gesucht wird, nicht aber zwischen allen Punkten.
Zuletzt bearbeitet:
