Empty cells with voronoin(...) for centers very close to another
1 visualizzazione (ultimi 30 giorni)
Mostra commenti meno recenti
I am having a very weird problem with the built-in funtion voronoin(..). As a minimum-example try to execute the following code (all the code snippets found here are attached in the file voronoi_empty_cells.m):
longlat = [-118.244619,33.908458;-118.492057,34.015511;-118.244611,33.908424;-118.244612,33.908427;-117.840758,34.085016;-118.305858,34.061761;-118.08201,33.999035;-118.244616,33.908389];
[V,C] = voronoin(longlat);
longlat
V
C
I receive
longlat =
1.0e+02 *
-1.182446190000000 0.339084580000000
-1.184920570000000 0.340155110000000
-1.182446110000000 0.339084240000000
-1.182446120000000 0.339084270000000
-1.178407580000000 0.340850160000000
-1.183058580000000 0.340617610000000
-1.180820100000000 0.339990350000000
-1.182446160000000 0.339083890000000
V =
1.0e+02 *
Inf Inf
-1.175161891466962 0.327928640719027
-1.180897486066318 0.344022006326355
-1.183943270789415 0.339019143878580
-1.183756945093469 0.339449809600732
-1.181979761227092 0.340159730233682
-1.181288370173040 0.338918670025123
-1.182447056666668 0.339084196666667
-1.181504234334189 0.339306037215277
C =
[1x5 double]
[1x3 double]
[1x3 double]
[1x3 double]
[1x4 double]
[1x5 double]
[1x5 double]
[]
Please note that the last cell in C is empty. This is unforeseen behavior since the number of cells should match the number of cell centers (i.e. eight). To understand what is going on I plotted the voronoi cells [A] by using the data from C and V and the patch(...) function and [B] by using voronoi(...).
The blue asterisks denote the vertices in V, the red asterisks the cell centers in longlat. The red polygons where created by method [A] (only polygons not containing inf where plotted) and the blue lines are created by method [B]. At first glance everything seems fine but when scrolling into the point marked by the arrow the following image results.
It appears to me that vertices (1) and (2) do not exist in V and vertex (3) is slightly moved from its actual position. As a result cell 4 (the small triangle cell in the center) does not exist in C (cell 5 is in position 4, cell 6 in position 5, ..., cell 8 is in position 7, and position 8 is empty).
Does anyone know what is going on here?
0 Commenti
Risposte (2)
Walter Roberson
il 13 Ott 2015
veroni is, my sleepy memory thinks, based upon qhull. qhull adds a bit of noise to the point locations in order to avoid degenerate cases (e.g., on lattices.) If you re-run veroni you will probably get a different output. When narrow cells are a natural consequence of the point distribution it may be quite difficult to avoid having a point ending up "misplaced".
2 Commenti
Walter Roberson
il 13 Ott 2015
I do not know about the recent implementations of veronoi(). Notice the references to qhull options in the documentation ? It used to call qhull. And the alternate routine it mentions, veronoin() specifically discusses qhull.
Toby997
il 5 Set 2017
I am experiencing the exact same problem and still haven't found any solution yet... My calculation involves 3d datasets, therefore I have to use voronoin. Any help is highly appreciated!
0 Commenti
Vedere anche
Categorie
Scopri di più su Voronoi Diagram in Help Center e File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!