Schnitt: Gerade/Rechteck

[Medium]

Genau den Ansatz hatte ich schon, allerdings ist das Verfahren viel zu grob. Es geht darum: Ich habe ein Bild in kleinere Bilder zerlegt. Dann nehm ich einen Punkt im Bild, und von diesem aus einen Vektor. Nun will ich eine Liste aller Rechtecke haben, die dieser daraus erzeugte Strah schneidet.
Ich kann nun aus dem Strahl durchaus eine Strecke machen in dem ich einfach den 2. Punkt so wähle dass er ausserhalb des Bildes liegt um den selben Effekt zu haben, jedoch führt das dazu, dass ich viel zu viele Rechtecke als Schnittkandidaten habe - im Worst-Case alle.

Das hier hängt mit meinem kürzlich hier erstellten Thema zusammen, wie man eine Gerade mit einer Fkt. 3. Grades schneidet, und das braucht eben so arg lange, dass ich diese Methode hier brauche um vorab sehr "billig" möglichst viel auszuschließen. Im Grunde macht man das bei fast allen 3D Anwendungen genau so, nur eben mit dem "View-Frustum" und einem Octree der Szene. Bei mir isses halt nur 2D, der Frustum ist eine Linie, und der Octree ist ein regelmäßiges Gitter von Rechtecken.