Angular line sweep algorithm

Question

I am trying to implement a radial/angular sweep algorithm that finds all segments (segments are disjoint) that are visible from one particular point in $O(n \lg n)$. So I am trying to order vertices by their angle with point P that we are checking visibility from. But I am uncertain with which point to start first with. If I am selecting them by their angle I have the following situation:

enter image description here

These are the first two points that are being checked:

enter image description here

But the problem is that I can't check them with lines before and thus they seem to be visible by the algorithm I found online $O(n \log n)$ algorithm for disjoint segment visibility problem. Those lines will end before the first line that's covering them ends so all 4 of them should be visible by this algorithm. So which criteria should I use to start my angular sweep algorithm?

Algorithm so far: I sorted points by the polar angle they make with initial point P. The approach is to start with a minimum degree. I am adding them to the binary search tree which has a custom comparator that adds them by comparing that segment with all other segments in a binary tree. If the segment we're inserting is $T$ and $O$ is comparing the segment, I'm checking whether $PT_{start}$ and $O$ have intersections. If they don't intersect then $T$ should be before $O$ in BST. That segment is visible. The problem is when I encounter lines like in the pictures above. It marks right segments as visible because there is no first line in BST so it can't check them with the biggest one on the left. I have no idea what should be my starting point and how to differ those problems.

Answer 1

You can "split" each of those lines (that you see their endpoint before their starting point), into 2ドル$ lines: one totally below the $x$ axis, and one totally above it.

Notice that this adds a small caveat: you will need to create a "tie breaker" in your algorithm, that will take the closest point to the origin from a set of points with the same "angle".

• Exzone: Starting with the closest point gives me this problem (deduction of the one above): i.imgur.com/deTMdpH.png
• nir shahar: Oh, by visibility you meant "seeing the enitre line" and not "seeing a portion of the line". So yea, it will not work. I will update the answer in a few minutes to reflect that change.
• nir shahar: @Exzone updated it. Please take a look at it again
• Exzone: Sorry but how would that be efficient if I need to update seen segments as blocked? (Portion of line is marked as visible segment)
• nir shahar: @Exzone I thought of some other way to solve this problem, which might be a bit easier to think about. Take a look when Im done editing