4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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".

$\endgroup$
7
  • $\begingroup$ Starting with the closest point gives me this problem (deduction of the one above): i.imgur.com/deTMdpH.png $\endgroup$
    – Exzone
    Jun 27 at 12:31
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Jun 27 at 12:50
  • $\begingroup$ @Exzone updated it. Please take a look at it again $\endgroup$
    – nir shahar
    Jun 27 at 13:14
  • 1
    $\begingroup$ Sorry but how would that be efficient if I need to update seen segments as blocked? (Portion of line is marked as visible segment) $\endgroup$
    – Exzone
    Jun 27 at 21:17
  • $\begingroup$ @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 $\endgroup$
    – nir shahar
    Jun 27 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.