Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

[Jazzman_Marburg]

Hallo Gemeinde!
Frohe Feiertage und so

Vielleicht hat ja jemand Zeit und Lust neben Lebkuchen und Gans beim folgendem Problemchen behilflich zu sein:
Ich habe da einen feinen Algorithmus, der mir ein Rechteck (Grundrechteck) in beliebig viele kleinere Rechtecke (ohne Überlappung -- "zero waste") unterteilt (mit Beachtung von Seiten- und Flächen Restriktionen). Das funktionert super und das Ergebnis sieht nun wie ein Grundriss einer Wohnung aus. Mein Problem: Ich hätte gern Türen zwischen benachbarten Räumen. Die anhängende PNG-Datei macht das Problem hoffentlich klarer.
Ich habe also nach der Raum-Generierung ein Rechteck-Array vom Typ TRechteck, der für jeden Raum folgende Angaben enthält:
- Fläche, Länge, Breite, XPos und YPos
Nun wird es schwierig: Ich denke, ich müßte nun durch das Rechteck-Array laufen, um benachbarte Räume zu identifizieren. Ich vermute in der daraus folgenden zweidimensionalen "Ist-Nachbar-von-Matrix" würde dann für jede Raumkobination stehen:
- 1 (Nachbar Nordwand) oder
- 2 (Nachbar Westwand) oder
... etc. stehen.
Anschließend würde ich durch diese Matrix laufen und die Türen entsprechend setzen.

Ich bin mir aber nicht sicher ob das überhaupt eine gute Idee ist (mir verbiegt sich das Hirn bei der Vorstellung: Ich müßte dann ja die Räume nach iregendeinem Kriterium sortieren, die Lage der Tür ist ja wichtig, sonst setze ich die Tür für einen Raum mittig in seiner vertikalen Wand, aber dann kommt nocht ein kleiner Nachbarraum und dann sitzt doch die Tür an falscher Stelle oder so). Naja, und Außenwände sollten garkeine Tür haben.

Falls das ich das Problem auch nur Ansatzweise klar geschildert habe, würde ich mich über Kommentare/Ideen oder gar Lösungen sehr freuen.

Vielen Dank vorab
Gruß
Jazzman

[fkerber]

Hi,

nur mal so ins Unreine - bin mir nicht so sicher, ob es das Problem besser oder schlechter lösbar macht

Außenwände zu finden ist ja kein Problem, daher klammere ich die einfach mal aus.
Generell ist der Wunsch doch, in jeden Wandabschnitt genau mittig eine Tür reinzubekommen, richtig?
Also bliebe ja nur das Problem, die Schnittpunkt der horizontalen und vertikalen Wände zu finden, damit du tatsächlich Wandabschnitte hast.

Das wiederum klingt dann für mich nach einem Fall für: http://de.wikipedia.org/wiki/Sweep_%28Informatik%29


LG, Frederic

[Jazzman_Marburg]

Zitat von fkerber:

Außenwände zu finden ist ja kein Problem, daher klammere ich die einfach mal aus.

Ja.

Zitat von fkerber:

Generell ist der Wunsch doch, in jeden Wandabschnitt genau mittig eine Tür reinzubekommen, richtig?

Ja.

Zitat von fkerber:

Also bliebe ja nur das Problem, die Schnittpunkt der horizontalen und vertikalen Wände zu finden, damit du tatsächlich Wandabschnitte hast.

Hmmm

Bleiben wir mal bei dem angefügtem (bessere Grafik angefügt) Beispiel und starten mit dem linken oberen Raum 1:
Raum 1 hat eine Nachbarwand mit einem anderen Raum, wenn seine YPos gleich der YPos eines anderen Raumes ist? Das würde dann aber für Raum 2 und Raum 3 zutreffen -- was ja dann falsch wäre.

Da fangen meine Probleme ja schon an...

Gruß
Jazzman

[himitsu]

rechte Seite eines Raumes (z.B. Raum 1) = linke Seite eines anderen Raumes (hier nur Raum 2) ... daß läßt sich doch leicht prüfen

Unterseite = Oberseite (z.B. Raum 1 = Raum 4 und 5)

Oberseite = Unterseite

linke seite = rechte Seite



Wenn du nun 2 benachbarte Räume hast, dann mußt du nur noch die Tür finden.

Liegt Wand A von Raum A innerhalb von Wand B des Raumes B, dann liegt die Tür in der Mitte der Wand A. (z.B. A = Raum 2 und B = Raum 5)
Liegt Wand B von Raum B innerhalb von Wand A des Raumes A, dann liegt die Tür in der Mitte der Wand B. (z.B. A = Raum 4 und B = Raum 1)
Überschneiden sich die Wände (siehe Raum 1 und 5), dann brauchst du die Ecken, innerhalb der Schnittmenge. (Ecke von Raum 5 innerhalb der Wand von Raum 1 und Ecke von Raum 1 innerhalb der Wand von Raum 5) Die Tür liegt hier nun zwischen dieses beiden Ecken.

