Freien Platz in einer Fläche finden

[BlueStarHH]

Hallo,

ich habe eine Fläche, die durch ein TRect definiert ist (Flaeche: TRect). Auf dieser Fläche liegen viele andere TRect's (Belegt: array of TRect). Ich möchte nun wissen, wo ein freier Platz für das Rect "PlatzFuer" vorhanden ist. "PlatzFuer" darf keine TRect's aus "Belegt" berühren und muss such vollständig in "Flaeche" befinden. Die Suche soll von unten nach oben in "Flaeche" ausgeführt werden. Die X,Y-Koordinate der freien Fläche soll zurückgegeben werden. Gibt es dafür einen fertigen Algorithmus? Hat jemand eine Idee, wie man das besser (schneller) hinbekommt, als alle möglichen X,Y-Koordinaten einfach durchzutesten?

Delphi-Quellcode:

function FindeFreienPlatz(Flaeche, PlatzFuer: TRect; Belegt: array of TRect): TPoint;
begin
  ...
end;

[Uwe Raabe]

Nur so aus dem Ärmel: Du beginnst mit (0,0) und prüfst sequentiell alle anderen Rechtecke auf Kollision. Sobald du eins findest hast du zwei Möglichkeiten: rechts davon oder darunter. Mit diesen neuen Koordinaten wiederholst du den Test. Dabei entsteht ein binärer Baum (wegen rechts/darunter), den du entsprechend durchwanderst. Entweder immer erst rechts prüfen und dann darunter oder umgekehrt. Wenn du auf keinem Weg durch den Baum erfolgreich bist, passt das neue Rechteck nicht mehr in deine Fläche.

Ich habe das Verfahren jetzt nicht validiert. Es kann also durchaus sein, dass gültige Positionen gar nicht überprüft werden.

[Medium]

Soweit meine kurze Recherche und Gedankenmacherei führen, sieht das nach einem NP-schweren Problem aus, insbesondere wenn man die optimale Platzierung sucht. (Optimal im Sinne von: Es bleibt möglichst wenig Platz zu den umgebenden Rechtecken. Es gibt natürlich auch andere Metriken für "optimal", je nach dem was du gerade brauchst.)

Für den allgemeinen Fall, wie du ihn beschreibst, sehe ich erstmal keine wirklich bessere bzw. einfachere Lösung als Pixel für Pixel durchzugehen. (RICHTIG hart wird es, wenn man ein vorgegebenes Set von Rechtecken in ein großes einpassen will. Also alle sind "beweglich". Da bewegt man sich dann schon in ziemlich abgefahrenen Sphären der Mathematik.)

[stahli]

Ich habe mal etwas ähnliches umgesetzt.
Vielleicht hilft Dir das irgendwie als Anregung: https://www.delphipraxis.net/165177-scrollboxflow.html

Für meine Zwecke hat das gut funktioniert, aber ob es für Dich taugt, weiß ich natürlich nicht.

[himitsu]

Dahinter versteckt sich ein nettes Problemchen der Menschheit, wo schon seit Äonen unzählige Jahre an Forschung draufgegangen sind.

https://de.wikipedia.org/wiki/Verschnittplanung


Für dich wird wohl Bruteforce erstmal die einfache Lösung sein.
In deinem Fall gibt es nur eine "kleine" Menge an Pixeln, die du leicht halbwegs schnell durchprobieren kannst.
Imr TRect gibt es da bereits eine fertige Prüffunktion
TRect.Overlaps

Das ließe sich noch optimieren, denn im Prinzip brauchst erstmal nur im Raster von je einer ganzen Kantenlänge zu prüfen, ob dort nichts ist,
TRect.Contains / PtInRect
und wenn nicht, dann nur noch im Umkreis der halben Kantenlänge schauen, ob es eine Stelle ohne Überschneidungen gibt.
TRect.Overlaps

Maximal in zwei Prüfungen/Durchläufen, falls du ebenfalls nochmals um 90% gedreht nachsehn willst.



Ansonsten gibt es zu dem kleinen Problemchen auch schon ein paar halbwegs nutzbare Lösungsansätze, von einfach bis extrem komplex und rechenintensiv.



Wenn ein festes Raster gegeben ist (z.B. 1 oder mehrere x Pixel) und die Rechtecke alle gleich groß oder ein kleineres Vielfaches des Rasters groß sind, dann kann es ganz einfach werden,
wobei Bruteforce auch dann immernoch extrem schnell sein kann.

[BlueStarHH]

Danke an alle für die Ideen!