Finde Sternbilder in 2D Grid < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:03 Do 14.08.2014 | | Autor: | ThomasTT |
| Aufgabe | | Nimm an du hast eine Liste von (x,y)-Koordinaten. Nun ist die Aufgabe alle Quadrate (schräg oder gerade) zu finden. Zum Beispiel (2 10), (5 11), (1 13), (4 14) ergibt ein Quadrat, das schräg ist, und (5 5), (10 0), (10 5), (5 0) ist ein Quadrat, welches gerade ist. Quadrate können um jedmöglichen Winkel gedreht sein. Optimale Konvergenz: [mm] N^2 [/mm] |
Nehmen wir an wir haben N Koordinaten-Paare. Mein Ansatz ist einen Nx2 Array mit all den (x,y) Koordinaten zu erstellen. Danach schreibe ich eine Schleife, die jeden Punkt durchgeht (von 1 bis N) und in dieser Schleife ist eine weitere die ebenfalls alle Punkte von 1 bis N durchgeht. Mit diesen zwei Punkten kann ich genau feststellen wo die letzten beiden Punkte des Quadrates sein sollten. Daher brauche ich eine weitere Schleife die nochmals alle Punkte von 1 bis N durchgeht, und findet die dritte Schleife während ihres Durchlaufs die beiden verbleibenden Punkte, dann haben wir ein Quadrat gefunden.
Nun das Problem ist, dass ich 3 Schleifen hätte, d.h. [mm] N^3 [/mm] KOnvergenz. Daher frage ich mich, was wäre eine Ansatz dieses Problem auf [mm] N^2 [/mm] zu optimieren.
|
|
| |
|
Hallo!
Das ist eine interessante Frage, und ich überlege auch schon eine ganze Weile, wie man das auf [mm] N^2 [/mm] runter bekommt, aber ich komm auch nicht drauf.
Aber dein bisheriger Algorithmus läßt sich auch noch optimieren:
Wenn du in der ersten Schleife grade den i. Punkt betrachtest, musst du in der zweiten Schleife die Punkte j=(i+1)...N und in der dritten nur noch die Punkte k=(j+1)...N betrachten. Sonst prüfst du die Punkte doppelt und dreifach und würdest demnach auch mehr Quadrate finden, als da tatsächlich sind.
Interessant wäre auch, ob jeder Punkt eine Ecke von höchstens einem Quadrat ist. Dann kann man immer alle Punkte, die ein Quadrat bilden, aus der Liste entfernen. Die kürzer werdende Liste ist dann auch schneller zu durchsuchen. Wenn zwei quadrate aber die gleiche Ecke haben, würdest du dem zweiten aber eine Ecke klauen, und das würde nicht erkannt werden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:05 Do 14.08.2014 | | Autor: | ThomasTT |
Ja, deine Hinweise sind in der Tat korrekt. Der letzte Hinweis ist glaube ich nicht praktikabel, da wir diese Annahmen nicht treffen koennen.
Trotzalledem frage ich mich wie man das in zwei Schleifen machen kann. Denn man braucht doch mindestens zwei Schleifen (fuer zwei Eckpunkte eben) damit die verbleibenden zwei Punkte exakt zu bestimmen sind. Und um die verbleibenden Punkte zu prüfen braucht man halt eine dritte Schleife.
|
|
|
| |
|
Hi!
Ich hab aus deiner zweiten Frage mal eine Mitteilung gemacht - die erste Frage ist ja noch offen.
Das einzige, was mir noch einfätt wäre, wenn man tatsächlich auch das Bild des Sternenhimmels hätte. (So steht es ja im Titel deiner Frage). Dann kann man mit zwei Schleifen zwei Punkte her nehmen, und dann direkt im Bild gucken, ob an den vier oder sechs zu erwartenden Stellen noch ein Stern sitzt. Dann geht das tatsächlich mit N².
Aber ich vermute, der Titel ist eher im übertragenen Sinn gemeint, und es gibt kein Bild vom Sternenhimmel...
Von daher, warten wir mal ab, ob sonst noch wer nen Lösungsvorschlag hat.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:10 Sa 16.08.2014 | | Autor: | felixf |
Moin!
> Nimm an du hast eine Liste von (x,y)-Koordinaten. Nun ist
> die Aufgabe alle Quadrate (schräg oder gerade) zu finden.
> Zum Beispiel (2 10), (5 11), (1 13), (4 14) ergibt ein
> Quadrat, das schräg ist, und (5 5), (10 0), (10 5), (5 0)
> ist ein Quadrat, welches gerade ist. Quadrate können um
> jedmöglichen Winkel gedreht sein. Optimale Konvergenz:
> [mm]N^2[/mm]
>
> Nehmen wir an wir haben N Koordinaten-Paare. Mein Ansatz
> ist einen Nx2 Array mit all den (x,y) Koordinaten zu
> erstellen. Danach schreibe ich eine Schleife, die jeden
> Punkt durchgeht (von 1 bis N) und in dieser Schleife ist
> eine weitere die ebenfalls alle Punkte von 1 bis N
> durchgeht. Mit diesen zwei Punkten kann ich genau
> feststellen wo die letzten beiden Punkte des Quadrates sein
> sollten. Daher brauche ich eine weitere Schleife die
> nochmals alle Punkte von 1 bis N durchgeht, und findet die
> dritte Schleife während ihres Durchlaufs die beiden
> verbleibenden Punkte, dann haben wir ein Quadrat gefunden.
Wenn du die dritte Schleife durch eine Abfrage in einer Hash-Tabelle ersetzt, kannst du die Laufzeit auf [mm] $O(N^2)$ [/mm] herunterschrauben: initialisieren der Hash-Tabelle benoetigt $O(N)$ Schritte, und jede Abfrage $O(1)$ Schritte.
LG Felix
|
|
|
|
