|
6823
|
1 ## Copyright (C) 2007 David Bateman |
|
|
2 ## |
|
|
3 ## This file is part of Octave. |
|
|
4 ## |
|
|
5 ## Octave is free software; you can redistribute it and/or modify it |
|
|
6 ## under the terms of the GNU General Public License as published by |
|
|
7 ## the Free Software Foundation; either version 2, or (at your option) |
|
|
8 ## any later version. |
|
|
9 ## |
|
|
10 ## Octave is distributed in the hope that it will be useful, but |
|
|
11 ## WITHOUT ANY WARRANTY; without even the implied warranty of |
|
|
12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|
|
13 ## General Public License for more details. |
|
|
14 ## |
|
|
15 ## You should have received a copy of the GNU General Public License |
|
|
16 ## along with Octave; see the file COPYING. If not, write to the Free |
|
|
17 ## Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
|
|
18 ## 02110-1301, USA. |
|
|
19 |
|
|
20 ## -*- texinfo -*- |
|
|
21 ## @deftypefn {Loadable Function} {@var{T} =} delaunayn (@var{P}) |
|
|
22 ## @deftypefnx {Loadable Function} {@var{T} =} delaunayn (@var{P}, @var{opt}) |
|
|
23 ## Form the Delaunay triangulation for a set of points. |
|
|
24 ## The Delaunay triangulation is a tessellation of the convex hull of the |
|
|
25 ## points such that no n-sphere defined by the n-triangles contains |
|
|
26 ## any other points from the set.\n |
|
|
27 ## The input matrix @var{P} of size [n, dim] contains n points in a space |
|
|
28 ## of dimension dim. The return matrix @var{T} has the size [m, dim+1]. It |
|
|
29 ## contains for each row a set of indices to the points, which describes a |
|
|
30 ## simplex of dimension dim. For example, a 2d simplex is a triangle and 3d |
|
|
31 ## simplex is a tetrahedron. |
|
|
32 ## |
|
|
33 ## Extra options for the underlying Qhull command can be specified by the |
|
|
34 ## second argument. This argument is a cell array of strings. The default |
|
|
35 ## options depend on the dimension of the input: |
|
|
36 ## |
|
|
37 ## @itemize |
|
|
38 ## @item 2D and 3D: @var{opt} = @{'Qt','Qbb','Qc'@} |
|
|
39 ## @item 4D and higher: @var{opt} = @{'Qt','Qbb','Qc','Qz'@} |
|
|
40 ## @end itemize |
|
|
41 ## |
|
|
42 ## If @var{opt} is [], then the default arguments are used. If @var{opt} |
|
|
43 ## is @{'@w{}'@}, then none of the default arguments are used by Qhull. |
|
|
44 ## See the Qhull documentation for the available options. |
|
|
45 ## |
|
|
46 ## All options can also be specified as single string, for example |
|
|
47 ## 'Qt Qbb Qc Qz'. |
|
|
48 ## |
|
|
49 ## @end deftypefn |
|
|
50 |
|
|
51 function t = delaunayn (x, varargin) |
|
|
52 if (nargin < 1) |
|
|
53 print_usage() |
|
|
54 endif |
|
|
55 |
|
|
56 t = __delaunayn__ (x, varargin {:}); |
|
|
57 |
|
|
58 ## Try to remove the zero volume simplices. The volume of the i-th simplex is |
|
|
59 ## given by abs(det(x(t(i,1:end-1),:)-x(t(i,2:end),:)))/prod(1:n) |
|
|
60 ## (reference http://en.wikipedia.org/wiki/Simplex). Any simplex with a |
|
|
61 ## relative volume less than some arbitrary criteria is rejected. The |
|
|
62 ## criteria we use is the volume of the simplex corresponding to an |
|
|
63 ## orthogonal simplex is equal edge length all equal to the edge length of |
|
|
64 ## the original simplex. If the relative volume is 1e3*eps then the simplex |
|
|
65 ## is rejected. Note division of the two volumes means that the factor |
|
|
66 ## prod(1:n) is dropped. |
|
|
67 idx = []; |
|
|
68 [nt, n] = size(t); |
|
|
69 for i = 1 : nt |
|
|
70 X = x(t(i,1:end-1),:) - x(t(i,2:end),:); |
|
|
71 if (abs (det (X)) / sqrt (sum (X .^ 2, 2)) < 1e3 * eps) |
|
|
72 idx = [idx, i]; |
|
|
73 endif |
|
|
74 endfor |
|
|
75 t(idx,:) = []; |
|
|
76 endfunction |
