View
127
Download
3
Category
Preview:
Citation preview
Diagramas de Voronoi
Evento de Círculo
HandleCircleEvent(pl)
1. Buscar em T o arco verticalmente acima de pl, que está prestes a desaparecer, e deletar todos os eventos de círculos associados a ele;
2. Deletar a folha que representa p em T. Atualizar as tuplas representando os nodos internos. Rebalancear;
3. Adicionar o centro do círculo causando o evento como um vértice de Voronoi, e criar duas semi-retas correspondentes a este ponto de parada. Atualizar ponteiros;
4. Checar as triplas de arcos consecutivos envolvendo o desaparecimento do arco. Inserir o evento de círculo correspondente se o círculo intersepta a linha da sweepline e não contém nenhum ponto.
Recommended