Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Although BoundedDiagram function worked well for a small data set, I got errors in a specific case that I cannot explain. I am sorry I am pasting here a large list but you could not verify it otherwise:

Needs["ComputationalGeometry`"];

data2D = {{0., 0.1846}, {-0.1846, 0.}, {0., -0.1846}, {0.1846, 0.}, {0.4189,0.2418}, 
          {0.2418, 0.4189}, {0., 0.4837}, {-0.2418, 0.4189}, {-0.4189, 0.2418}, 
          {-0.4837, 0.},{-0.4189, -0.2418}, {-0.2418, -0.4189}, {0., -0.4837},
          {0.2418, -0.4189}, {0.4189, -0.2418}, {0.4837, 0.}, {0.8455, 0.}, 
          {0.8041, 0.2613}, {0.684, 0.497}, {0.497, 0.684}, {0.2613, 0.8041},
          {0., 0.8455}, {-0.2613, 0.8041}, {-0.497, 0.684}, {-0.684, 0.497},
          {-0.8041, 0.2613}, {-0.8455, 0.}, {-0.8041, -0.2613}, {-0.684, -0.497}, 
          {-0.497, -0.684}, {-0.2613, -0.8041}, {0., -0.8455}, {0.2613, -0.8041}, 
          {0.497, -0.684}, {0.684, -0.497}, {0.8041, -0.2613}, {1.2923, 0.}, 
          {1.2599, 0.2876}, {1.1643, 0.5607}, {1.0103, 0.8057}, {0.8057, 1.0103},
          {0.5607, 1.1643}, {0.2876, 1.2599}, {0., 1.2923}, {-0.2876, 1.2599}, 
          {-0.5607, 1.1643}, {-0.8057, 1.0103}, {-1.0103, 0.8057}, {-1.1643, 0.5607},
          {-1.2599, 0.2876}, {-1.2923, 0.}, {-1.2599, -0.2876}, {-1.1643, -0.5607}, 
          {-1.0103, -0.8057}, {-0.8057, -1.0103}, {-0.5607, -1.1643}, {-0.2876, -1.2599}, 
          {0., -1.2923}, {0.2876, -1.2599}, {0.5607, -1.1643}, {0.8057, -1.0103}, 
          {1.0103, -0.8057}, {1.1643, -0.5607}, {1.2599, -0.2876}};

You can see in

ListPlot[data2D, AspectRatio -> 1, PlotStyle -> PointSize[Large]]

and in

DiagramPlot[data2D] 

that the Voronoi Areas appear clear.

But when using

BoundedDiagram[{{-4, -4}, {4, -4}, {4, 4}, {-4, 4}}, data2D]

I get errors like :

Solve::svars: Equations may not give solutions for all "solve" variables.

BoundedDiagram::nobd: Bounded diagram failed.

If I limit the data set I get correct results (but not always):

BoundedDiagram[{{-4, -4}, {4, -4}, {4, 4}, {-4, 4}}, data2D[[1 ;; 10]]]

Notice that VoronoiDiagram[data2D] produces the correct Voronoi data.

Can anybody explain why this is happening or is it a Mathematica bug ?

Solution

Following Belisarius' advice, I am rolling my own algorithm. Actually I used VoronoiDiagram function (why invent the wheel?). I used a circular bound (of radius 1.5) that seems more appropriate for my application.

v = VoronoiDiagram[data2D];

intersection[ray_, radius_] :=
  Module[{start = ray[[1]], end = ray[[2]], sx, sy, ex, ey, l},
    {sx, sy} = start; {ex, ey} = end;
    l = 
      (sx*ex + sy*ey + Sqrt[(sx*ex + sy*ey)^2 - (ex^2 + ey^2) (sx^2 + sy^2 - radius^2)])/
        (ex^2 + ey^2);
    start + l*(end - start)];

{vorvert, vorval} =
  {Table[
     If[Head[v[[1, i]]] === Ray, 
       intersection[v[[1, i]], radius = 1.5], 
       v[[1, i]]], 
     {i, 1, Length[v[[1]]]}],
   v[[2]]};

DiagramPlot[data2D, vorvert, vorval]

enter image description here

I welcome any improvement - addition.

share|improve this question
    
I am thinking about generalizing for arbitrary boundary shape. This is a challenge! –  tchronis Nov 21 '13 at 21:24
add comment

1 Answer

up vote 4 down vote accepted

The problem is that the high symmetry of the point set results in an ill-conditioned matrix. You can see it from:

BoundedDiagram[1.5 {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},  Union@data2D]

RowReduce::luc: Result for RowReduce of badly conditioned matrix {{0.,-3.,4.5},{1.11022*10^-16,-1.11022*10^-16,0.}} may contain significant numerical errors. >>

So, let's perturb the points slightly:

noise[x_] := x + RandomReal[{0, 10^-4}, 2]
data2DD = noise /@ data2D;
{diagvert1, diagval1} = BoundedDiagram[1.5 {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}}, Union@data2DD];
DiagramPlot[data2DD, diagvert1, diagval1]

Mathematica graphics

share|improve this answer
    
Thanks @belisarius , the original data set was rounded using Round[data2D,0.0001] but the symmetry remained. I see a perturbation can produce the Voronoi vertices , edges and areas but they are still an approximation. In problems where accuracy matters a lot someone cannot afford a close solution. Also are you sure perturbating will always work ? I am taking N-integrals in the Voronoi areas to calculate SER (Symbol Error Rate) in telecommunication systems for very low Noise - so perturbation interferes greatly in my solutions. Thus i cannot adapt the above tweak. –  tchronis Nov 21 '13 at 19:34
1  
@tchronis then I think you'll have to roll your own algorithm paying particular attention to numerical details. –  belisarius Nov 21 '13 at 19:40
    
@tchronis But if the figure isn't going to change you could pick the polygons by hand once ... just a silly idea. –  belisarius Nov 21 '13 at 19:44
    
Picking by hand is not my favorite :-) –  tchronis Nov 22 '13 at 10:42
    
@tchronis Perhaps you misunderstood me. What I had in mind is the following: 1) Calculate your original bounded diagram 2) If it is ill conditioned, perturb the points and recalculate 3) Keep the polygon edges list , and apply to your original point set 4) Verify that this is a valid bounded diagram for the original point set. You'll find the fourth step is usually unnecessary if the perturbations are small enough (smaller than your Round[]) –  belisarius Nov 22 '13 at 11:46
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.