Effizient prüfen, ob Rechteck und Halbgerade sich schneiden können?

Question

wie kann man effizient prüfen, ob sich eine Halbgerade und ein Rechteck schneiden könnten?

Danke,

Thilo

Comments

In welcher Form liegen dir die Angaben vor?
4 Ecken ABCD, ein Punkt P und ein Vektor r?

3-dimensional? Das braucht wohl mehrere Schritte.
1. Schritt: Spatprodukt (AB, AD, r ) ≠ 0?
2. Schritt: Ebene mit Gerade schneiden. t sollte > 0 sein.
3. Schritt: Ortsvektor des Schnittpunkts als 0S= 0P + uAB + vAD darstellen und testen, ob u und v zwischen 0 und 1.

---

2-Dimensional. Für das Rechteck alle 4 Ecken, eventuell noch Mittelpunkt-Vektor, auch normiert. Das müsste ja nur einmal berechnet werden. Also die Rechtecke sind statisch, die Halbgeraden bewegen sich, daher kann man für die Rechtecke schon ein paar mehr Berechnungen anstellen und im Arbeitsspeicher speichern.

Für die Halbgerade sind Ortsvektor und normierter Richtungsvektor vorhanden sowie normierter Normalenvektor.

Außerdem sind die Rechtecke nicht gedreht, also die Seiten parallel zu den Koordinatenachsen.

---

Ah. Ok. Dann nützt dir meine Ergänzung oben nicht so viel. Vielleicht 3. Schritt? Scheint mir aber zu aufwändig.

Vielleicht

Gleichung g: v = 0P + t r der Halbgeraden komponentenweise ansehen. 

und Gleichungen mit den Randkoordinaten des Rechtecks aufstellen. Die Bereiche für t müssten überlappen und in der Überlappung sollte ein t > 0 vorkommen. 

---

 Wenn die Halbgerade durch das Rechteck laufen soll, muss sie eine der Diagonalstrecken schneiden. Das wären ein oder zwei Prüfungen, die durchzuführen wären.

Möglicherweise lässt sich vorab checken, ob diese Prüfungen im konkreten Falle überhaupt notwendig sind.

Answer 1

Jedes Rechteck teilt den Raum in 9 Rechteckige Felder ein wobei ein Rechtecksfeld das Rechteck selber ist. Prüfe in welchem Rechtecksfeld sich der Ursprung der Halbgeraden befindet. Das sollten 4 Integervergleiche sein, die recht schnell gehen. Nun gibt es 2 Möglichkeiten:

1. Wir befinden und über, unter, links oder rechts vom Rechteck. Dann prüfen wir auf einen Schnittpunkt mit der zugewandet Rechtecksseite. 

2. Wir befindet uns links über, rechts über, links unter oder rechts unter unserem Rechteck. Dann würden wir auf Schnitt mit einer Diagonalen prüfen (Wenn wir nur wissen wollen ob die Halbgarade das Rechteck schneidet). Oder auf Schnitt mit den uns zugewanten Rechtecksseiten (Wenn wir wissen wollen wo Das Rechteck von der Halbgeraden getroffen wird.)