octave: scripts/geometry/delaunayn.m annotate

annotate scripts/geometry/delaunayn.m @ 31240:bf8f33249e86

delaunayn simplex check consistency and performance improvement (bug #60818) * delaunayn.m: Apply consistent volume calculation across all trivial simplex removal code paths. Vectorize 3D simplex removal code path and minimize function calls within >3D loop for performance improvement. Update FIXME note for future performance improvement. Add input type validation checks. Add BISTs for dimensions other than 2D, simplex removal, and input validation. * etc/News.8.md: Describe function improvements under General Improvements.

author	Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
date	Wed, 28 Sep 2022 14:35:30 -0400
parents	66456820ff59
children	8b75954a4670

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 ##
30564 796f54d4ddbf update Octave Project Developers copyright for the new year John W. Eaton <jwe@octave.org> parents: 30330 diff changeset	3 ## Copyright (C) 2007-2022 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))
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	73 error ("delaunayn: input points must be a two dimensional numeric array.");
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
31240 bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	91 ## Begin check for and removal of trivial simplices
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	92 if (! isequal (T, 0)) # skip trivial simplex check if no simplexes
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	93
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	94 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	95 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	96 else
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	97 tol = 1e3 * eps;
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	98 endif
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	99
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	100 ## 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	101 ## 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	102 ## (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	103 ## 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	104 ## 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	105 ## 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	106 ## 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	107 ## 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	108 ## 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	109 ## from volume calculations.
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	110
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	111 [nt, nd] = size (T); # nt = simplex count, nd = # of simplex points
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	112 dim = nd - 1;
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 ## calculate common origin edge vectors for each simplex (p2-p1,p3-p1,...)
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	115 ## store in 3D array such that:
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	116 ## 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	117 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	118 [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	119
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	120 ## calculate orthogonal simplex volumes for comparison
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	121 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	122
31240 bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	123 ## calculate simplex volumes according to problem dimension
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	124 if (nd == 3)
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	125 ## 2-D: area = cross product of triangle edge vectors
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	126 vol = edge_vecs(:,1,1) .* edge_vecs(:,2,2)...
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	127 - edge_vecs(:,1,2) .* 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	128
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	129 elseif (nd == 4)
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	130 ## 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	131 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	132 (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	133 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	134 - 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	135 (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	136 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	137 + 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	138 (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	139 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	140
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	141 else
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	142 ## >= 4-D: simplex 'volume' proportional to det\|edge_vecs\|
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	143
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	144 ## FIXME: Vectorize this for nD inputs without excessive memory impact
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	145 ## over __delaunayn__ itself. Perhaps with a paged determinant function.
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	146 ## see bug #60818 for speed/memory improvement attempts and concerns.
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	147
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	148 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	149
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	150 ##reshape so det can operate in dim1&2
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	151 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	152
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	153 ## calculate determinant for arbitrary problem dimension
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	154 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	155 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	156 endfor
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	157 endif
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	158
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	159 ## mark simplices with relative volume < tol for removal
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	160 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	161
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	162 ##Remove trivially small simplexes from T
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	163 T(idx, :) = [];
25328 3b96348d5ccd delaunayn.m: Vectorize test for 2-D zero volume simplexes (bug #53689) Rik <rik@octave.org> parents: 25054 diff changeset	164 endif
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	165 endfunction
13746 7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346) Rik <octave@nomad.inbox5.com> parents: 11587 diff changeset	166
31240 bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	167 ## 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	168 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	169 %! 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	170 %! 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	171
31240 bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	172 ## Test 2-D input
19172 4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests. Rik <rik@octave.org> parents: 19164 diff changeset	173 %!testif HAVE_QHULL
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests. Rik <rik@octave.org> parents: 19164 diff changeset	174 %! 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	175 %! 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	176
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests. Rik <rik@octave.org> parents: 19164 diff changeset	177 ## Test 3-D input
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests. Rik <rik@octave.org> parents: 19164 diff changeset	178 %!testif HAVE_QHULL
4318cb91deac delaunayn.m: Slight performance increase and addition of BIST tests. Rik <rik@octave.org> parents: 19164 diff changeset	179 %! 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	180 %! 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	181 %! [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	182
31240 bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	183 ## 3D test with trivial simplex removal
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	184 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	185 %! 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	186 %! 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	187 %! 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	188
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	189 ## 4D single simplex test
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	190 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	191 %! 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	192 %! 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	193 %! 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	194
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	195 ## 4D two simplices test
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	196 %!testif HAVE_QHULL
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	197 %! 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	198 %! 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	199 %! 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	200 %! 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	201
19833 9fc020886ae9 maint: Clean up m-files to follow Octave coding conventions. Rik <rik@octave.org> parents: 19697 diff changeset	202 ## 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	203 %!error <Invalid call> delaunayn ()
31240 bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	204 %!error <input points must be> delaunayn ("abc")
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	205 %!error <input points must be> delaunayn ({1})
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	206 %!error <input points must be> delaunayn (true)
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	207 %!error <input points must be> delaunayn (cat (3, [1 2 3], [4 5 6]))
bf8f33249e86 delaunayn simplex check consistency and performance improvement (bug #60818) Nicholas R. Jankowski <jankowski.nicholas@gmail.com> parents: 30691 diff changeset	208

Mercurial > octave

annotate scripts/geometry/delaunayn.m @ 31240:bf8f33249e86