Empty cells with voronoin(...) for centers very close to another

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?

Answer 1

[Walter Roberson]

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".

[Lucas Schwartz]

Thank you for your reply! I can't find any evidence for your statement since executing the code in the question multiple times always results in the same values for V and C (up to 15 decimal places).

Do you know the functionality of voronoi(...) since the output of that is correct. Maybe it is possible to extract the data from there?

[Walter Roberson]

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.

Answer 2

[Toby997]

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!