# 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. 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. EDIT:

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)\$...