Wie lässt sich ein nicht kollidierendes Rechteck finden, das einem Ort am nächsten liegt?

Question

Für ein 2D-Spiel, an dem ich arbeite, verwende ich die Sortierung der Y-Achse in einer einfachen, auf Rechtecken basierenden Kollisionserkennung. Das funktioniert gut, und jetzt möchte ich die nächstgelegene ein leeres Rechteck an einer bestimmten Stelle mit einer bestimmten Größe effizient zu erstellen. Wie kann ich dies tun? Gibt es einen Algorithmus?

Ich könnte mir einen einfachen Brute-Force-Gittertest vorstellen (wobei jedes Gitter die Größe der gesuchten Leerstelle hat), aber das ist natürlich langsam und nicht einmal ein vollständiger Test.

Answer 1

Erwägen Sie die Verwendung von Quad-Trees zum Speichern Ihrer Rechtecke. Siehe http://en.wikipedia.org/wiki/Quadtree für weitere Informationen.

Answer 2

Wenn Sie bereits die Achsensortierung verwenden, haben Sie vermutlich eine Liste Ihrer Rechtecke berechnet, die nach ihren Positionen sortiert sind.

Vielleicht verstehe ich das falsch, aber könnten Sie nicht einfach die beiden Rechtecke vor und nach dem fraglichen Rechteck betrachten und dann entscheiden, welches näher ist? Wenn es darum geht, das Rechteck zu finden, das einem beliebigen Punkt am nächsten liegt, könnten Sie einfach die Liste durchgehen, bis Sie das erste Rechteck finden, das weiter entfernt ist als Ihr beliebiger Punkt, und dieses und das davor liegende Rechteck zum Vergleich verwenden.