Schnittpunkte beliebiger Polygone mit einem beliebigem Achsen-parallelem Rechteck

[Iwo Asnet]

Zwei Geraden schneiden sich? G1 = Ax+B, G2 = Mx+N
Ergo setzen wir G1=G2 (Y-Werte sind ja gleich) und suchen dazu das X...
Ax+B = Mx+N
Ax-Mx = N-B
x(A-M) = N-B
x = (N-B)/(A-M)

Fein. Wir können als X ausrechnen und dann setzen wir das in (z.B.) G1 ein und erhalten den Schnittpunkt S = (X,A*X+B)

Eigentlich haben wir ja keine Geraden, sondern Strecken. G1 wird also durch p1 und p2 begrenzt, G2 durch q1 und q2.
Der Punkt S befindet sich auf der Strecke (p1-p2) genau dann, wenn?.... Sx zwischen p1x und p2x und Sy zwischen p1y und p2y liegt.

Eigentlich popeleinfach.