Using visible line segments to compute a visibility polygon

Question

Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the region in $P$ consisting of all points $q$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

As for now, let's ignore the case where a line segment lies completely on the ray.

Now I have a collection of line segments (edges of the polygon) which are visible from point $p$. The problem is that not every line segment in the collection is fully visible which is why I can't simply connect them into a polygon. I first need to compute which part of each line segment is visible and connect those. This last step is what I struggle with.

Here are two examples:

In the left example edge $\overline{AD}$ is partially seen from $p$, in the right example it's $\overline{GH}$ (rest of the edges are completely visible).

For the left example, how can I use the fact that $\overline{EB}, \overline{BC}, \overline{AD}$ and $\overline{DE}$ are visible from point $p$ in order to compute the visibility polygon?

I struggle with finding an algorithm to do this which doesn't fail for every second case I apply it to. Any suggestions?

Answer 1

First, assume we already have a list $L$ with all segments in $P$ that are at least partially visible from $p$, ordered by the smallest angle $\theta$ such that a segment is visible from $p$ at angle $\theta$. (This can be done with a (angular) sweep line algorithm in $O(n\log n)$)

Now, observe that if a line from $p$ to some point on the segment $s_i$ in $L$ intersects some segment of $P$, it must intersect either $s_{i-1}$ or $s_{i+1}$ (be careful to wrap around the ends of the list), i.e. one of the neighbours of $s_i$.

Therefore, we can construct the visibility polygon as follows: iterate over all segments $s_i$ in $L$ and compute the visible sub-segment of $s_i$ using the segments $s_{i-1},s_{i+1}$. (call it $s_i^*$) Add it to your visibility polygon and then add the lines connecting the endpoints of $s_i^*$ with $s_{i-1}^*$ and $s_{i+1}^*$ to the visibility polygon (if they aren't already connected directly).

Answer 2

If visibility polygon means a polygon $P'$ where point $p$ needs to able to see all the points on the line segments in $P$ without any other point blocking it then here is what I think:

You are given polygon $P$ so you are also given the vertices $V$ and edges $E$ (line segments) within $P$. So if $p$ is visible in $P$ then point $p$ and all points $x$ on the edges $E$ can form a line segment $\overline{px}$ where no other point on $\overline{px}$ can contain another point $x'$ from another edge $E'$.

This means that $\overline{px}$ does not intersect any other point $x'$ of any other $E'$ in $P$. This also means that you would be able to check from one vertex on $E$ to the other.

Therefore, if at given time your algorithm finds a segment that's only partially visible you will also know where the last point that allows it to be visible to $p$ and so you would use that point as the new vertex.

For example, in the your left polygon above, you can find the point from $\overline{AD}$ where any further towards $A$ would render the line partially not visible. Let's say that this new point is $A'$. Then by removing $\overline{AD}$ and $\overline{AC}$ and add $\overline{A'D}$ and $\overline{A'C}$ to the given polygon (or simply replace $A$ with $A'$ for the line segments involving $A$) then you would be able to compute the visibility polygon.

The one problem that I can think of currently is that there are infinitely many points on a given line so this algorithm can essentially run infinitely. So there has to be a length difference, $\delta$, between two points on the line segment that's small enough to be able to check all critical points but big enough that it won't let the algorithm run infinitely so that your algorithm would just increment by $\delta$.