recipiente segmento de linha para uma rápida intersecção Ray? (2D)

Question

Eu tenho um raio, eu preciso encontrar o segmento de linha mais próximo que ela atinge. Eu acho que é possível fazer isso em O (log n) tempo, se eu classifico os segmentos de linha em primeiro lugar, mas não me lembro como classificá-los ... Eu acho que algum tipo de árvore que funcionam melhor, mas como é que eu classifico -los por ambos ponto de início e fim? Gostaria também de inserções rápidas para esta estrutura de dados, se possível.

Há um monte de código para um raio contra um segmento de linha, mas eu preciso de algo para um raio vs muitos segmentos de linha ... Eu não sei o que termos para o google para.

Um link para um artigo adequado é bom, código C ++ é ainda melhor. Obrigado! :)

PS: Os segmentos de linha são realmente os lados de um polígono não-auto-interseção, classificados em ordem CCW ... mas eu acho que pode haver alguma vantagem para classificá-los de uma forma diferente

?

Isso tudo é 2D.

---

Pensando bem, eu não estou totalmente certo de que este é possível. Algum tipo de ajuda espacial particionamento poder, mas por outro lado, não posso pensar em alguma maneira de classificar as linhas de modo que pudessem ser comparados com um raio arbitrário.

Answer 1

Você poderia dar uma caixa delimitadora do polígono (min-max coordenadas x, y) e construir uma grade dentro da caixa. Então, para cada célula, lembre-se todas as linhas que cruzam a célula.

Encontre um intesection assim:

• Saiba qual célula os hits ray primeiro (O (1))
• Grade travessia algoritmo para "desenhar" um raio através da grade . Quando você bate célula não vazia, verifique todas as suas linhas, verificar se intersecção está dentro da célula e escolher o cruzamento mais próximo. Se todas as intersecções estão fora da célula, continuar (este é O (comprimento grade)).

Você também pode fazer o hierárquica grade (ou seja, quadtree -. Um árvore que você estavam pedindo), e caminhar-lo usando o mesmo algoritmo. Isto é feito em raytracing em 3D e a complexidade de tempo é O (sqrt ( N)).

---

Se preferir, use a abordagem que eu fiz na minha raytracer:

• quadtree contendo as linhas (construção de quadtree é desribed na artigo) - você dividir nós (= áreas) se eles contêm muitos objetos em 4 sub-nós (sub-áreas)

• Recolha todo folha nós do quadtree que são atingidos pelo raio:

  Compute raio retângulo interseção (não é difícil) para a raiz. Se a raiz é atingido pelo raio, prosseguir com os seus filhos de forma recursiva.

A coisa legal sobre isso é que quando um nó de árvore é não hit, você ignorou o processamento de sub-árvore inteira (potencialmente uma grande área retangular).

No final, isso é equivalente a atravessar a grade - você recolher as menores células no caminho do raio, e, em seguida, testar todos os objetos nelas para cruzamento. Você apenas tem que testar todas elas e escolher o cruzamento mais próximo (para que você explore todas as linhas no caminho de ray).

Este é O (sqrt (N)).

Na passagem de grade, quando você encontrar uma interseção, você pode parar de procurar. Para conseguir isso com travessia quadtree, você teria que seach as crianças na ordem certa - quer classificar os 4 rect cruzamentos por distância ou habilmente atravessar a grade de 4 células (um estamos de volta ao percurso)

.

Esta é apenas uma abordagem diferente, comparativamente mesmo difícil de implementar penso eu, e funciona bem (eu testei em dados reais - O (sqrt (N))). Novamente, você só iria beneficiar dessa abordagem se você tiver pelo menos um par de linhas, quando o polígono tem 10 bordas do benefício em comparação com apenas testando todos eles seria pouco, eu acho.

Answer 2

Você está procurando / métodos ativos de mesa Borda scanline base? Você pode dar uma olhada na entrada da Wikipedia para Scanline Rendering ou procure o Gráficos Gems diretório para os algoritmos (principalmente C, mas alguns código C ++ também) .

Answer 3

Tenha em mente que a classificação é um O (n log n) operação na melhor das hipóteses. Você pode ser melhor fora apenas verificando cada um individualmente.

Answer 4

Como você está certo de que você vai bater qualquer um deles? Se eles são linhas, é improvável.

Se for realmente um polígono (ou seja planar) que você está tentando teste, a maneira usual de fazer esse tipo de coisa é se cruzam com o plano em primeiro lugar, em seguida, teste esse ponto (nas coordenadas 2D) para dentro / fora polígono.

Talvez eu não entendi o que você está fazendo realmente.

Em cruzamentos gerais acelerando com figuras complexas é feito com o particionamento espacial (e, em seguida, técnicas como MailBoxing, se os testes são caros).

[Update: Eu descaracterizou a intenção original] Você ainda pode usar (2d) de particionamento espacial, mas a sobrecarga pode não valer a pena. teste individual são baratos, se seus polígonos não são complicados que poderia ser mais barato apenas caminhar com eles. É difícil dizer a partir da descrição.

Answer 5

Peça esclarecimentos, isso é correto?

• Você tem um conjunto dinâmico de segmentos de linha L .
• Inquérito: dada qualquer ponto (x, y) e e qualquer direção do raio a partir deste ponto, você quer determinar a linha mais próxima em L (se houver)?

Assim, o ponto (x, y) não é correção? (Poderia ser qualquer ponto, e qualquer direção?)