Convergence des points d'arrêt dans l'algorithme de Fortune

Question

J'implémente l'algorithme Sweepline de Fortune pour calculer les diagrammes de Voronoi.Ma référence principale est "Géométrie computationnelle :Algorithmes et applications" de de Berg et al., et bien que leur couverture du sujet soit très claire, ils passent sous silence plusieurs détails petits mais importants que j'ai eu du mal à résoudre moi-même.J'ai cherché de l'aide sur le Web, mais d'autres sites Web donnent un aperçu encore plus complet que le manuel ou donnent exactement le même pseudocode que celui fourni par le livre.

J'ai besoin d'un moyen de déterminer si une paire de points d'arrêt déterminés par un triple d'arcs sur la ligne de plage converge ou diverge, afin de détecter les événements circulaires à venir.Il semble que pour prendre une décision, j'aurais besoin de connaître la forme des bords des cellules de Voronoï que tracent les points d'arrêt au fur et à mesure de la progression de l'algorithme de Fortune.Par exemple, si je pouvais trouver la pente du bord tracé par un point d'arrêt, je pourrais calculer l'endroit où les deux lignes formées par les points d'arrêt et leurs pentes respectives se croisent, et décider si elles convergent en fonction de ce résultat.Cependant, je ne sais pas comment obtenir des informations sur les pistes, seulement la position actuelle des points d'arrêt.

La seule information avec laquelle je dois travailler est l'emplacement x,y des trois sites et la coordonnée y actuelle de la ligne de balayage (j'utilise une ligne de balayage horizontale).

En fait, j'ai une idée pour déterminer la convergence.Étant donné deux sites, le point de rupture entre les deux sections de la ligne de plage qu'ils définissent est régi uniquement par la position actuelle de la ligne de balayage.J'ai pensé à enregistrer la position des deux points d'arrêt, à avancer temporairement un peu la ligne de balayage et à enregistrer leurs nouvelles positions.Étant donné que les arêtes d'un diagramme de Voronoï normal ne se courbent pas, si la distance entre la nouvelle paire de points d'arrêt est inférieure à la distance entre l'ancienne paire, alors les points d'arrêt convergent ;sinon, ils divergent.Mais cela semble à la fois dangereux (je ne sais pas si cela fonctionne toujours) et moche.Il doit certainement exister un meilleur moyen.

Toutes les idées seraient appréciées, et le pseudocode (dans une syntaxe de type C# si possible) en particulier.Je suis également conscient qu'il existe des bibliothèques de géométrie computationnelle que je pourrais utiliser pour obtenir des diagrammes de Voronoï, mais il s'agit d'un exercice d'apprentissage personnel, je souhaite donc implémenter moi-même toutes les parties de l'algorithme.

Answer 1

Bienvenue Drake.Je l'ai implémenté en vérifiant si les points d'arrêt convergent physiquement vers le centre du cercle dans un incrément « fictif » de la position de la ligne de balayage.Cela se complique un peu car dans certains cas, le centre du cercle peut être presque ou précisément à la position de la ligne de balayage, donc l'incrément de la ligne de balayage doit être proportionnel à la différence entre la position actuelle de la ligne de balayage et le centre du cercle généré, comme vous le recommandez.

Dire:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (et nous descendons, c'est-à-diredans la direction y décroissante).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (le diviseur 10,0f est arbitrairement choisi).

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.

Je sais que cela coûte probablement très cher, car vous devez calculer les positions des points d'arrêt plusieurs fois, mais je suis convaincu que cela prend en charge tous les cas possibles.

Quoi qu'il en soit, je trouve de sérieux problèmes d'erreur de précision en virgule flottante ailleurs dans l'algorithme.Certainement pas aussi simple que je le pensais au départ.

Answer 2

C'est donc plutôt embarrassant, mais après avoir dormi sur le problème, la réponse semble évidente. J'écris cela pour espérer aider les élèves à l'avenir avec la même question que moi.

Le bord Voronoi entre deux sites se divise perpendiculairement le segment de ligne (imaginaire) connectant les sites. Vous pouvez dériver la pente du bord en prenant la perpendiculaire de la pente du segment de ligne de connexion, puis effectuez un test d'intersection de la ligne sur les deux bords, mais il existe un moyen encore plus facile.

Tant que trois sites sont pas Collineear , puis les bords qui se blottissent perpendiculairement les segments entre les sites sont également tangents au cercle dont le bord contient les trois sites. Par conséquent, les points d'arrêt définis par un triple de sites Voronoi convergent si le centre du cercle défini par les trois sites est devant le site Moyen , où "devant" et "derrière" dépend de la coordonnée Système et alignement d'une balle d'ajoncs que vous avez choisi.

Dans mon cas, j'ai une boulette horizontale que je passe du minimum Y au maximum Y, de sorte que les points d'arrêt convergent si la coordonnée Y du centre du cercle est supérieure à la coordonnée Y du site du milieu, et diverger autrement.

EDIT: Kristian D'Amato souligne légitimement que l'algorithme ci-dessus manque des cas de convergence. L'algorithme final que j'ai fini par utiliser est ci-dessous. Bien sûr, je ne suis pas convaincu que ses 100% correct, mais il semble fonctionner pour tous les cas que j'ai essayés.

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

Si les sites sont commandés dans le sens des aiguilles d'une montre autour du centre du cercle, l'arc convergeait.S'ils sont commandés dans le sens antihoraire autour du centre du cercle, l'arc est divergeant.(ou vice versa, en fonction de votre mise en œuvre).Les tests pour CW ou CCW sont sortis du code que vous utilisez pour trouver le centre du cercle.

Voici un extrait de code C # pour calculer le circonstancer D de points 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 ;