algoritmo para problema de visibilidade de segmento separado

Considere que temos $n$ segmentos separados e um ponto $P$que não está em nenhum segmento. Eu quero encontrar um$O(n \log n)$ algoritmo para verificar quais segmentos são visíveis a partir $P$. Um segmento é visível a partir de$P$ se tiver um ponto visível de $P$.

Minha idéia é usar uma linha de varredura com um ponto final em $P$, classifique os pontos no sentido horário por grau e comece a partir de um ponto final no segmento visível mais próximo (que eu não sei encontrar), gire e detecte um segmento visível e alguns segmentos invisíveis possíveis por vez. Tudo o que consigo pensar é$O(n^2)$tão longe. Alguém pode sugerir uma$O(n \log n)$ algoritmo.

Wolg poderíamos assumir $P$ é o ponto de origem $(0,0)$.

1. Liste os pontos finais de todos os segmentos, represente-os na coordenada polar $(\theta,\rho) \in [0,2\pi) \times [0,\infty)$ e classificá-los por grau.
2. Imagine que há um raio de $P$ apontando para a direita, nós o varremos por uma rodada (mudando gradualmente sua direção $\alpha$ de 0 a $2\pi$) Deixei$R(\alpha)$ denota o raio de $P$ para direção $\alpha$. Nos perguntamos quais são os segmentos$R(\alpha)$ hits e qual é a ordem deles em $R(\alpha)$.
3. Descubra todos os segmentos atingidos $R(0)$e classifique-os por ordem em $R(0)$. Armazene-os em uma árvore de pesquisa binária equilibrada (por exemplo, árvore vermelho-preta).
4. Faça uma iteração sobre os pontos encontrados (e classificados) na etapa 1: cada ponto $(\theta,\rho)$ indica que um segmento iniciaria / pararia de atingir o raio $R(\alpha)$ quando $\alpha$ aumentar para $\theta$. Atualize a árvore de pesquisa binária de acordo.
5. Os elementos que antes eram os menores na árvore de pesquisa binária são os segmentos visíveis de $P$.

É fácil verificar se o tempo de execução do algoritmo acima é $O(n \log n)$.

Podemos fazer uma varredura radial de linha para resolver o problema -

Classifique os pontos finais dos segmentos de linha com o ângulo da união da linha $P$ e o ponto final $Q$ fazer, quebrar laços wrt distância de $P$. Agora, quando varremos radialmente (no sentido horário), mantemos dois tipos de eventos 'abertos' e 'fechados', que correspondem à abertura e fechamento de algum novo segmento de linha. Acompanhe quantos segmentos de linha estão 'ativos' a qualquer momento ('ativo' significa que encontramos o ponto final que corresponde ao evento 'aberto' do segmento de linha, mas não encontramos o outro ponto final no varrer ainda). Se em algum momento tivermos exatamente um segmento de linha 'ativo', esse segmento será visível em$P$.

Devemos tomar cuidado para que, ao iniciar a varredura, sempre comecemos em algum evento 'aberto'.

Haverá $2n$esses eventos e acompanhar o número de segmentos ativos podem ser realizados em tempo constante por segmento (por meio de uma tabela de hash ou tempo de logaritmo, usando uma BST balanceada). Portanto, o passo dominante no algoritmo é a classificação que leva$\mathcal{O}(n)$ tempo conforme necessário.

Como em todos os problemas de geometria computacional, pode haver alguns casos de esquecimento que eu negligenciei, mas a ideia geral de que, em algum ponto do tempo durante a varredura radial da linha, se tivermos exatamente um segmento de linha ativo, será visível a partir de $P$ é o ponto crucial para resolver esse problema.