Betroffene Gebiete von Zwei Objekten berechnen.
-
Du darfst dich glücklich schätzen, wenn Zeit = Geld bei der Entwicklung eines Algorithmus zweitrangig sein soll. Wie sieht es da mit der Effektivität des Algorithmus aus - Hauptsache es läuft oder was?
Was ist, wenn du es auf einmal mit mehreren Hundert oder Tausend Quadraten statt hier 15 zu tun hast?Algorithmen sind das Salz in der Programmiersuppe! Zutrauen täte ich mir das, nur sehe ich keine Veranlassung dazu.
Poste deine eigene Lösung, wenn du fertig bist. Als Chef einer Firma gäbe ich dir eine Woche Zeit dafür. Dann muss aber alles ohne Bugs fertig sein, sicher und sehr effizient laufen.
Das Thema könnte vielleicht ein sportiver Vorschlag im Forum 'Projekte' sein?
-
Also Effektivität ist auch erstmal "Zweitrangig" solange ich irgend ein Ergebnis vorliegen habe. Der durchschnittswert an Regionen wird wohl im 3 Stelligen Bereich liegen. Aber das ganze zu optimieren ist auch interessant, wenn nicht sofort nötig.
-
Arbeitsaufwand und Performance - alles zweitrangig? Toll! Eine 3-stellige Anzahl von Quadraten (max 999) ist auch kein Peanut mehr und lohnt bereits das Nachdenken über einen optimierten Algorithmus von Anfang an.
Auf die Schnelle schlage ich vor:
1. Mit den Randkoordinaten alle Quadrate aussortieren, die von vornherein nicht in Betracht kommen --> maximal 4 if-Abfragen je Quadrat
2. Mit den 4 Rändern der verbleibenden Quadrate und der Gerade o - o eine Schnittpunktberechnung durchführen --> sobald ein Treffer = innen, sonst aussen
3. Die Schnittpunktberechnungen mit float oder double durchführenJetzt solltest du aber selbst anfangen mit der Realisierung! Der optimale Algorithmus ist jener, der mit möglichst wenigen if-Abfragen und möglichst wenigen verbleibenden Schnittpunktberechnungen auskommt. Dein Ansatz 'Hau rein, optimieren kann ich immer noch' erscheint mir hochgradig suspekt!
Ich denke mal, mit maximal 200 Zeilen Sourcecode kann die Sache geritzt sein. :p
-
Ich check grad das Problem nicht.
Die Grid-Zellen die den Strahl schneiden kann man einfach in einer Schleife durchgehen. Zellen die den Strahl nicht schneiden braucht man dazu nichtmal zu testen.
Beschreibung:
http://www.cse.yorku.ca/~amana/research/grid.pdf
-
Wie ich das machen würde:
Ich teile die Regionen in Reihen auf und prüfe dann zuerst, ob der Strahl nach oben oder nach unten geht.
Wenn der Strahl nach oben geht: (nach unten folgt analog)
1. Teile alle Regionen in ihre Reihen auf.
2.loop bis die Region des Endpunktes gefunden wurde:
2.1 Bestimme den Schnittpunkt der Gerade vom Startpunkt aus mit der Gerade, die die aktuelle Reihe nach oben begrenzt.
2.2 Bestimme die Region der aktuellen Reihe in der der Endpunkt liegt.
2.3 markiere alle Regionen auf der Riehe dazwischen(beende, wenn die Region des Endpunktes gefunden wurde)
2.4 gehe eine Reihe nach oben und wähle den gefunden Schnittpunkt als StartpunktSollte sehr schnell gehen, da in jeder Iteration nur 1 Schnittpunktberechnung gemacht werden muss, egal wie viele Regionen in einer Reihe liegen und die Regionen alle gleich groß sind. Dann sind die Operationen 2.2 -2.4 auf jeden Fall effizient
Man kann das Ganze nochmal verbessern, indem man testet, ob der Strahl stärker horizontal oder vertikal läuft und dann vielleicht stattdessen die Regionen in Zeilen aufteilt.
-
otze schrieb:
Wie ich das machen würde:
Ich teile die Regionen in Reihen auf und prüfe dann zuerst, ob der Strahl nach oben oder nach unten geht.
Wenn der Strahl nach oben geht: (nach unten folgt analog)
1. Teile alle Regionen in ihre Reihen auf.
2.loop bis die Region des Endpunktes gefunden wurde:
2.1 Bestimme den Schnittpunkt der Gerade vom Startpunkt aus mit der Gerade, die die aktuelle Reihe nach oben begrenzt.
2.2 Bestimme die Region der aktuellen Reihe in der der Endpunkt liegt.
2.3 markiere alle Regionen auf der Riehe dazwischen(beende, wenn die Region des Endpunktes gefunden wurde)
2.4 gehe eine Reihe nach oben und wähle den gefunden Schnittpunkt als StartpunktSollte sehr schnell gehen, da in jeder Iteration nur 1 Schnittpunktberechnung gemacht werden muss, egal wie viele Regionen in einer Reihe liegen und die Regionen alle gleich groß sind. Dann sind die Operationen 2.2 -2.4 auf jeden Fall effizient
Man kann das Ganze nochmal verbessern, indem man testet, ob der Strahl stärker horizontal oder vertikal läuft und dann vielleicht stattdessen die Regionen in Zeilen aufteilt.
Auf so eine Ähnliche lösung bin ich auch gekommen, die wird auch gerade implementiert. Hier gibts noch ein paar sonderfälle zu beachten aber alles in allen sollte ich das damit relativ effektiv hinkriegen. Vor allem da man hier durch Bruchrechnung sogar Floating Points operations sparen kann (Ich versuche wenn möglich nur im Ganzzahlbereich zu rechnen).
-
Es ist in der Schleife gar keine Schnittpunkt-Berechnung nötig.
Bitte lest euch doch einfach das Paper durch, der Algorithmus ist wirklich nicht so schwer.
-
Der Ansatz in den Paper ist sehr interessant.
Wenn mich nicht alles täuscht, läuft man damit sozusagen auf den Strahl entlang. Und zwar immer genau "1 Regionabschnitt" in die Richtung deren Region man als nächstes passiert Entweder in die nächste Spalte oder Zeile.
Die Frage ist für mich was ist DeltaX und DeltaY, laut Paper ist es die anzahl an t's die ich in die richtung gehen muss, um der größe einer Region zu entsprechen. Aber irgendwie steh ich auf den Schlauch wie ich das berechnen soll.
-
Ich glaube ich hab das mit DeltaX und DeltaY herausgefunden.
MaxX und MaxY ist ja das t für meine Gerade an dem ich die nächste Regionengrenze in X oder Y richtung schneide.dies setze ich mit einen Faktor in meine Geradengleichung ein. Und rechne aus, bei welchen Faktor er mit diesen Wert jeweils die X oder Y Grenze passiert Bsp:
Geradengleichung:
(2,9)+t(9,15)
Die breite einer Region beträgt 4t1=MaxX=2/9
t2=MaxY=4/15(0,Irgendwas)+x*2/9*(9,15)=(4,Irgendwas) //wielange muss ich in richtung der Geraden gehen um ein Grenzüberschritt in X richtung zu machen
Das reduziert sich auf die Formel
2x=4 damit ist x = 2
Für y ists ja dann das selbe nur das die 0 genau anders stehen.
Ich hoffe ich hab das damit richtig verstanden.
-
@hustbaer: Nochmal besten Dank für den Link. Konnte den Algo jetzt implementieren, erste NUnit tests und nachvollziehen auf den Papier zeigt das er ausnehmend gut funktioniert. Das hat mir riesig geholfen. Und besten dank auch an alle anderen für die Hinweise und Tipps.
