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

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.$n$$O(n \log n)$$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:$d$$r_{0}$$r_{1}$

• Caso 1: Se então não há soluções, os círculos são separados.$d > r_{0} + r_{1}$

• Caso 2: Se então não há soluções porque um círculo está contido no outro.$d < |r_{0} - r_{1}|$

• 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 = 0$$r_{0} = r_{1}$

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.

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.

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.