AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

Ein Thema von Jazzman_Marburg · begonnen am 27. Dez 2011 · letzter Beitrag vom 31. Dez 2011
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von Jazzman_Marburg
Jazzman_Marburg

Registriert seit: 2. Aug 2004
359 Beiträge
 
#1

Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 27. Dez 2011, 13:39
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
Miniaturansicht angehängter Grafiken
doorproblem.png  
--- Delphi XE Starter, Windows 8 ---
  Mit Zitat antworten Zitat
Benutzerbild von fkerber
fkerber
(CodeLib-Manager)

Registriert seit: 9. Jul 2003
Ort: Ensdorf
6.723 Beiträge
 
Delphi XE Professional
 
#2

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 27. Dez 2011, 14:00
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
Frederic Kerber
  Mit Zitat antworten Zitat
Benutzerbild von Jazzman_Marburg
Jazzman_Marburg

Registriert seit: 2. Aug 2004
359 Beiträge
 
#3

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 27. Dez 2011, 16:01
Außenwände zu finden ist ja kein Problem, daher klammere ich die einfach mal aus.
Ja.
Generell ist der Wunsch doch, in jeden Wandabschnitt genau mittig eine Tür reinzubekommen, richtig?
Ja.
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
Miniaturansicht angehängter Grafiken
doorproblem.png  
--- Delphi XE Starter, Windows 8 ---
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.509 Beiträge
 
Delphi 11 Alexandria
 
#4

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 27. Dez 2011, 16:11
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.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list

Geändert von himitsu (27. Dez 2011 um 16:17 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Jazzman_Marburg
Jazzman_Marburg

Registriert seit: 2. Aug 2004
359 Beiträge
 
#5

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 27. Dez 2011, 16:18
Das werde ich mal ausprobieren!

Dankeschön

Gruß
Jazzman
--- Delphi XE Starter, Windows 8 ---
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.509 Beiträge
 
Delphi 11 Alexandria
 
#6

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 27. Dez 2011, 16:24
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
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.289 Beiträge
 
Delphi 10.4 Sydney
 
#7

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 27. Dez 2011, 19:51
Evtl. könnte man rel. einfach mit IntersectRect auf Überschneidungen der Rechtecke prüfen (jedes mit jedem).
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#8

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 28. Dez 2011, 09:11
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;
  Mit Zitat antworten Zitat
Angel4585

Registriert seit: 4. Okt 2005
Ort: i.d.N.v. Freiburg im Breisgau
2.199 Beiträge
 
Delphi 2010 Professional
 
#9

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 28. Dez 2011, 09:40
Haben die Türen eine fixe Breite? Was wenn die Wand zwischen zwei Räumen kleiner ist?
Also so versetzte Räume quasi
Martin Weber
Ich bin ein Rüsselmops
  Mit Zitat antworten Zitat
Benutzerbild von Jazzman_Marburg
Jazzman_Marburg

Registriert seit: 2. Aug 2004
359 Beiträge
 
#10

AW: Zwischen-den-Jahren-Kopfnuss: Hilfe zum Algorithmus

  Alt 28. Dez 2011, 10:09
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.

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
--- Delphi XE Starter, Windows 8 ---
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 10:41 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf