O(nlogn) divide and conquer algorithm to find visible lines

3
votes

O(nlogn) algorithm

I am trying to solve the problem shown in the image attached. I got the divide part, where you would recursively divide the line sets into halves and the lines with the smallest and largest slope would be visible.

I don't know how to do the merge part though and I'm not understanding it.

Intuitively, at first, I'd think that all lines would be visible eventually if there are no three lines that intersect at one point.

As well, the conquer part is when I would take out invisible lines... from what I understand, there shouldn't be any lines taken out before the conquer phase.

If anyone can explain for those of us that has a bit of a slower brain, I'd be very thankful! :)

1
algorithmdivide-and-conquer
without illustrative image we can only guess ... unseen lines removal in computer gfx is usually done by computing the surface normal (if mesh is convex) . Concave meshes are subdivide to convex meshes prior to this. There may be other algorithms out there exploiting something known about the case for which it is used but without more info is hard to say to what is you example refering to. If your mesh is solid (not just wire-frame) then you can use Z-sorting or Z-Buffering but I guess that is not what you want to hear - Spektre

1 Answers

1
votes

Consider a 3 line example. You have 2 options. a) only 2 lines are visible b) all 3 lines are visible.

So you need to determine if the middle one is visible or not. To do this you can compute the intersection point of the outer 2 lines (call it A). If A is above the the middle line then the middle one is hidden, if it's below then it's visible (draw the two figure and it will be obvious).

To determine if the point is above or below substitue it's coordinates in the line equation (y = ax + b). If y > ax + b then the point is above the line, if y < ax + b the point is below and if y = ax + b the point is on the line (shouldn't happen according to the problem).

To solve your problem I would just take the lines in order of the slope and try to add them to the solution. Every time you add a new line check if the previous line is still visible and remove it if it's not (repeat as many times as needed, since the new line might hide more than just one previous line).

If you insist on doing merges you need to apply this logic on the merge line to figure out how many lines you remove from the middle.