Mercurial > octave

annotate scripts/geometry/delaunayn.m @ 33587:a56b2283959a default tip @

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
maint: Merge stable to default.
author Markus Mützel <markus.muetzel@gmx.de>
date Thu, 16 May 2024 08:42:51 +0200
parents 2e484f9f1f18
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
27923
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
1 ########################################################################
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
2 ##
32632
2e484f9f1f18 maint: update Octave Project Developers copyright for the new year
John W. Eaton <jwe@octave.org>
parents: 32297
diff changeset
3 ## Copyright (C) 2007-2024 The Octave Project Developers
27918
b442ec6dda5c use centralized file for copyright info for individual contributors
John W. Eaton <jwe@octave.org>
parents: 26376
diff changeset
4 ##
27923
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
5 ## See the file COPYRIGHT.md in the top-level directory of this
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
6 ## distribution or <https://octave.org/copyright/>.
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
7 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
8 ## This file is part of Octave.
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
9 ##
24534
194eb4bd202b maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents: 23220
diff changeset
10 ## Octave is free software: you can redistribute it and/or modify it
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
11 ## under the terms of the GNU General Public License as published by
24534
194eb4bd202b maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents: 23220
diff changeset
12 ## the Free Software Foundation, either version 3 of the License, or
22755
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22323
diff changeset
13 ## (at your option) any later version.
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
14 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
15 ## Octave is distributed in the hope that it will be useful, but
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
16 ## WITHOUT ANY WARRANTY; without even the implied warranty of
22755
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22323
diff changeset
17 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22323
diff changeset
18 ## GNU General Public License for more details.
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
19 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
20 ## You should have received a copy of the GNU General Public License
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6846
diff changeset
21 ## along with Octave; see the file COPYING. If not, see
24534
194eb4bd202b maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents: 23220
diff changeset
22 ## <https://www.gnu.org/licenses/>.
27923
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
23 ##
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
24 ########################################################################
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
25
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
26 ## -*- texinfo -*-
20852
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20158
diff changeset
27 ## @deftypefn {} {@var{T} =} delaunayn (@var{pts})
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20158
diff changeset
28 ## @deftypefnx {} {@var{T} =} delaunayn (@var{pts}, @var{options})
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
29 ## Compute the Delaunay triangulation for an N-dimensional set of points.
20158
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
30 ##
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
31 ## The Delaunay triangulation is a tessellation of the convex hull of a set of
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
32 ## points such that no N-sphere defined by the N-triangles contains any other
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
33 ## points from the set.
19593
446c46af4b42 strip trailing whitespace from most source files
John W. Eaton <jwe@octave.org>
parents: 17744
diff changeset
34 ##
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
35 ## The input matrix @var{pts} of size [n, dim] contains n points in a space of
20158
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
36 ## dimension dim. The return matrix @var{T} has size [m, dim+1]. Each row of
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
37 ## @var{T} contains a set of indices back into the original set of points
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
38 ## @var{pts} which describes a simplex of dimension dim. For example, a 2-D
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
39 ## simplex is a triangle and 3-D simplex is a tetrahedron.
11587
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11563
diff changeset
40 ##
21546
f7f97d7e9294 doc: Wrap m-file docstrings to 79 characters + newline (80 total).
Rik <rik@octave.org>
parents: 20852
diff changeset
41 ## An optional second argument, which must be a string or cell array of
f7f97d7e9294 doc: Wrap m-file docstrings to 79 characters + newline (80 total).
Rik <rik@octave.org>
parents: 20852
diff changeset
42 ## strings, contains options passed to the underlying qhull command. See the
f7f97d7e9294 doc: Wrap m-file docstrings to 79 characters + newline (80 total).
Rik <rik@octave.org>
parents: 20852
diff changeset
43 ## documentation for the Qhull library for details
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
44 ## @url{http://www.qhull.org/html/qh-quick.htm#options}.
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
45 ## The default options depend on the dimension of the input:
11587
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11563
diff changeset
46 ##
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11563
diff changeset
47 ## @itemize
28027
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
48 ## @item 2-D and 3-D: @var{options} = @code{@{"Qt", "Qbb", "Qc"@}}
10821
693e22af08ae Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents: 10793
diff changeset
49 ##
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
50 ## @item 4-D and higher: @var{options} = @code{@{"Qt", "Qbb", "Qc", "Qx"@}}
6826
8618f29520c6 [project @ 2007-08-24 16:02:07 by jwe]
jwe
parents: 6823
diff changeset
51 ## @end itemize
11587
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11563
diff changeset
52 ##
28714
d8dcb36bb904 maint: spellcheck documentation ahead of 6.1 release.
Rik <rik@octave.org>
parents: 28027
diff changeset
53 ## If Qhull fails for 2-D input the triangulation is attempted again with
28027
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
54 ## the options @code{@{"Qt", "Qbb", "Qc", "Qz"@}} which may result in
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
55 ## reduced accuracy.
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
56 ##
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
57 ## If @var{options} is not present or @code{[]} then the default arguments are
19593
446c46af4b42 strip trailing whitespace from most source files
John W. Eaton <jwe@octave.org>
parents: 17744
diff changeset
58 ## used. Otherwise, @var{options} replaces the default argument list.
446c46af4b42 strip trailing whitespace from most source files
John W. Eaton <jwe@octave.org>
parents: 17744
diff changeset
59 ## To append user options to the defaults it is necessary to repeat the
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
60 ## default arguments in @var{options}. Use a null string to pass no arguments.
11587
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11563
diff changeset
61 ##
19164
ba167badef9f Deprecate delaunay3 and extend delaunay to 3-D inputs.
Rik <rik@octave.org>
parents: 17744
diff changeset
62 ## @seealso{delaunay, convhulln, voronoin, trimesh, tetramesh}
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
63 ## @end deftypefn
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
64
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
65 function T = delaunayn (pts, varargin)
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
66
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
67 if (nargin < 1)
6826
8618f29520c6 [project @ 2007-08-24 16:02:07 by jwe]
jwe
parents: 6823
diff changeset
68 print_usage ();
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
69 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
70
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
71 ## NOTE: varargin options input validation is performed in __delaunayn__
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
72 if ((! isnumeric (pts)) || (ndims (pts) > 2))
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
73 error ("delaunayn: input PTS must be a 2-dimensional numeric array");
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
74 endif
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
75
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
76 ## Perform delaunay calculation using either default or specified options
28027
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
77 if (isempty (varargin) || isempty (varargin{1}))
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
78 try
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
79 T = __delaunayn__ (pts);
30691
66456820ff59 delaunayn.m: Emit more meaningful error if triangulation fails.
Markus Mützel <markus.muetzel@gmx.de>
parents: 30564
diff changeset
80 catch err
28027
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
81 if (columns (pts) <= 2)
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
82 T = __delaunayn__ (pts, "Qt Qbb Qc Qz");
30691
66456820ff59 delaunayn.m: Emit more meaningful error if triangulation fails.
Markus Mützel <markus.muetzel@gmx.de>
parents: 30564
diff changeset
83 else
66456820ff59 delaunayn.m: Emit more meaningful error if triangulation fails.
Markus Mützel <markus.muetzel@gmx.de>
parents: 30564
diff changeset
84 rethrow (err);
28027
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
85 endif
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
86 end_try_catch
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
87 else
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
88 T = __delaunayn__ (pts, varargin{:});
2e6dc7e2b191 Use appropriate Qhull options as necessary to obtain triangulation (bug #50494).
Rik <rik@octave.org>
parents: 27923
diff changeset
89 endif
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
90
32297
0e033c4385a5 delaunayn: Also warn for negative integers with large magnitude (bug #64658).
Markus Mützel <markus.muetzel@gmx.de>
parents: 32295
diff changeset
91 ## Avoid erroneous calculations due to integer truncation. See bug #64658.
0e033c4385a5 delaunayn: Also warn for negative integers with large magnitude (bug #64658).
Markus Mützel <markus.muetzel@gmx.de>
parents: 32295
diff changeset
92 ## FIXME: Large integer values in excess of flintmax can lose precision
0e033c4385a5 delaunayn: Also warn for negative integers with large magnitude (bug #64658).
Markus Mützel <markus.muetzel@gmx.de>
parents: 32295
diff changeset
93 ## when converting from (u)int64 to double. Consider modifying
0e033c4385a5 delaunayn: Also warn for negative integers with large magnitude (bug #64658).
Markus Mützel <markus.muetzel@gmx.de>
parents: 32295
diff changeset
94 ## simplex checking to account for large integer math to avoid this
0e033c4385a5 delaunayn: Also warn for negative integers with large magnitude (bug #64658).
Markus Mützel <markus.muetzel@gmx.de>
parents: 32295
diff changeset
95 ## problem.
32295
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
96 if (isinteger (pts))
32297
0e033c4385a5 delaunayn: Also warn for negative integers with large magnitude (bug #64658).
Markus Mützel <markus.muetzel@gmx.de>
parents: 32295
diff changeset
97 if (any (abs (pts(:)) > flintmax ('double')))
32295
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
98 warning (["delaunayn: conversion of large integer values to ", ...
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
99 "double, potential loss of precision may result in " ...
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
100 "erroneous triangulations."]);
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
101 endif
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
102 pts = double (pts);
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
103 endif
eccbf170743f delaunayn: Add precision loss warning for large int inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 32292
diff changeset
104
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
105 ## Begin check for and removal of trivial simplices
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
106 if (! isequal (T, 0)) # skip trivial simplex check if no simplexes
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
107
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
108 if (isa (pts, "single"))
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
109 tol = 1e3 * eps ("single");
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
110 else
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
111 tol = 1e3 * eps;
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
112 endif
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
113
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
114 ## Try to remove the ~zero volume simplices. The volume of the i-th simplex
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
115 ## is given by abs(det(pts(T(i,2:end),:)-pts(T(i,1),:)))/factorial(ndim+1)
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
116 ## (reference http://en.wikipedia.org/wiki/Simplex). Any simplex with a
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
117 ## relative volume less than some arbitrary criteria is rejected. The
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
118 ## criteria we use is the volume of a simplex corresponding to an
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
119 ## orthogonal simplex (rectangle, rectangular prism, etc.) with edge lengths
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
120 ## equal to the common-origin edge lengths of the original simplex. If the
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
121 ## relative volume is 1e3*eps then the simplex is rejected. Note division
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
122 ## of the two volumes means that the factor factorial(ndim+1) is dropped
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
123 ## from volume calculations.
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
124
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
125 [nt, nd] = size (T); # nt = simplex count, nd = # of simplex points
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
126 dim = nd - 1;
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
127
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
128 ## Calculate common origin edge vectors for each simplex (p2-p1,p3-p1,...)
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
129 ## Store in 3-D array such that:
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
130 ## rows = nt simplexes, cols = coordinates, pages = simplex edges
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
131 edge_vecs = permute (reshape (pts(T(:, 2:nd), :).', [dim, nt, dim]), ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
132 [2, 1, 3]) - pts(T(:, 1), :, ones (1, 1, dim));
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
133
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
134 ## Calculate orthogonal simplex volumes for comparison
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
135 orthog_simplex_vols = sqrt (prod (sumsq (edge_vecs, 2), 3));
7795
df9519e9990c Handle single precision eps values
David Bateman <dbateman@free.fr>
parents: 7208
diff changeset
136
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
137 ## Calculate simplex volumes according to problem dimension
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
138 if (nd == 3)
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
139 ## 2-D: area = cross product of triangle edge vectors
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
140 vol = edge_vecs(:,1,1) .* edge_vecs(:,2,2) ...
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
141 - edge_vecs(:,1,2) .* edge_vecs(:,2,1);
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
142
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
143 elseif (nd == 4)
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
144 ## 3-D: vol = scalar triple product [a.(b x c)]
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
145 vol = edge_vecs(:,1,1) .* ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
146 (edge_vecs(:,2,2) .* edge_vecs(:,3,3) - ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
147 edge_vecs(:,3,2) .* edge_vecs(:,2,3)) ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
148 - edge_vecs(:,2,1) .* ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
149 (edge_vecs(:,1,2) .* edge_vecs(:,3,3) - ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
150 edge_vecs(:,3,2) .* edge_vecs(:,1,3)) ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
151 + edge_vecs(:,3,1) .* ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
152 (edge_vecs(:,1,2) .* edge_vecs(:,2,3) - ...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
153 edge_vecs(:,2,2) .* edge_vecs(:,1,3));
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
154
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
155 else
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
156 ## 1-D and >= 4-D: simplex 'volume' proportional to det|edge_vecs|
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
157
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
158 ## FIXME: Vectorize this for n-D inputs without excessive memory impact
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
159 ## over __delaunayn__ itself, or move simplex checking into __delaunayn__;
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
160 ## perhaps with an optimized page-wise determinant.
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
161 ## See bug #60818 for speed/memory improvement attempts and concerns.
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
162 vol = zeros (nt, 1);
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
163
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
164 ## Reshape so det can operate in dim 1&2
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
165 edge_vecs = permute (edge_vecs, [3, 2, 1]);
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
166
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
167 ## Calculate determinant for arbitrary problem dimension
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
168 for ii = 1:nt
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
169 vol(ii) = det (edge_vecs(:, :, ii));
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
170 endfor
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
171 endif
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
172
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
173 ## Mark simplices with relative volume < tol for removal
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
174 idx = (abs ((vol) ./ orthog_simplex_vols)) < tol;
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
175
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
176 ## Remove trivially small simplexes from T
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
177 T(idx, :) = [];
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
178
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
179 ## Ensure CCW node order for consistent outward normal (bug #53397)
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
180 ## simplest method of maintaining positive unit normal direction is to
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
181 ## reverse order of two nodes; this preserves 'nice' monotonic descending
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
182 ## node 1 ordering. Currently ignores 1-D cases for compatibility.
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
183 if (dim > 1 && any (negvol = (vol(! idx) < 0)))
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
184 T(negvol, [2, 3]) = T(negvol, [3, 2]);
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
185 endif
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
186
25328
3b96348d5ccd delaunayn.m: Vectorize test for 2-D zero volume simplexes (bug #53689)
Rik <rik@octave.org>
parents: 25054
diff changeset
187 endif
31548
c8ad083a5802 maint: Clean up m-files before Octave 8.1 release.
Rik <rik@octave.org>
parents: 31253
diff changeset
188
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
189 endfunction
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
190
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
191
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
192 ## Test 1-D input
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
193 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
194 %! assert (sortrows (sort (delaunayn ([1;2]), 2)), [1, 2]);
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
195 %! assert (sortrows (sort (delaunayn ([1;2;3]), 2)), [1, 2; 2, 3]);
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
196
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
197 ## Test 2-D input
19172
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
198 %!testif HAVE_QHULL
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
199 %! x = [-1, 0; 0, 1; 1, 0; 0, -1; 0, 0];
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
200 %! assert (sortrows (sort (delaunayn (x), 2)), [1,2,5;1,4,5;2,3,5;3,4,5]);
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
201
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
202 ## Test 3-D input
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
203 %!testif HAVE_QHULL
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
204 %! x = [-1, -1, 1, 0, -1]; y = [-1, 1, 1, 0, -1]; z = [0, 0, 0, 1, 1];
30330
01de0045b2e3 maint: Shorten some long lines to <= 80 characters (bug #57599)
Rik <rik@octave.org>
parents: 29359
diff changeset
205 %! assert (sortrows (sort (delaunayn ([x(:) y(:) z(:)]), 2)),
01de0045b2e3 maint: Shorten some long lines to <= 80 characters (bug #57599)
Rik <rik@octave.org>
parents: 29359
diff changeset
206 %! [1,2,3,4;1,2,4,5]);
19172
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests.
Rik <rik@octave.org>
parents: 19164
diff changeset
207
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
208 ## 3-D test with trivial simplex removal
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
209 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
210 %! x = [0 0 0; 0 0 1; 0 1 0; 1 0 0; 0 1 1; 1 0 1; 1 1 0; 1 1 1; 0.5 0.5 0.5];
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
211 %! T = sortrows (sort (delaunayn (x), 2));
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
212 %! assert (rows (T), 12);
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
213
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
214 ## 4-D single simplex test
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
215 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
216 %! x = [0 0 0 0; 1 0 0 0; 1 1 0 0; 0 0 1 0; 0 0 0 1];
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
217 %! T = sort (delaunayn (x), 2);
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
218 %! assert (T, [1 2 3 4 5]);
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
219
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
220 ## 4-D two simplices test
31240
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
221 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
222 %! x = [0 0 0 0; 1 0 0 0; 1 1 0 0; 0 0 1 0; 0 0 0 1; 0 0 0 2];
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
223 %! T = sortrows (sort (delaunayn (x), 2));
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
224 %! assert (rows (T), 2);
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 30691
diff changeset
225 %! assert (T, [1 2 3 4 5; 2 3 4 5 6]);
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 11587
diff changeset
226
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
227 ## Test negative simplex produce positive normals
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
228 ## 2-D test
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
229 %!testif HAVE_QHULL <*53397>
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
230 %! x = [-1, 0; 0, 1; 1, 0; 0, -1; 0, 0];
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
231 %! y = delaunayn (x);
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
232 %! edges = permute (reshape (x(y(:, 2:end), :).', [2, 4, 2]), [2, 1, 3]) - ...
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
233 %! x(y(:, 1), :, ones (1, 1, 2));
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
234 %! vol = edges(:,1,1) .* edges(:,2,2) - edges(:,1,2) .* edges(:,2,1);
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
235 %! assert (all (vol >= 0));
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
236
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
237 ## 3-D test
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
238 %!testif HAVE_QHULL <*53397>
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
239 %! x = [[-1, -1, 1, 0, -1]',[-1, 1, 1, 0, -1]',[0, 0, 0, 1, 1]'];
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
240 %! y = delaunayn (x);
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
241 %! edges = permute (reshape (x(y(:, 2:end), :).', [3, 2, 3]), [2, 1, 3]) - ...
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
242 %! x(y(:, 1), :, ones (1, 1, 3));
31248
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
243 %! vol = edges(:,1,1) .* ...
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
244 %! (edges(:,2,2) .* edges(:,3,3) - edges(:,3,2) .* edges(:,2,3)) ...
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
245 %! - edges(:,2,1) .* ...
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
246 %! (edges(:,1,2) .* edges(:,3,3) - edges(:,3,2) .* edges(:,1,3)) ...
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
247 %! + edges(:,3,1) .* ...
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
248 %! (edges(:,1,2) .* edges(:,2,3) - edges(:,2,2) .* edges(:,1,3));
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
249 %! assert (all (vol >= 0));
8b75954a4670 delaunayn: adjust node ordering for positive outward normal vectors (bug #53397)
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31240
diff changeset
250
32292
b262966c853c delaunayn.m: Avoid erroneous simplex removal for integer inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31706
diff changeset
251 ## Avoid integer input erroneous volume truncation
b262966c853c delaunayn.m: Avoid erroneous simplex removal for integer inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31706
diff changeset
252 %!testif HAVE_QHULL <*64658>
b262966c853c delaunayn.m: Avoid erroneous simplex removal for integer inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31706
diff changeset
253 %! pts = [0 0 0; 0 0 10; 0 10 0; 0 10 10; 10 0 0; ...
b262966c853c delaunayn.m: Avoid erroneous simplex removal for integer inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31706
diff changeset
254 %! 10 0 10; 10 10 0; 10 10 10; 5 5 5];
b262966c853c delaunayn.m: Avoid erroneous simplex removal for integer inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31706
diff changeset
255 %! assert (isempty (delaunayn (int32 (pts))), false);
b262966c853c delaunayn.m: Avoid erroneous simplex removal for integer inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31706
diff changeset
256 %! assert (delaunayn (pts), delaunayn (int32 (pts)));
b262966c853c delaunayn.m: Avoid erroneous simplex removal for integer inputs (bug #64658).
Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
parents: 31706
diff changeset
257
19833
9fc020886ae9 maint: Clean up m-files to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 19697
diff changeset
258 ## Input validation tests
28896
90fea9cc9caa test: Add expected error message <Invalid call> to BIST tests for nargin.
Rik <rik@octave.org>
parents: 28714
diff changeset
259 %!error <Invalid call> delaunayn ()
31253
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
260 %!error <input PTS must be> delaunayn ("abc")
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
261 %!error <input PTS must be> delaunayn ({1})
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
262 %!error <input PTS must be> delaunayn (true)
a40c0b7aa376 maint: changes to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 31248
diff changeset
263 %!error <input PTS must be> delaunayn (ones (3,3,3))