1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Compute which vertices of a concave polygon are visible from a point outside the polygon

Discussion in 'Computer Science' started by Dozed12, Oct 8, 2018.

  1. Dozed12

    Dozed12 Guest

    Given a concave polygon $P$ defined by $n$ vertices and a point $p$ outside the polygon, I want to compute which of the vertices $v$ of the polygon are visible to point $p$. A vertex $v$ is considered visible to $p$ if the line between $p$ and $v$ doesn't cross the polygon $P$ in any edge or vertex except $v$.

    My current approach is to draw line segment from $p$ to each $v$ and check if that line intercepts any of the edges of the polygon $P$. Obviously this is quite a slow approach with $O(n^2)$, not to mention 2 line segment interception isn't a light computation.

    My question is if there is a faster approach to this problem, maybe in $O(n)$.

    This image should give a clear understanding of the problem.



    I have found an optimization to this problem. Still using line segment intersections but first pruning some vertices that we know for sure won't be visible. Using the average coordinates of $P$, called $Center$ in the figure, we can calculate in $O(n)$ which vertices make a "bigger" angle with the $Center$ in relation to $q$. These vertices are $M$ and $T$ in the image. With this we can assume all the vertices "behind" $M$ and $T$ wont be visible to $q$ and that the edges that they form will also not interfere.


    This allows us to "prune" a good amount of vertices and cutting the temporal complexity of the problem a lot. Unfortunately, in the worst case this will only save us from checking one edge meaning the complexity will still be $O(n^2-n)$. But it can also cause the best case to be $O(n)$. So in the general case, given a concave polygon with vertices well distributed we should expect around $O(n log(n))$ complexity with this optimization. That's pretty good already. However now I'm wondering if it's possible to use this idea of rays further and really get a solution that is always $O(n log(n))$ or even $O(n)$...

    Login To add answer/comment

Share This Page