문제

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

One can use the accepted answer here to compute visible vertices in $P$ from a point $p$ in $\mathcal{O}(n\log{}n)$.

My question is, does an algorithm exist to do it in $\mathcal{O}(n)$ time?

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top