Schnitt"menge" zwischen Rechteck und Strecke ermitteln

Werbeanzeige

Elmi

Treue Seele

Beiträge: 253

05.12.2012, 09:43

Schnitt"menge" zwischen Rechteck und Strecke ermitteln

Hi,

ich habe hier in einem 2D-Koordinatensystem zum einen ein Rechteck, dessen Seiten parallel zur X- bzw. y-Achse sind sowie eine Strecke, die irgendwo in diesem Koordinatensystem liegt.

Hier will ich jetzt

a) herausfinden ob die Strecke das Rechteck schneidet (wobei Anfangs- und Endpunkt der Strecke außerhalb des Rechteckes liegen können, was die Geschichte IMHO ziemlich verkompliziert) und

b) die Schnittpunktkoordinaten zwischen Strecke und Kanten des Rechteckes ermitteln (so es den nwelche gibt)

So, hat jemand eine Idee, wie man das möglichst rechenzeitsparsam hinbekommen könnte?

Danke :-)

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

05.12.2012, 09:50

Die Strecke parametrisieren wir als Strecke(t) = Startpunkt + t * (Endpunkt - Startpunkt)
Also Strecke(0) ist der Startpunkt, Strecke(1) ist der Endpunkt, Strecke(0.5) wäre genau die Mitte.

Bestimme nun das kleinste und größte "t", für das die x-Koordinate von Strecke(t) zwischen Min.X und Max.X liegt.
Das gleiche machst du auf der y-Achse.
("Wann taucht die Strecke in das Rechteck ein, wann geht sie wieder raus?" - aber nur auf jeweils einer Achse - also sehr einfach zu berechnen!)

Am Ende hast du zwei Intervalle, die dir sagen, für welche t-Werte die Strecke auf der x- und y-Achse im Rechteck liegt.
Die Überlappung der Intervalle gibt dir den t-Wertebereich, für den die Strecke tatsächlich im Rechteck liegt.
Wenn sich die Intervalle nicht überlappen, gibt es keinen Schnitt.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Elmi

Treue Seele

Beiträge: 253

06.12.2012, 09:04

Hmmm, aber wenn ich jeweils nur die X- bzw. Y-Richtung getrennt voneinander betrachte, geht das doch in z.B. dem Fall hier schief:

(Link)

Rein auf Basis der X- Koordinaten, ergibt sich die mit rot markierte Überlappung. Nur wenn man auch noch Y einbezieht, sieht man, dass die Strecke komplett außerhalb liegt. D.h. bei Verwendung von jeweils nur einer Achse für die Berechnung bekomme ich nicht wirklich die Überlappung?

Zum Seitenanfang

Evrey

Treue Seele

Beiträge: 245

Beruf: Weltherrscher

06.12.2012, 12:12

Eine Gerade kannst du wie gesagt als eine Kombination aus Ankerpunkt-Vektor und Richtungsvektor darstellen. Im Idealfall ist der Richtungsvektor auf die Länge 1 normiert, muss aber nicht sein. Das sieht dann in etwa so aus:

	Quellcode
1	f(t) := v(x0;y0) + t*v(dx;dy) = v(x(t); y(t))

Diese Gerade lässt sich auch in eine andere Form umbauen, nämlich:

	Quellcode
1 2	y(x) := mx + n x(y) := ay + b

Diese Darstellung hat den praktischen Vorteil, dass x und y voneinander abhängig gemacht sind. Nur wie kommt man an diese Gleichungen? Nun... es gibt etwas, das die Komponenten in f(t) verbindet, nämlich das t. Und damit können wir die Abhängigkeit erhalten. Die gesuchte Lösung lautet:

	Quellcode
1 2	x(y) := dx/dy * (y - y0) + x0 y(x) := dy/dx * (x - x0) + y0

Ich empfehle dir, es dir nochmal selbst herzuleiten. Dann wirst du es wesentlich besser verstehen, was dir künftige Fragen dieser Art erspart.

Was jetzt kommt ist extrem einfach. Ein Rechteck ist im einfachsten Fall (parallel zu den Koordinatenachsen) durch zwei Intervalle bestimmt. [xA;xB], was die Breite festlegt, und [yA;yB], was die Höhe festlegt. Die untere linke Ecke liegt also im Punkt v(xA;yA), die obere rechte im Punkt v(xB;yB). Jetzt musst du nur noch einsetzen und testen. Wenn die Gerade die linke Rechteck-Kante schneidet, gilt:

C-/C++-Quelltext

int _yG{y(xA)}; // _yG ist die y-Position der Geraden an der x-Koordinate xA.
if((_yG >= yA) && (_yG <= yB)) { // Prüfe, ob _yG im Intervall [yA;yB] liegt.
  std::cout << "Yays, schneidet das Rechteck!";
}

Eine Gerade schneidet oder berührt dann ein Rechteck, wenn diese Überprüfung für mindestens eine Kante des Rechtecks zutrifft. Du wirst also bis zu vier Berechnungen dieser Art machen müssen. Man kann einige Berechnungen durch geschickte Kombination einsparen. Zudem kann man die Berechnung abbrechen, sobald einer der Tests true liefert. Du wirst noch die Sonderfälle betrachten müssen, in denen dx und/oder dy Null sind. Aber das überlasse ich dir. Ist extrem einfach.

Lineare Algebra solltest du dir gern mal anschauen. Das wahrscheinlich Nützlichste aus der Mathematik, wenn es um Spieleprogrammierung geht.

	C-/C++-Quelltext
1 2 3 4	int main(int _argc, char** _argv) noexcept { asm volatile("lock cmpxchg8b %eax"); return 0; } // ::main

(Dieses kleine Biest vermochte einst x86-Prozessoren lahm zu legen.)

=> Und er blogt unter Hackish.Codes D:

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

06.12.2012, 13:35

Zitat von »Elmi«

Hmmm, aber wenn ich jeweils nur die X- bzw. Y-Richtung getrennt voneinander betrachte, geht das doch in z.B. dem Fall hier schief: (...)

Nein, du hast mich scheinbar nicht verstanden.
Schau hier (anklicken zum Vergrößern!):

Entlang der Linie habe ich die beiden Intervalle eingezeichnet.
Im roten Intervall befindet sich die Linie auf der x-Achse im Bereich des Rechtecks.
Im grünen Intervall befindet sie sich auf der y-Achse im Bereich des Rechtecks.
Die Intervalle überlappen sich nicht. Es gibt also keinen Punkt auf der Linie, dessen x- und y-Koordinaten im Rechteckbereich liegen, also keinen Schnitt.

@Evrey:
Mit der Steigungsform zu arbeiten halte ich für keine gute Idee. Da hat man immer Sonderfälle bei senkrechten Geraden.
Mit Vektoren ist es numerisch stabiler und es lässt sich ganz einfach auf beliebig viele Dimensionen übertragen (z.B. 3D).

David Scherfgens Website | Konzentrationstest Polizei