Zusammengefaßt liegt die Tür nun immer zwischen den "inneren" Ecken der benachbarten Räume. (2 Räume > 2 sich berührende Wände > 4 Ecken > 2 innere Ecken > dazischen die Tür)


PS: Ist die Wand, zwischen den 2 inneren Ecken nun schmaler als eine Tür, dann paßt dort vermutlich keine Tür hin.

[Jazzman_Marburg]

Das werde ich mal ausprobieren!

Dankeschön

Gruß
Jazzman

[himitsu]

Du mußt ja einfach nur erstmal die Parallele prüfen.

Rechte Wand von Raum 1 und linke Wand von Raum 2 liegen auf der selben Geraden,
genauso wie die untere Wand von Raum 1 auf einer Geraden liegen, wo auch die oberen Wände von Raum 4 und 5 liegen.

Nun noch die Eckpunkte prüfen, also ob die Wände sich berühren
- linke Ecke/Seite von Raum 4 >= von linke Ecke/Seite von Raum 1 <= rechte Ecke/Seite von Raum 4
und/oder
- linke Ecke/Seite von Raum 4 >= von rechte Ecke/Seite von Raum 1 <= rechte Ecke/Seite von Raum 4

[stahli]

Evtl. könnte man rel. einfach mit IntersectRect auf Überschneidungen der Rechtecke prüfen (jedes mit jedem).

[Furtbichler]

Benachbarte Räume A und B haben ja eine gemeinsame Wand. Also ist
a) A.Xpos + A.Breite = B.Xpos (und A.Ypos + A.Höhe überschneidet sich mit B.Ypos + B.Höhe)
oder
b) A.Ypos + A.Höhe = B.Ypos (und A.Xpos + A.Breite überschneidet sich mit B.Xpos + B.Breite)

Damit kannst Du also eine Liste definieren als: A ist Nachbar von B.

für jeden Eintrag der Liste erzeugst Du eine Tür. Die kann ja nur am rechten oder unteren Rand des Rechteckes A sein.
Du musst nur noch die Mitte des sich überlappenden Bereiches finden. Das ist ja nicht so schwer, denn der überlappende Bereich, also die gemeinsame Wand ist die Schnittmenge der beiden rechten Wand von A mit der linken von B bzw. der unteren Wand von A mit der oberen von B.

Bei der Implementierung würdest du natürlich keine Liste erzeugen, sondern einfach so vorgehen:

Delphi-Quellcode:

For i:=0 to Rechteckliste.Count - 2 do
  For j:=i+1 to Rechteckliste.Count - 1 do
    If IstRechtsvon (RechteckListe[i], RechtEckListe[j]) then
       BaueTuerAnDerRechtenSeiteEin (RechteckListe[i], RechtEckListe[j]) 
    else if IstUnterhalbVon(RechteckListe[i], RechtEckListe[j]) then
       BaueTuerAnDerUnterenSeiteEin (RechteckListe[i], RechtEckListe[j]) 
...
Procedure BaueTuerAnDerRechtenSeiteEin (RechtEck A,B);
Begin
  GemeinsameWand := ErmittleUeberschneidung(A.RechteWand, B.LinkeWand);
  BaueTuerInDieMitte(GemeinsameWand);
End;

[Angel4585]

Haben die Türen eine fixe Breite? Was wenn die Wand zwischen zwei Räumen kleiner ist?
Also so versetzte Räume quasi

[Jazzman_Marburg]

Liebe Leute, ihr seid wirklich klasse

So viele Ideen hätte ich wirklich nicht erwartet -- die Weihnachtsplätzchen haben euch offensichtlich nicht lahmgelegt.
Ich werde mir jetzt erstmal alle Vorschläge genauer anschauen und mal mit rumspielen.

Die Idee von stahli mit IntersectRect die Überschneidung von zwei Rechtecken (ähm. 'Räumen') zu prüfen sieht natürlich verlockend einfach aus.

Furtbichlers Vorschlag habe ich gestern Abend auch schon mal versucht -- vielversprechend, aber irgendwo habe ich da noch einen Fehler drin.

Zitat von Angel4585:

Haben die Türen eine fixe Breite? Was wenn die Wand zwischen zwei Räumen kleiner ist?
Also so versetzte Räume quasi

Ja, auch so ein kleines Nebenproblem: Die Türen sollten eine Mindestbreite haben, ja. Da soll später nämlich ein 'autonomer' Roboter durchfahren können. Das ist das Einsatzgebiet der generierten 'Wohnung'.

Selbstredend auch schönen Dank an Frederic und himitsu.

Lieben Dank für eure Mühe!

Schönen Gruß
Jazzman