[Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm

[Nicholas Jankowski]

Follow-up Comment #14, bug #60818 (project octave):

Attached is an mildly corrected patch - the 2D and 3D cases didn't need /2 and
/6. (forgot they were dropped with the volume/volume calculation.) and I left
a few typos in both 2D and 3D versions. Otherwise it's still the same.

I'll reexamine the timing tomorrow.  When I ran the tests where I manually
wrote out the explicit determinants, i still had the incorrect  (and maybe
faster) tol checks in there. I'm wondering if a correct tol check would make
it and the LU approach comparable in speed. I also excepted to see LU decomp
do better after ~5 or 6 dimensions, but the numbers below were showing that to
still be 2x faster.

the easiest question - is the small simplex test necessary? for matlab
compatibility it is, as they throw out zero-volume simplexes.  with floating
point error determining 'zero-volume' = less than some arbitrary distance from
zero.  maybe we could make an optional flag to disable it, but it needs to be
there by default.

i think one simple case needing small simplex removal.  A simple cube with a
center point:


A = [0 0 0;
     1 0 0;
     0 1 0;
     0 0 1;
     1 1 0;
     1 0 1;
     0 1 1;
     1 1 1;
     0.5 0.5 0.5];

delaunayn(A), size(ans)
ans =

   5   9   2   1
   5   9   3   1
   6   9   2   1
   6   9   4   1
   6   5   9   2
   6   5   8   9
   7   9   3   1
   7   9   4   1
   7   5   9   3
   7   5   8   9
   7   6   9   4
   7   6   8   9

ans =

   12    4


the size before small simplexes were removed, however:

T =

   5   3   2   1
   5   9   2   1
   5   9   3   1
   6   4   2   1
   6   9   2   1
   6   9   4   1
   6   5   8   2
   6   5   9   2
   6   5   8   9
   7   9   3   1
   7   9   4   1
   7   5   9   3
   7   5   8   9
   7   6   9   4
   7   6   8   9

debug> size(T)
ans =

   15    4


with the volumes:

vol =

        0
   0.5000
  -0.5000
        0
  -0.5000
   0.5000
        0
   0.5000
   0.5000
   0.5000
  -0.5000
  -0.5000
  -0.5000
   0.5000
   0.5000


it apparently created three zero volume tetrahedra from the cube faces:

>> A([5 3 2 1], :)
ans =

   1   1   0
   0   1   0
   1   0   0
   0   0   0

>> A([6 4 2 1], :)
ans =

   1   0   1
   0   0   1
   1   0   0
   0   0   0

>> A([6 5 8 2], :)
ans =

   1   0   1
   1   1   0
   1   1   1
   1   0   0



(file #51627)
    _______________________________________________________

Additional Item Attachment:

File name: bug60818-delaunayn-v4.patch    Size:3 KB
   
<https://file.savannah.gnu.org/file/bug60818-delaunayn-v4.patch?file_id=51627>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?60818>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/