> The solution was to densify vertices of the square against which objects to be served were intersected. I remembered the easiest solution to query which line

> The solution was to densify vertices of the square against which objects to be served were intersected. I remembered the easiest solution to query which lines with some width cross some bounding box (for putting them in quadtree). Just increase BB size by half a line width on each side and you have a very good approximation of a much harder and slower problem. A small percentage of lines will be returned and not drawn, but it's a good trade-off.