Convergência de ponto de interrupção no algoritmo da Fortune

Question

Estou implementando o algoritmo de varredura da Fortune para calcular diagramas de Voronoi.Minha referência principal é "Geometria Computacional:Algoritmos e Aplicações" de de Berg et al., e embora a cobertura do tópico seja muito clara, eles ignoram vários detalhes pequenos, mas importantes, que tenho tido dificuldade em resolver sozinho.Pesquisei ajuda na web, mas outros sites fornecem uma visão geral ainda mais ampla do que o livro ou fornecem exatamente o mesmo pseudocódigo fornecido pelo livro.

Preciso de uma maneira de determinar se um par de pontos de interrupção determinados por um triplo de arcos na linha da praia converge ou diverge, a fim de detectar eventos circulares futuros.Parece que para tomar uma decisão eu precisaria de conhecimento sobre a forma das bordas das células de Voronoi que os pontos de interrupção traçam à medida que o algoritmo de Fortune avança.Por exemplo, se eu pudesse encontrar a inclinação da aresta traçada por um ponto de interrupção, poderia calcular onde as duas linhas formadas pelos pontos de interrupção e suas respectivas inclinações se cruzam e decidir se elas convergem com base nesse resultado.Porém, não tenho ideia de como obter informações sobre as encostas, apenas a posição atual dos breakpoints.

A única informação com a qual tenho que trabalhar é a localização x,y dos três locais e a coordenada y atual da linha de varredura (estou usando uma linha de varredura horizontal).

Na verdade, tenho uma ideia para determinar a convergência.Dados dois locais, o ponto de interrupção entre as duas seções da linha de praia que eles definem é governado apenas pela posição atual da linha de varredura.Pensei em registrar a posição dos dois pontos de interrupção, avançando temporariamente um pouco a linha de varredura e registrando suas novas posições.Como as arestas em um diagrama de Voronoi normal não se curvam, se a distância entre o novo par de pontos de interrupção for menor que a distância entre o par antigo, então os pontos de interrupção convergem;caso contrário, eles divergem.Mas isso parece perigoso (não tenho ideia se sempre funciona) e feio.Certamente deve haver uma maneira melhor.

Qualquer idéia seria apreciada, e pseudocódigo (em uma sintaxe semelhante a C #, se possível), especialmente.Também estou ciente de que existem bibliotecas de geometria computacional que eu poderia usar para obter diagramas de Voronoi, mas este é um exercício de aprendizado pessoal, então quero implementar eu mesmo todas as partes do algoritmo.

Answer 1

Bem vindo Drake.Eu o implementei verificando se os pontos de interrupção convergem fisicamente para o centro do círculo em um incremento 'fictício' da posição da linha de varredura.Na verdade, isso se complica um pouco porque em certos casos o centro do círculo pode estar quase ou precisamente na posição da linha de varredura, portanto o incremento da linha de varredura precisa ser proporcional à diferença entre a posição atual da linha de varredura e o centro do círculo gerado conforme você recomenda.

Dizer:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (e estamos nos movendo para baixo, ou seja,na direção decrescente de y).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (o divisor 10,0f é escolhido arbitrariamente).

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

Eu sei que isso provavelmente é muito caro, já que você precisa calcular as posições dos pontos de interrupção várias vezes, mas tenho certeza de que isso cuidará de todos os casos possíveis.

De qualquer forma, estou encontrando sérios problemas com erros de precisão de ponto flutuante em outras partes do algoritmo.Definitivamente não é tão simples quanto pensei inicialmente.

Answer 2

Portanto, isso é um tanto embaraçoso, mas depois de dormir sobre o problema, a resposta parece óbvia.Estou escrevendo isso para ajudar os alunos no futuro com a mesma pergunta que eu.

A borda de Voronoi entre dois locais corta perpendicularmente o segmento de linha (imaginário) que conecta os locais.Você poderia derivar a inclinação da aresta tomando a perpendicular da inclinação do segmento de linha de conexão e, em seguida, realizando um teste de intersecção de linha nas duas arestas, mas há uma maneira ainda mais fácil.

Contanto que três sites sejam não colinear, então as arestas que cortam perpendicularmente os segmentos entre os locais também são tangentes ao círculo cuja aresta contém todos os três locais.Portanto, os pontos de interrupção definidos por um triplo de sítios de Voronoi convergem se o centro do círculo definido pelos três sítios estiver na frente do meio local, onde "na frente" e "atrás" dependem do sistema de coordenadas e do alinhamento da linha de varredura que você escolheu.

No meu caso, eu tenho uma varredura horizontal que estou movendo do mínimo y para o máximo y, então os pontos de interrupção convergem se a coordenada y do centro do círculo for maior que a coordenada y do site do meio e divergem caso contrário .

Editar:Kristian D'Amato aponta corretamente que o algoritmo acima perde alguns casos de convergência.O algoritmo final que acabei usando está abaixo.Claro, não tenho certeza de que esteja 100% correto, mas parece funcionar em todos os casos em que experimentei.

Given left, middle, right sites
    if they are collinear, return false
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right)
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center)

IsRightOfLine(start, end, point)
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0

Answer 3

Se os locais estiverem ordenados no sentido horário em torno do centro do círculo, o arco está convergindo.Se eles estiverem ordenados no sentido anti-horário em torno do centro do círculo, o arco será divergente.(ou vice-versa, dependendo da sua implementação).O teste de cw ou ccw está fora do código que você usa para encontrar o centro do círculo.

Aqui está um trecho de código C# para calcular o circuncentro d dos pontos a,b,c:

        Vector2 ba = b - a;
        Vector2 ca = c - a;     
        float baLength = (ba.x * ba.x) + (ba.y * ba.y);
        float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
        float denominator = 2f * (ba.x * ca.y - ba.y * ca.x);   
        if (denominator <= 0f ) { // Equals 0 for colinear points.  Less than zero if points are ccw and arc is diverging.
            return false;  // Don't use this circle event!
        };
        d.x = a.x + (ca.y * baLength - ba.y * caLength) / denominator ;
        d.y = a.y + (ba.x * caLength - ca.x * baLength) / denominator ;