Freien Platz in einer Fläche finden

[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.