Interseção de Círculo com Algoritmo de Linha de Varredura

15

Infelizmente ainda não sou tão forte em entender o algoritmo da linha de varredura . Todos os trabalhos e livros didáticos sobre o tema já foram lidos, mas o entendimento ainda está longe. Apenas para esclarecer, tento resolver o máximo de exercícios possível. Mas, tarefas realmente interessantes e importantes ainda são um desafio para mim.

O exercício a seguir encontrei nas notas de aula da Intersecção do Segmento de Linha do onipotente Jeff Erickson.

Exercício 2. Descreva e analise um algoritmo de varredura para determinar, dados círculos no plano, se dois se cruzam, em O ( n log n ) . Cada círculo é especificado pelo seu centro e raio, de modo que a entrada consiste em três matrizes X [ 1 .. n ] , Y [ 1 .. n ] e R [ 1 .. n ] . Cuidado para implementar corretamente as primitivas de baixo nível.nO(nlogn)X[1..n],Y[1..n]R[1..n]

Vamos tentar facilitar uma coisa complexa. O que sabemos sobre a interseção de círculos? O analógico pode ser encontrado com a interseção de linhas. Duas linhas podem se cruzar se forem adjacentes, qual propriedade o círculo deve ter para se cruzar? Deixe que é a distância entre o centro dos círculos, r 0 e R 1 centros dos círculos. Considere alguns casos:dr0r1

  • Caso 1: Se então não há soluções, os círculos são separados.d>r0+r1

  • Caso 2: Se então não há soluções porque um círculo está contido no outro.d<|r0r1|

  • Caso 3: Se e r 0 = r 1 , em seguida, os círculos são coincidentes e há um número infinito de soluções.d=0r0=r1

Portanto, parece que as condições de interseção estão prontas, é claro que pode haver condições incorretas. Corrija se for o caso.

Algoritmo. Agora precisamos encontrar algo em comum entre dois círculos que se cruzam. Com a interseção de analógico para linha, precisamos ter condição de inserção e exclusão da condição na fila de eventos. Digamos que o ponto do evento seja a coordenada x do primeiro e do último ponto em que a linha de varredura vertical toca. No primeiro ponto, inserimos o círculo no status e verificamos se há interseção (3 casos para verificação são mencionados acima) com os círculos mais próximos; no último ponto, excluímos o círculo de status .

Parece que é suficiente para o algoritmo da linha de varredura. Se houver algo errado ou se houver algo que deva ser feito de forma diferente, sinta-se à vontade para compartilhar seus pensamentos conosco.

Termo aditivo :

Insiro um círculo quando a linha de varredura vertical toca o círculo pela primeira vez e removo um círculo do status quando a linha de varredura toca pela última vez. A verificação da interseção deve ser feita para o círculo anterior mais próximo. Se adicionamos um círculo ao status e já havia outro círculo que adicionamos antes e ele ainda estava lá, portanto, o círculo anterior não foi "fechado", portanto pode haver uma interseção.

com
fonte
4
onipotente [carece de fontes?]
Jeffe
@com o que você quer dizer com "círculo anterior mais próximo"?
31412 Joe
11
Suponho que statusmantém os círculos atualmente cruzando a linha de varredura? Suponha que você tenha atualmente 100 círculos statuse processe um evento de inserção e insira o 101º círculo. Quantos círculos você compara para verificar a interseção? Como você escolhe quais círculos comparar?
31412 Joe
@ Joe, é exatamente isso que eu preciso, como no algoritmo clássico de linhas de varredura, em que "a interseção de duas linhas implica adjacência dessas duas linhas em algum momento", preciso encontrar o análogo similar com círculos. A coisa mais simples que eu venha com é menor coordenar e y mais alto de coordenadas do círculo, se o círculo se cruzam sua projeção de intervalos do menor y para o mais alto y deve se cruzam para. Então talvez agora eu esteja me aproximando da sua ideia de semicírculos. Os semicírculos acima contêm o y mais alto e , abaixo, o y mais baixo . yyyyyy
com

Respostas:

5

Você está definitivamente no caminho certo. A grande questão é: quando você insere um círculo, quais outros círculos você procura por interseção? Como você realiza essa verificação?

No caso de interseção do segmento de linha, os segmentos de linha em qualquer coordenada x são totalmente ordenados. (Você pode listá-las da coordenada Y mais baixa para a mais alta). Assim, você pode manter os segmentos de linha em uma árvore de pesquisa binária e, ao adicionar um novo segmento, você só precisa descobrir onde ele pertence à árvore de pesquisa binária e verificar seus vizinhos quanto a eventos de interseção.

No caso dos círculos, não está claro imediatamente quais círculos verificar. Se sua resposta for "todos eles", seu algoritmo precisará de algum trabalho.

Você pode descobrir uma maneira de representar os círculos para que eles sejam totalmente ordenados, como são os segmentos de linha?

Tente representar os círculos como dois semi-círculos. Cada evento de inserção é na verdade dois eventos: insira a metade superior e a metade inferior.

Joe
fonte
Infelizmente, eu não entendo a idéia de semicírculos, talvez você considere o semicírculo como uma unidade mínima de círculo que pode ser interceptada (3 casos de interseção: a interseção é no semicírculo superior, ou na parte inferior, ou em ambos). No início, todos os círculos são ordenados pela coordenada x de seus limites esquerdo e direito. Portanto, não devemos considerar x estado coordenado , porque todos os círculos já vêm em x ordem de coordenadas. Portanto, parece mais lógico considerar a coordenada y do centro (do semicírculo) ou qualquer combinação de y e raios. Sua opinião?
244
@com Você precisa do ponto central e do raio para determinar se dois círculos se cruzam, como você fez nas suas próprias verificações de interseção. Apenas a coordenada y e o raio por si só não especificam completamente o limite do círculo. Parece haver algo fundamental nos algoritmos de linha de varredura que você não está entendendo, mas é difícil para mim dizer o que é.
31412 Joe
0

Eu poderia pensar nessa abordagem análoga à varredura de Bentley Ottmann que é executada no tempo O ((n + k) logn).

Eu poderia reduzir o problema da interseção do círculo para a interseção do segmento de linha. Vou considerar o diâmetro vertical paralelo ao eixo Y para cada um dos círculos. O algoritmo deve usar uma linha horizontal que varre o plano de baixo para cima.

Agora temos o ponto final superior, o ponto final inferior para cada um dos círculos. Além disso, precisamos modificar o predicado Intersection para dizer que dois segmentos se cruzam se e somente se a linha de varredura corta os dois círculos em um ponto.

Como o problema de interseção de linha pode ser resolvido no tempo O ((n + k) logn), o mesmo limite também se segue para a interseção de círculo.

Estou bastante convencido de que isso funcionaria, mas se vocês puderem apontar algum caso que isso não resolverá em geral, me avise.

TheGT
fonte