[OctDev] Re: Changes for the geometry package

[Brad B. <br...@sh...>]

Raphael and Pedro,

Thanks Pedro for your reworking of the Qhull interface for Octave.  I noticed a few items.  I'm not an Octave user so I didn't try out the .m files.  Nor am I a MATLAB user.   I agree with you that compatibility between MATLAB and Octave is a good thing.  

MATLAB will switch to Qhull 2003.1 for R14.

                                                --Brad

--------------------------
Raphael, Pedro's compatibility edit shouldn't effect you.  This line was 
removed for 2002.1 and replaced with a macro qh_VERSION.   In 2003.1, qh_version is defined in global.c.
        //qh_version changed in qhull2003. Line removed for compatibility
        //char qh_version[] = "qhull.oct 2004-01-24";

---------------------------
  sprintf(flags,"qhull %s",options); //Notice that output options will not work. 

Missing check for buffer overflow.   flags is char[255],

----------------------
  //  Qt won't work since it
  // premerges the facets and only afterwards it triangulates.

I noticed some inconsistent usage for Qt/QJ/Q0.  convexn currently uses Q0 while delaunayn() and voronoin() use merged facets.
  
I think you should use 'Qt' for convexn() and delaunayn().   If the data contains singularities, Qhull 'Q0' may produce garbage results.  For example, try
        rbox 1000 W1e-12 | qhull Q0
        <clip>
        qhull precision error: f894 is concave to f1029, since p895 (v153) is 5.107e015 above
        qhull precision error: f1060 is concave to f1115, since p826 (v150) is 3.664e-015 above

QJ guarantees a simplicial result but it perturbs the input.   Qt is approximately 1000 times more accurate.  You should be able to use it.  The end result is a simplicial data structure just like QJ or Q0, but with some facets marked "tricoplanar".  

I understand that MATLAB R14 will use 'Qt' for convexn() and delaunayn() and merged facets for voronoin().

If 'Qt' is used for voronoin() then non-simplicial Delaunay regions generate multiple copies of the corresponding Voronoi vertex:  Compare the following Voronoi diagram of the unit cube centered at the origin.  

> rbox c | qhull v p Qz
3
1
     0      0      0

> rbox c | qhull v p Qz QJ
3
12
2.881346095995534e-011 3.615999963933415e-011 0.7499999999619742
-2.783323571620144e-011 0.7500000000345136 6.739575564296274e-011
-4.608868842126412e-011 -3.874200960041208e-011 0.7499999999619742
2.590405667746154e-011 -0.7499999999641777 4.712574774856648e-011
2.860267578341791e-011 0.7500000000345134 1.095989965449462e-011
1.435529473070574e-011 1.742878064092679e-011 -0.749999999962591
0.7499999998980858 1.958799789036902e-011 6.939693264484959e-011
0.7499999998980858 -8.294376296902328e-011 -3.313482821454272e-011
-4.140066067748194e-011 -3.832711925610965e-011 -0.749999999962591
-3.962064010210042e-011 -0.7499999999641775 -1.839872698639056e-011
-0.7500000000187241 2.902783569069811e-011 -4.421357724382347e-011
-0.7500000000187242 -6.90043022721909e-011 5.381861623021678e-011

> rbox c | qhull v p Qz Qt
3
6
     0      0      0
     0      0      0
     0      0      0
     0      0      0
     0      0      0
     0      0      0

--------------------------------
    // Volume calculation. Copy-paste from geom2.c. qh_getarea didn't give proper results

Volume computation increases run time by about 10%.  It is not needed for most applications.   Should it be optional?    

Volume computation is not implemented for Voronoi diagrams.  For option 'FA', Qhull returns the corresponding Delaunay areas.  If used, it needs to be documented.

I curious why you copy pasted the code.  The original code should work fine.  If you copy-paste, then you may miss out on future improvements to the original code.

------------
EOF

At 10:02 AM 2/2/2004, Pedro Tarrafeta wrote:
>Hi,
>
>I've been working lately on the geometry package. I have written a DLD
>function named qhull that is working properly and that can be used as the
>engine for delaunay(n), voronoi(n) and convhull(n) functions. I have also
>written delaunayn.m voronoin.m and convhulln.m so that they use this new
>qhull function.
>
>This new functions are supposed to work like their Matlab counterparts. Now:
>- [ch, v] convhulln(x), returns ch triangulated (thru Q0 option, not Qt) and
>returns the hulls volume on v, just like Matlab.
>- [V, C] voronoin(x) returns the Voronoi vertices including a first vertex at
>infinity, and the vector array C in the same manner as Matlab (if a reference
>to point 1 is found this means the voronoi cell is unbounded).
>
>qhull function returns:
>
>[H, a, vol, N, O, R, V, C, inf] = qhull (p [,opt])
>
>H : an index vector to the points of the enclosing convex hull.
>a : total area of hull
>vol: total volume of hull
>N : normal vector for each facet
>O : offsets of the hyperplanes
>R : a list with the neighbors to each facet.
>V : voronoi vertex. Only usefull if 'd' or 'v' option specifiedj. Otherwise
> it should return the baricentrum of each facet...
>C : voronoi cells. List related to V
>inf: Vector with ones if corresponding voronoi cell is unbounded, 0 otherwise
>
>I think this gives a better control over the geometry package than what we
>have right now. Also it is more Matlab compatible.
>
>I attach the corresponding files.
>
>Regards,
>Pedro
>
>
>
>
>