Flächenüberschneidung suchen

[blablab]

Kann es sein dass das mit dem sortieren sogar noch aufwändiger ist?
Ich muss ja dann in jeder Liste die binäre Suche anwenden (das ist noch nicht aufwändig). Als Ergebnis hab ich dann jeweils eine Position wo dann zum Beispiel oberhalb alle Rects in Frage kommen und unterhalb nicht. Um diese 4 Listen zusammenzufügen würde ich dann einen Boolean-Array mit der Länge n machen und dann alle Listen durchgehen und die Rects die nicht in Frage kommen im Boolean-Array markieren. Und dann müsste ich nochmal den Boolean-Array durchegehen und mir die die übriggebliebenen Rects rausschreiben.

Das wäre dann:
4*Binäre Suche = 4* log(n)
Boolean-Array initialisieren = n
Falsche Rects rausstreichen ~ 4* 1/2n
Übriggebliebenen Rects rausschreiben = n

Insgesamt sind das dann ganz grob >4n Operationen.
Das ist ja eigentlich nicht viel, aber wenn ich die n Rects einfach alle durchgehe, dann muss ich ja auch nur jeweils 4 Vergleiche pro Rect machen. Und wenn einer der 4 Vergleiche false ergibt, dann müssen die restlichen nicht verglichen werden. Das bedeutet es sind sogar eher weniger als 4n Operationen...