Visible Lines

[legend986]

When a set of lines not parallel to each other are given. What is the best way of getting the visible lines? These are in the 2D space and I'm sort of viewing from y=infinity...

I thought of using divide and conquer and then getting the solution but I'm wondering if there is a better way...

[pm_kirkham]

What are the constraints on visibility?

[legend986]

Well, as far as I can see:

The lines extend up to infinity. They intersect but three lines do not intersect at the same point. They are of the form y=mx+c, where m is the slope. Well, I guess thats it... Or are you asking for something else?

[pm_kirkham]

Well, initially I thought that if you're at y=infinity and are looking at them, then all of them are in your field of view (assuming the 2D space your lines are in is the x,z plane). Now you're saying that the lines are in the x,y plain. Again, with a non-zero angular field of view, all lines in the plain are visible, and only the line x=0 appears as a point. So you're using 'visible' to mean something else - actually explain your problem fully and unambiguously.

[legend986]

We say that line Li is uppermost at a given x-coordinate x0 if its y-coordinate at x0 is greater than y-coodinates of all the other lines at x0. So something like mix0+ci>mjx0+cj for all i!=j. We say line Li is visible only if there is some x-coordinate at which it is uppermost so some portion of it can be seen if you look down from y=infinity. There are only two planes that are being considered in this problem I guess. We don't have the z-plane.

And no, all the lines in the plane are not visible. Its difficult to draw here, but there are many situations where the lines are not visible.

[pm_kirkham]

Right - your lines occult each other. As you're 'viewing' from y=infinity, you're just solving which has the greatest y-value, so it becomes a simple linear programming problem.

Alternatively, the lines with the most extreme positive and negative gradients will have the greatest y-ordinates for x->+infinity and x->-infinity. The visible ones will be of increasing gradient with increasing x - ordinate, so you can sort them and then find successive intersections. If the x-ordinate of intersection of lines L(n) and L(n+1) is less than that of L(n-1) and L(n), then L(n) is not visible, otherwise L(n) is above L(n-1) and L(n+1) between their intersections. I haven't done a proof, but I suspect you can just do a linear scan of the sorted list, so you end up with a O(NlogN) algorithm due to the sort.