Betroffene Gebiete von Zwei Objekten berechnen.

[Fedaykin]

Ich habe folgendes Problem:
Ich rastere eine Ebene in verschiedene Gebiete zu bestimmten Größen (z.b 2000 Einheiten).
d.h:
also X=10,Y=10: Gebiet(0,0)
X=5000,Y=5000: Gebiet(2,2)
D.H. Ich kann jeden Punkt in einen Koordinatensystem, einen genauen Gebiet zuordnen. Nun das Problem:
Ich brauche einen Algorithmus der mir alle Gebiete liefert, durch welche eine Gerade zwischen zwei Punkten läuft. Im simpelsten Fall ist das nur das Gebiet in dem die Gerade startet und auch endet, im schwerwiegenderen Fall sind das mehrere Gebiete. Gibts für sowas einen relativ schnellen Algorithmus?

Bsp:

-1      0     1    2     3
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
|     |     |     |     |     | -1
|     |     |     |     |     |
+-----+-----+-----+-----+-----+
|     |    o|     |     |     |
|     |  X  |  X  |     |     | 0
|     |     |     |     |     |
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
|     |     |  X  |  X  |     | 1
|     |     |     |o    |     |
+-----+-----+-----+-----+-----+

Die beiden o sind die Gedachten Objekte, eine Linie zwischen den o's würde also das Gebiet 0,0;1,0;1,1;2,1 betreffen.

[Jan Hinnerk]

Ja, das gibt es. Im Eigenbau geht der Weg ungefähr so:

1. Gebiete definieren als Polygone, im einfachsten Fall als Rechtecke
2. Für den zu prüfenden Punkt Gerade zum Koordinatenursprung bilden.
3. Analysieren, ob die Prüfgerade genau einen Schnittpunkt mit dem Prüfpolygon besitzt, wenn ja = Punkt liegt im Polygon.

Den Algorithmus als Source habe ich nicht gerade zur Hand, vielleicht kann ich ihn suchen. Ich denke mir, dass es dafür auch frei verfügbare Libs gibt.

[Fedaykin]

Ich vergaß zu erwähnen das die Gebietsgrößen immer Quadrate mit fester ausdehnung sind. Also im N * N Einheiten groß, dabei Variiert das N niemals innerhalb einer berechnung. Das wird das ganze wohl vereinfachen.

[berniebutt]

Jan Hinnerks Vorschlag ist die allgemeine Lösung der Trigonometrie und erfordert einen gewissen Programmier- und Rechenaufwand.

In deinem Fall mit einer geringen Anzahl (hier 15) von gleichgrossen Quadraten kannst du dir die Sache einfacher machen mit einer begrenzten Anzahl von if-Abfragen. Jedes Quadrat besitzt vier Randwerte xmin, xmax, ymin, ymax. Der Punkt liegt innerhalb eines Quadrates, wenn alle vier Bedingungen bei einem Quadrat zutreffen:

x > xmin, x < xmax, y > ymin, y < ymax

Trifft nur eine Bedingung nicht zu, so liegt der Punkt ausserhalb. Beachten solltest du auch, ob ein Punkt genau auf einem Rand liegt. Die Optimierung der if-Abfragen bleibt deine Angelegenheit.

Das ganze gehört so eher in den Bereich Übungsaufgabe!

[Nexus]

Schau dir mal den Bresenham-Algorithmus an. Im Artikel Rasterung von Linien findest du noch mehr...

[Fedaykin]

Nexus schrieb:

Schau dir mal den Bresenham-Algorithmus an. Im Artikel Rasterung von Linien findest du noch mehr...

Der Algorithmus ist interessant, ich hab den glaube ich schonmal für ein LineOfSight implementierung benutzt. Das Problem ist nur, das er sich immer auf Mittelpunkte bezieht. Das Problem bei mir ist, das die Objekte innerhalb einer Region unterschiedlich liegen können. Und damit unterschiedliche Regionen betroffen oder nicht betroffen sind. Der Bresenham Algo garantiert mir damit, das ich mindestens alle Region erwische die ich will, leider aber ggf dabei zu viele.

Mein aktueller Ansatz ist folgender.

Ich berechne mir die Geradengleichung der Linie.
Prüfe nun für alle Regionen welche in Frage kommen ob die Gerade das dort herrschende Koordinatensystem schneidet. Schneidet es die X Achse an einen Punkt ist diese Region und die Links daneben liegende Region teil der Menge.
Schneidet es die Y Achse an einen Punkt ist diese Region und die Darunterliegende Region Teil der Menge. Ich denke da kommen noch ein paar sonderregeln hinzu was nullpunkt oder maximalwert einer Region angeht.

[berniebutt]

Habe das jetzt endlich verstanden mit der Linie o - o und dass mehrere Quadrate betroffen sein können.

Der zuletzt genannte Ansatz mit dem Schnittpunkt zweier Linien ist richtig. Du must dann noch unterscheiden, wo der Schnittpunkt liegt - ausserhalb oder innerhalb eines Quadrates.

So wie es aussieht, kommst du um die Trigonometrie und einige weitere Plausibilitätsprüfungen nicht herum. Da musst du wohl selbst herangehen oder suchen, ob jemand das schon gemacht hat. Der fertige Algorithmus ist selbst programmiert nicht in wenigen Stunden einsatzfähig zu bekommen.

Viel Glück!

[Fedaykin]

berniebutt schrieb:

Habe das jetzt endlich verstanden mit der Linie o - o und dass mehrere Quadrate betroffen sein können.

Der zuletzt genannte Ansatz mit dem Schnittpunkt zweier Linien ist richtig. Du must dann noch unterscheiden, wo der Schnittpunkt liegt - ausserhalb oder innerhalb eines Quadrates.

So wie es aussieht, kommst du um die Trigonometrie und einige weitere Plausibilitätsprüfungen nicht herum. Da musst du wohl selbst herangehen oder suchen, ob jemand das schon gemacht hat. Der fertige Algorithmus ist selbst programmiert nicht in wenigen Stunden einsatzfähig zu bekommen.

Viel Glück!

Die Zeit ist zweitrangig (Hey ich werde dafür bezahlt *gg*). Ich glaube ich benutze den Bresenham Algo (irgendwie will ich da immer Breshham schreiben) um erstmal grob herauszufinden welche Bereiche überhaupt in Frage kommen (eine Art Bounding Box für Linien), und prüfe dann mit den Schnittpunkt-Ansatz. Ob die Gerade wirklich diesen Bereich schneidet. Wenn interesse besteht kann ich ja das Ergebnis dann mal posten.

[berniebutt]

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?

[Fedaykin]

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.

[berniebutt]

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ühren

Jetzt 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

[hustbaer]

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

[otze]

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 Startpunkt

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

[Fedaykin]

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 Startpunkt

Sollte 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).

[hustbaer]

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.

[Fedaykin]

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.

[Fedaykin]

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 4

t1=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.

[Fedaykin]

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