Suppose there are many line segments on a plane (2D scene) and I would like to redraw only small portion ("window") of the whole scene. The scene is dynamic, meaning one can add/remove/transform lines. Also, this being about drawing, it matters in what order the lines have to be redrawn (painter's algorithm, z-index). It is also possible to move a line in front of / behind of another line, effectively changing its painting order.
What data structure is suitable for this kind of problem?
I would like both the scene modifications and finding of the affected lines to be as quick as possible. One way to implement such scene graph is to use a simple list of line segments, sorted by z-index and during the redraw iterate through the list and if a segment fits the window, redraw. However, this has linear time complexity, and I would like to know if there is a faster way, preferably logarithmic.