[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization
From: |
Nicholas Jankowski |
Subject: |
[Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm |
Date: |
Wed, 30 Jun 2021 00:42:15 -0400 (EDT) |
User-agent: |
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.114 Safari/537.36 |
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/
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, (continued)
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, anonymous, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, A.R. Burgers, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Markus Mützel, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, anonymous, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, anonymous, 2021/06/29
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm,
Nicholas Jankowski <=
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Dmitri A. Sergatskov, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, anonymous, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Dmitri A. Sergatskov, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Dmitri A. Sergatskov, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, anonymous, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, Nicholas Jankowski, 2021/06/30
- [Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm, anonymous, 2021/06/30