|
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 -*- |
|
6846
|
21 ## @deftypefn {Function File} {[@var{idx}, @var{p}] =} tsearchn (@var{x}, @var{t}, @var{xi}) |
|
6823
|
22 ## Searches for the enclosing Delaunay convex hull. For @code{@var{t} = |
|
|
23 ## delaunayn (@var{x})}, finds the index in @var{t} containing the |
|
|
24 ## points @var{xi}. For points outside the convex hull, @var{idx} is NaN. |
|
7001
|
25 ## If requested @code{tsearchn} also returns the barycentric coordinates @var{p} |
|
6823
|
26 ## of the enclosing triangles. |
|
|
27 ## @seealso{delaunay, delaunayn} |
|
|
28 ## @end deftypefn |
|
|
29 |
|
|
30 function [idx, p] = tsearchn (x, t, xi) |
|
|
31 if (nargin != 3) |
|
|
32 print_usage (); |
|
|
33 endif |
|
|
34 |
|
|
35 nt = size (t, 1); |
|
|
36 [m, n] = size (x); |
|
|
37 mi = size (xi, 1); |
|
|
38 idx = nan (mi, 1); |
|
|
39 p = nan (mi, n + 1); |
|
|
40 |
|
|
41 ni = [1:mi].'; |
|
|
42 for i = 1 : nt |
|
|
43 ## Only calculate the Barycentric coordinates for points that have not |
|
|
44 ## already been found in a triangle. |
|
|
45 b = cart2bary (x (t (i, :), :), xi(ni,:)); |
|
|
46 |
|
|
47 ## Our points xi are in the current triangle if |
|
|
48 ## (all(b >= 0) && all (b <= 1)). However as we impose that |
|
|
49 ## sum(b,2) == 1 we only need to test all(b>=0). Note need to add |
|
|
50 ## a small margin for rounding errors |
|
|
51 intri = all (b >= -1e-12, 2); |
|
|
52 idx(ni(intri)) = i; |
|
|
53 p(ni(intri),:) = b(intri, :); |
|
|
54 ni(intri) = []; |
|
|
55 endfor |
|
|
56 endfunction |
|
|
57 |
|
|
58 function Beta = cart2bary (T, P) |
|
|
59 ## Conversion of Cartesian to Barycentric coordinates. |
|
|
60 ## Given a reference simplex in N dimensions represented by a |
|
|
61 ## (N+1)-by-(N) matrix, and arbitrary point P in cartesion coordinates, |
|
|
62 ## represented by a N-by-1 row vector can be written as |
|
|
63 ## |
|
|
64 ## P = Beta * T |
|
|
65 ## |
|
|
66 ## Where Beta is a N+1 vector of the barycentric coordinates. A criteria |
|
|
67 ## on Beta is that |
|
|
68 ## |
|
|
69 ## sum (Beta) == 1 |
|
|
70 ## |
|
|
71 ## and therefore we can write the above as |
|
|
72 ## |
|
|
73 ## P - T(end, :) = Beta(1:end-1) * (T(1:end-1,:) - ones(N,1) * T(end,:)) |
|
|
74 ## |
|
|
75 ## and then we can solve for Beta as |
|
|
76 ## |
|
|
77 ## Beta(1:end-1) = (P - T(end,:)) / (T(1:end-1,:) - ones(N,1) * T(end,:)) |
|
|
78 ## Beta(end) = sum(Beta) |
|
|
79 ## |
|
|
80 ## Note below is generalize for multiple values of P, one per row. |
|
|
81 [M, N] = size (P); |
|
|
82 Beta = (P - ones (M,1) * T(end,:)) / (T(1:end-1,:) - ones(N,1) * T(end,:)); |
|
|
83 Beta (:,end+1) = 1 - sum(Beta, 2); |
|
|
84 endfunction |
|
|
85 |
|
|
86 %!shared x, tri |
|
|
87 %! x = [-1,-1;-1,1;1,-1]; |
|
|
88 %! tri = [1, 2, 3]; |
|
|
89 %!test |
|
|
90 %! [idx, p] = tsearchn (x,tri,[-1,-1]); |
|
|
91 %! assert (idx, 1) |
|
|
92 %! assert (p, [1,0,0], 1e-12) |
|
|
93 %!test |
|
|
94 %! [idx, p] = tsearchn (x,tri,[-1,1]); |
|
|
95 %! assert (idx, 1) |
|
|
96 %! assert (p, [0,1,0], 1e-12) |
|
|
97 %!test |
|
|
98 %! [idx, p] = tsearchn (x,tri,[1,-1]); |
|
|
99 %! assert (idx, 1) |
|
|
100 %! assert (p, [0,0,1], 1e-12) |
|
|
101 %!test |
|
|
102 %! [idx, p] = tsearchn (x,tri,[-1/3,-1/3]); |
|
|
103 %! assert (idx, 1) |
|
|
104 %! assert (p, [1/3,1/3,1/3], 1e-12) |
|
|
105 %!test |
|
|
106 %! [idx, p] = tsearchn (x,tri,[1,1]); |
|
|
107 %! assert (idx, NaN) |
|
|
108 %! assert (p, [NaN, NaN, NaN]) |
