Algorithme pour calculer un diagramme Voronoi sur une sphère?

StackOverflow https://stackoverflow.com/questions/545870

Question

Je suis à la recherche d'un simple (si elle existe) algorithme pour trouver le diagramme Voronoi pour un ensemble de points sur la surface d'une sphère. Le code source serait génial. Je suis un homme Delphi (oui, je sais ...), mais je mange C code aussi.

Était-ce utile?

La solution

Voici un document sur sphérique Voronoi diagrammes .

Ou si vous assimilez Fortran (bleah!) Il y a ce site .

Autres conseils

Mise à jour en Juillet 2016:

Merci à un certain nombre de bénévoles (en particulier Nikolai Nowaczyk et moi), il est maintenant beaucoup plus code robuste / correct pour la manipulation des diagrammes Voronoi sur la surface d'une sphère en Python. Ceci est officiellement disponible en scipy.spatial.SphericalVoronoi de la version 0.18 de scipy partir. Il y a un exemple de travail d'utilisation et de traçage dans le docs .

L'algorithme suit la complexité quadratique du temps. Alors que loglinear est l'optimum théorique pour les diagrammes Voronoi sur les surfaces des sphères, c'est actuellement le meilleur que nous avons été en mesure de mettre en œuvre. Si vous souhaitez en savoir plus et aider à l'effort de développement, il y a quelques questions en suspens liées à l'amélioration de la façon dont Python gère les diagrammes de Voronoï sphériques et les structures de données associées:

Pour plus d'arrière-plan sur la théorie / développement / défis liés à ce code Python et les efforts de géométrie computationnelle connexes vous pouvez également consulter des entretiens de Nicolas et moi:

Réponse d'origine:

Je l'ai fait récemment écrit un code Python open source pour les diagrammes Voronoi sur la surface d'une sphère: https: / /github.com/tylerjereddy/py_sphere_Voronoi

L'utilisation, algorithme, et les limites sont documentées sur readthedocs ( http: //py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html ). Il y a quelques exemples détaillés là-bas, mais je vais placer un ou deux ci-dessous ainsi. Le module gère également le calcul des zones de surface de la région Voronoi, malgré quelques lacunes numériques dans la version de développement actuelle.

Je ne l'ai pas vu de nombreuses implémentations open source pour les diagrammes de Voronoï sphériques bien documentées, mais il y a eu un peu de buzz autour de la mise en œuvre JavaScript sur le site Web de Jason Davies ( http://www.jasondavies.com/maps/voronoi/ ). Je ne pense pas que son code est ouvert cependant. J'ai vu aussi un blog sur l'utilisation de Python pour faire face à une partie du problème ( http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/ ). Un grand nombre des principales sources de la littérature citées dans les postes ci-dessus semblent très difficiles à mettre en œuvre (j'ai essayé certains d'entre eux), mais peut-être que certaines personnes trouveront ma mise en œuvre utile ou même de suggérer des moyens de l'améliorer.

Exemples:

1) Produire un diagramme de Voronoï pour un ensemble de points pseudo-aléatoire sur la sphère unité: 

import matplotlib
import matplotlib.pyplot as plt
import matplotlib.colors as colors
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np
import scipy as sp
import voronoi_utility
#pin down the pseudo random number generator (prng) object to avoid certain pathological generator sets
prng = np.random.RandomState(117) #otherwise, would need to filter the random data to ensure Voronoi diagram is possible
#produce 1000 random points on the unit sphere using the above seed
random_coordinate_array = voronoi_utility.generate_random_array_spherical_generators(1000,1.0,prng)
#produce the Voronoi diagram data
voronoi_instance = voronoi_utility.Voronoi_Sphere_Surface(random_coordinate_array,1.0)
dictionary_voronoi_polygon_vertices = voronoi_instance.voronoi_region_vertices_spherical_surface()
#plot the Voronoi diagram
fig = plt.figure()
fig.set_size_inches(2,2)
ax = fig.add_subplot(111, projection='3d')
for generator_index, voronoi_region in dictionary_voronoi_polygon_vertices.iteritems():
   random_color = colors.rgb2hex(sp.rand(3))
   #fill in the Voronoi region (polygon) that contains the generator:
   polygon = Poly3DCollection([voronoi_region],alpha=1.0)
   polygon.set_color(random_color)
   ax.add_collection3d(polygon)
ax.set_xlim(-1,1);ax.set_ylim(-1,1);ax.set_zlim(-1,1);
ax.set_xticks([-1,1]);ax.set_yticks([-1,1]);ax.set_zticks([-1,1]); 
plt.tick_params(axis='both', which='major', labelsize=6)

entrer image description ici

2) Calculer les zones de surface des polygones de région de Voronoi et de vérifier que la zone de surface reconstituée est raisonnable: 

import math
dictionary_voronoi_polygon_surface_areas = voronoi_instance.voronoi_region_surface_areas_spherical_surface()
theoretical_surface_area_unit_sphere = 4 * math.pi
reconstituted_surface_area_Voronoi_regions = sum(dictionary_voronoi_polygon_surface_areas.itervalues())
percent_area_recovery = round((reconstituted_surface_area_Voronoi_regions / theoretical_surface_area_unit_sphere) * 100., 5)
print percent_area_recovery
97.87551 #that seems reasonable for now

