Schnitt: Gerade/Rechteck

[Nikolas]

Die Darstellung der Geraden ist beliebig austauschbar

Ich geh mal davon aus, dass dein Strahl im Kästchen mit Index (linke untere Ecke) s=(x,y) beginnt und Richtung d=(u,v) läuft, wobei d normalisiert ist. Deine Kästchen haben Länge (W,H). Mit L = H/v hast du den Vector d'=L*d, der von der der linken unteren ecke von (x,y) zu waagrechten mit y=x+W läuft.
Jetzt hast du die x-Werte x_i=x+i*u' (x*i*L*u) und kannst schauen, in welchem Kästchen das liegt.

Damit kommst du pro Ebene mit einer Addition (x_(i+1)=u'+x_i), einem Abrunden (und vielleicht noch der Abfrage wegen uebersprungener Kästchen hin.

Deine Ansätze nutzen überhaupt nicht aus, das die Rechtecke sehr nett angeordnet sind und du somit z.B. weisst, dass wenn deine Strecke durch (x,y) und (x+3,y) geht, wohl auch (x+1,y) geschnitten werden muss.


// Könntest du vielleicht dein Problem noch ein Mal erklären? Ich habe das Gefühl, dass es da vielleicht auch einen komplett anderen Ansatz für die Berechnung gibt, der noch mal schneller sein könnte.