Ermitteln Sie den nächsten freien Satz von X / Y-Koordinaten in einem immer größer werdenden 2D-Gitter, das in MySQL gespeichert ist
Ich habe eine sehr einfache MySQL-Tabelle, in der X- und Y-Koordinaten für Kacheln innerhalb eines Gitters gespeichert sind. Die Mitte des Gitters ist 0,0 und Kacheln können in jeder Richtung erstellt werden. Wenn die Koordinaten in der MySQL-Tabelle vorhanden sind, gelten sie als "übernommen".
%Vor%Ich muss einen Satz von 4 Kacheln (als ein Quadrat, kein Rechteck) in das Gitter in der nächstmöglichen Position zu 0,0 platzieren.
Zur Veranschaulichung - die grünen Kacheln darunter müssten gefunden werden.
Leider bin ich mir nicht einmal sicher, wo ich anfangen soll: (
3 Antworten
Hier ist eine Single-Query-Lösung.
Für jedes gegebene Quadrat t auf dem Gitter können wir 8 mögliche 4-quadratische Kacheln um es herum identifizieren, die leer sein können:
Wenn keine der 4 möglichen Kacheln mit (0,0) verfügbar ist, muss die nächstgelegene verfügbare Kachel (0,0) an ein vorhandenes Quadrat angrenzen (da für jede verfügbare Kachel nicht eine bereits vorhandene verwendet wird) Quadrat, können wir eine verfügbare Kachel finden, die näher ist).
Das bedeutet, dass wir eine Abfrage über die genommenen Quadrate konstruieren können, um mögliche verfügbare Kacheln zu berechnen.
Um zu überprüfen, ob wir eine verfügbare Kachel neben dem Quadrat t haben, können wir eine Abfrage wie die folgende verwenden:
%Vor% Dies bestimmt die linken, oberen, rechten und unteren Koordinaten sowie die Manhattan-Entfernung von (0,0) der verfügbaren Kacheln in der t1 -Position relativ zu den genommenen Quadraten.
Als nächstes brauchen wir eine Vereinigung der verfügbaren Kacheln in allen 8 Positionen. Wir müssen auch nach den 4 möglicherweise verfügbaren Kacheln suchen, die (0,0) enthalten, da sie nicht notwendigerweise an ein vorhandenes Quadrat angrenzen.
%Vor% Der Kürze halber habe ich x und y anstelle von position_x und position_y verwendet. Ich habe UNION ALL für Geschwindigkeit verwendet, da es vermeidet, nach doppelten Zeilen zu suchen, wir brauchen nur eine Zeile. Eine andere Optimierung besteht darin, nur nach Kacheln rechts von t zu suchen, wobei x & gt; = 0, unter t , wo y & gt; = 0 ist, und so weiter. Indizes für die Spalten x und y sollten für die Leistung entscheidend sein.
Ich habe es mit Ihrem Beispielraster getestet:
%Vor%Da die Logik ziemlich kompliziert ist, werde ich keine eindeutige SQL-Anweisung versuchen; Ich werde stattdessen Hilfstabellen verwenden. Natürlich können diese bei Bedarf durch abgeleitete Tabellen ersetzt werden.
Nehmen wir an, wir haben eine Tabelle numbers mit den Werten 0, 1, 2, 3, ... (groß genug).
Hieraus wird eine Tabelle points eingefügt. Diese Tabelle enthält das gesamte Gitter (oder zumindest eine ausreichend große rechteckige Teilmenge davon, die den Punkt (0,0) enthält).
Als nächstes berechne alle möglichen 2x2 Quadrate:
%Vor%Schließlich findet diese Abfrage alle leeren Quadrate und sortiert sie nach der Summe ihrer Punkte Entfernung von (0,0). Wenn das Ergebnis auf 1 begrenzt wird, wird das "beste" Quadrat zurückgegeben:
%Vor% Ihre Originaldaten befinden sich in der Tabelle t :
Die folgende SQL berechnet und legt die leeren Kacheln zuerst in eine neue Tabelle.
Dieses Gitter ist auf die niedrigsten und höchsten Punkte der schwarzen Steine beschränkt.
Plus eine Marge von 2 Fliesen für ein gutes Maß.
Aus diesen leeren Kacheln werden die quadratischen Blöcke über innere Joins berechnet.
Denn wenn ein innerer Join nicht mit einer Kachel verknüpft ist, die nicht in der Tabelle enthalten ist, dann wäre es sowieso kein leerer quadratischer Block.
Der Block mit dem niedrigsten Abstand zu (0,0) wird aufgrund der Reihenfolge nach oben gewählt, also gewählt.
Ergebnis:
%Vor%Eine Demo finden Sie hier auf Rextester.
Und hier ist eine MS SQL Server Version.
Mit rekursivem SQL und CTEs ist es dann möglich, dies in einer einzigen Abfrage zu tun.