Notez que la triangulation de Delaunay sur une sphère est juste la coque convexe. Ainsi, vous pouvez calculer la coque convexe 3D (par exemple en utilisant CGAL) et prendre le double.

Il y a un document de l'INRIA sur le Triangulation de Delaunay (DT) de points situés sur une sphère: CAROLI , Manuel et al. cace robustes et fi Ef triangulations de Delaunay de points sur ou à proximité d'une sphère. 2009. où ils parlent d'une mise en œuvre CGAL .

Le document se réfère à différentes mesures d'application des algorithmes disponibles DT.

Je cite le document:

  

Une réponse simple et standard consiste dans le calcul de la coque convexe 3D   des points, ce qui est notoirement équivalent.

pour le calcul de l'enveloppe convexe du papier suggère:

  1. Hull, un programme d'enveloppes convexes.
  2. Qhull .
  3. trois dimensions coques convexes. en FORTRAN. trois dimensions coques convexes.
  4. STRIPACK FORTRAN.

La classe DT C ++ de la méthode CGAL a dual pour obtenir le diagramme Voronoi.

Selon cette post par Monique Teillaud (l'un des auteurs du document mentionné ci-dessus), il me semble que en Novembre 2012, la mise en œuvre n'a pas été encore prêt.

Il a été un moment depuis que la question a été répondu, mais je l'ai trouvé deux documents qui implémentent algorithme de fortune (O efficacité (N lg N), la mémoire O (N)) sur la surface de la sphère. Peut-être un spectateur avenir trouver cette information utile.

  • « Balayer la sphère » par Dinis et Mamede, publié en 2010 Symposium international sur les diagrammes de Voronoï en sciences et en génie. Peut être acheté http://dx.doi.org/10.1109/ISVD.2010.32
  • « Un balayage de plan pour l'algorithme de Voronoï Tessellation de la Sphère » par Zheng et al. Je ne suis pas sûr qu'il a été publié en raison de la première, mais il est daté du 13 Décembre 2011. Il est disponible gratuitement à l'adresse http://www.e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf

Je travaille par moi-même en ce moment, donc je ne peux pas l'expliquer bien. L'idée de base est que l'algorithme de Fortune travaille sur la surface de la sphère tant que vous calculer correctement les paraboles de délimitation des points. Parce que la surface de l'enveloppe sphère, vous pouvez également utiliser une liste circulaire pour contenir la ligne de plage et ne pas se soucier de cellules de manutention au bord de l'espace rectangulaire. Avec cela, vous pouvez balayer du pôle nord de la sphère au sud et à sauvegarder à nouveau, en sautant sur des sites qui introduisent de nouveaux points à la ligne de plage (en ajoutant une parabole à la ligne de plage) ou l'introduction de sommets de la cellule (la suppression d'un parabola de la ligne de plage).

Les deux documents s'attendent à un haut niveau de confort avec l'algèbre linéaire pour comprendre les concepts, et ils ont tous deux continuent à me perdre au point qu'ils commencent à expliquer l'algorithme lui-même. Ni fournir le code source, malheureusement.

Je pense que le plan de Voronoi pour chaque point peut être construit en utilisant la géométrie non-euclidienne. Ce qui était normalement une ligne sur un plan 2D, est maintenant un 'grand cercle' sur la sphère (voir Wikipedia: la géométrie elliptique ). Il est facile de trouver les points sont du mauvais côté d'un grand cercle entre deux points, en tournant simplement la sphère telle que le grand cercle de division est l'équateur, et il est tous les points de l'autre hémisphère que le point que vous êtes la construction du plan Voronoi pour.

Ce n'est pas toute la réponse, mais c'est là que je commencerais ..

Il y a un joli exemple de programme de diagramme de Voronoï (y compris le code source Delphi 5/6).

Je pense que « points sur la surface d'une sphère » signifie que vous devez d'abord remappez 2D coordonnées, créer le diagramme de Voronoï puis les remapper à la sphère des coordonnées de surface. Les deux formules de article cartographie Wikipédia UV travailler ici?

Notez également que le diagramme de Voronoï aura la mauvaise topologie (il est à l'intérieur d'un rectangle et ne pas « enrouler autour »), ici, il pourrait aider à copier tous les points de (0,0) - (x, y) aux régions voisines ci-dessus (0, -y * 2) - (x, 0), ci-dessous (0, y) - (x, y * 2), à gauche (-x, 0) - (0, y) et à droite (x, 0) - (x * 2, y). J'espère que vous savez ce que je veux dire, ne hésitez pas à demander:)

CGAL travaille sur le paquet « noyau sphérique », qui permettrait de calculer exactement ce genre de choses . Malheureusement, est pas encore sorti , mais ce sera peut-être dans leur prochaine version, étant donné qu'ils ont déjà il mentionné dans une conférence tech Google mars

Je cite cette référence: http://www.qhull.org/html/qdelaun.htm

  

Pour calculer la triangulation de Delaunay de points sur une sphère, calculer leur enveloppe convexe. Si la sphère est la sphère unité à l'origine, la facette Normales sont les sommets de Voronoï de l'entrée.

Si vos points sont dans l'hémisphère, vous pourriez faire une projection gnomonique de sphérique à des coordonnées planes, puis trianguler, car de grands cercles deviennent des lignes droites de la distance la plus courte.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top