Coque convexe de Voronoi Diagramme

J'ai besoin d'un algorithme pour calculer la coque convexe d'un ensemble de points à partir du diagramme de Voronoi des points de O (n). Le diagramme de Voronoï est contenu dans une boîte englobante et est stocké sous la forme d'une liste de bord doublement connexe. L'entrée est une demi-arête dont l'origine est sur la boîte englobante.Coque convexe de Voronoi Diagramme

Je sais que deux points sont adjacents sur la coque convexe ssi ils partagent un bord voronoi infiniment long ...

Source

2010-11-23 wallacer

Pourquoi ne pouvez-vous pas contourner la coque convexe d'un bord infini à l'autre? Je pense que vous voudrez peut-être en dire un peu plus sur la façon dont le problème est représenté, afin que nous puissions comprendre la difficulté. –

Je suppose que la partie la plus difficile du problème est un test pour savoir si une arête particulière sur le diagramme de Voronoi continuerait à l'infini si elle n'était pas délimitée dans le cadre de délimitation. De plus, étant donné que le diagramme de voronoï et la boîte englobante sont stockés sous la forme d'une liste de contours doublement connexe, l'autre partie difficile consiste à déterminer comment traverser correctement le DCEL. De toute façon, j'ai trouvé une solution qui a fonctionné. Peut-être que je vais l'écrire ici bientôt. – wallacer

Si vous avez un cadre de sélection assez grand pour que seules les cellules infinies ont des bords de délimitation, la tâche doesn ne semble pas dur. Itérer à travers les bords de délimitation, pour chacun d'eux, le traverser vers l'avant et l'arrière pour trouver les premiers bords non-limitants F et B. Marquez le courant et tous les bords de délimitation trouvés pendant le cheminement comme used. Les arêtes F et B seraient infinies si la boîte n'existait pas. Ainsi, ils touchent des faces (fF et fB) dont les «centres» font partie de la coque convexe (la face courante est C), et la bordure C-to-F est la partie d'une coque convexe. Prenez la face fF et effectuez une itération à partir du double de F pour trouver le bord non limitatif suivant, par exemple, F1. Si c'est égal à 'B'-twin (ou ses bords limitrophes étaient used), nous avons terminé. Sinon, traversez le prochain voisin ('fF1').

Source

2011-01-27 22:28:27 mbaitoff

Que faire si vous n'avez pas une boîte de délimitation assez grande? –

@uvts_cvs: Cela signifie que tous les points ne sont pas inclus dans le cadre de sélection. Jetez ces points car ils ne peuvent pas être inclus dans la coque convexe. Les points restants ont la même coque convexe que l'ensemble original avait. – mbaitoff

-1

Je crois qu'il est possible de calculer la coque convexe du diagramme de Voronoi en temps O (n). Dans le cas d'un diagramme de Voronoï donné et d'un sommet qui doit résider dans le CH, vous pouvez parcourir les cellules du diagramme de Voronoi et dépenser la coque convexe comme dans l'algorithme de balayage de Grahm mais de manière différente.

Il n'y a qu'une seule théorie qui manque ici, regarder à côté ...

Selon la géométrie computationnelle par Springer le livre M4, théorème 7.4: Un point q est un sommet de Vor (P) si et seulement si son Le plus grand cercle vide C_p (q) contient trois sites ou plus sur sa limite. Cela signifie que les sites qui doivent être vérifiés à chaque itération est fait dans O (1), ce qui signifie que vous n'avez qu'à parcourir les sites O (n).

Selon le théorème 7.3, le nombre de sommets dans le diagramme de Voronoï d'un ste de n points sites dans une plaine au plus 2n-5 (ordre linéaire).

Il est donc possible de calculer le diagramme CH de Voronoï en temps O (n).

Source

2014-07-13 18:57:35 TripleS

Répondre

Questions connexes