Mercurial > octave
annotate libinterp/corefcn/tsearch.cc @ 25054:6652d3823428 stable
maint: Update copyright dates in all source files.
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Fri, 30 Mar 2018 09:19:05 -0400 |
parents | 194eb4bd202b |
children | b2917b7858ba |
rev | line source |
---|---|
6823 | 1 /* |
2 | |
25054
6652d3823428
maint: Update copyright dates in all source files.
John W. Eaton <jwe@octave.org>
parents:
24534
diff
changeset
|
3 Copyright (C) 2002-2018 Andreas Stahel |
6823 | 4 |
5 This file is part of Octave. | |
6 | |
24534
194eb4bd202b
maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents:
23662
diff
changeset
|
7 Octave is free software: you can redistribute it and/or modify it |
22755
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22407
diff
changeset
|
8 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:
23662
diff
changeset
|
9 the Free Software Foundation, either version 3 of the License, or |
22755
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22407
diff
changeset
|
10 (at your option) any later version. |
6823 | 11 |
22755
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22407
diff
changeset
|
12 Octave is distributed in the hope that it will be useful, but |
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22407
diff
changeset
|
13 WITHOUT ANY WARRANTY; without even the implied warranty of |
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22407
diff
changeset
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22407
diff
changeset
|
15 GNU General Public License for more details. |
6823 | 16 |
17 You should have received a copy of the GNU General Public License | |
7016 | 18 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:
23662
diff
changeset
|
19 <https://www.gnu.org/licenses/>. |
6823 | 20 |
21 */ | |
22 | |
7016 | 23 // Author: Andreas Stahel <Andreas.Stahel@hta-bi.bfh.ch> |
24 | |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21301
diff
changeset
|
25 #if defined (HAVE_CONFIG_H) |
21301
40de9f8f23a6
Use '#include "config.h"' rather than <config.h>.
Rik <rik@octave.org>
parents:
21200
diff
changeset
|
26 # include "config.h" |
9786
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9245
diff
changeset
|
27 #endif |
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9245
diff
changeset
|
28 |
23662
bd77ab816e43
eliminate obsolete file lo-math.h
John W. Eaton <jwe@octave.org>
parents:
23220
diff
changeset
|
29 #include <cmath> |
bd77ab816e43
eliminate obsolete file lo-math.h
John W. Eaton <jwe@octave.org>
parents:
23220
diff
changeset
|
30 |
6823 | 31 #include "lo-ieee.h" |
32 | |
19877
12ecb7212b44
move some files without external dependencies from dldfcn to corefcn
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
33 #include "defun.h" |
9786
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9245
diff
changeset
|
34 #include "error.h" |
20940
48b2ad5ee801
maint: Rename oct-obj.[cc|h] to ovl.[cc|h] for clarity.
Rik <rik@octave.org>
parents:
20939
diff
changeset
|
35 #include "ovl.h" |
9786
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9245
diff
changeset
|
36 |
10550 | 37 inline double max (double a, double b, double c) |
6823 | 38 { |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
39 if (a < b) |
10550 | 40 return (b < c ? c : b); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
41 else |
10550 | 42 return (a < c ? c : a); |
6823 | 43 } |
44 | |
10550 | 45 inline double min (double a, double b, double c) |
6823 | 46 { |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
47 if (a > b) |
10550 | 48 return (b > c ? c : b); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
49 else |
10550 | 50 return (a > c ? c : a); |
6823 | 51 } |
52 | |
53 #define REF(x,k,i) x(static_cast<octave_idx_type>(elem((k), (i))) - 1) | |
54 | |
55 // for large data set the algorithm is very slow | |
56 // one should presort (how?) either the elements of the points of evaluation | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
57 // to cut down the time needed to decide which triangle contains the |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
58 // given point |
6823 | 59 |
60 // e.g., build up a neighbouring triangle structure and use a simplex-like | |
61 // method to traverse it | |
62 | |
19877
12ecb7212b44
move some files without external dependencies from dldfcn to corefcn
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
63 DEFUN (tsearch, args, , |
21966
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
64 doc: /* -*- texinfo -*- |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
65 @deftypefn {} {@var{idx} =} tsearch (@var{x}, @var{y}, @var{t}, @var{xi}, @var{yi}) |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
66 Search for the enclosing Delaunay convex hull. |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
67 |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
68 For @code{@var{t} = delaunay (@var{x}, @var{y})}, finds the index in @var{t} |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
69 containing the points @code{(@var{xi}, @var{yi})}. For points outside the |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
70 convex hull, @var{idx} is NaN. |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
71 @seealso{delaunay, delaunayn} |
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21724
diff
changeset
|
72 @end deftypefn */) |
6823 | 73 { |
20939
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
74 if (args.length () != 5) |
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
75 print_usage (); |
6823 | 76 |
20799
c349d4c91ce2
eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents:
20555
diff
changeset
|
77 const double eps = 1.0e-12; |
c349d4c91ce2
eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents:
20555
diff
changeset
|
78 |
10550 | 79 const ColumnVector x (args(0).vector_value ()); |
80 const ColumnVector y (args(1).vector_value ()); | |
81 const Matrix elem (args(2).matrix_value ()); | |
82 const ColumnVector xi (args(3).vector_value ()); | |
83 const ColumnVector yi (args(4).vector_value ()); | |
6823 | 84 |
10550 | 85 const octave_idx_type nelem = elem.rows (); |
6823 | 86 |
10550 | 87 ColumnVector minx (nelem); |
88 ColumnVector maxx (nelem); | |
89 ColumnVector miny (nelem); | |
90 ColumnVector maxy (nelem); | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
91 for (octave_idx_type k = 0; k < nelem; k++) |
6823 | 92 { |
10550 | 93 minx(k) = min (REF (x, k, 0), REF (x, k, 1), REF (x, k, 2)) - eps; |
94 maxx(k) = max (REF (x, k, 0), REF (x, k, 1), REF (x, k, 2)) + eps; | |
95 miny(k) = min (REF (y, k, 0), REF (y, k, 1), REF (y, k, 2)) - eps; | |
96 maxy(k) = max (REF (y, k, 0), REF (y, k, 1), REF (y, k, 2)) + eps; | |
6823 | 97 } |
98 | |
20232
a9574e3c6e9e
Deprecate Array::length() and Sparse::length() in favour of ::numel().
Carnë Draug <carandraug@octave.org>
parents:
20172
diff
changeset
|
99 const octave_idx_type np = xi.numel (); |
10550 | 100 ColumnVector values (np); |
6823 | 101 |
18100
6a71e5030df5
Follow coding convention of defining and initializing only 1 variable per line in liboctinterp.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
102 double x0, y0, a11, a12, a21, a22, det; |
6a71e5030df5
Follow coding convention of defining and initializing only 1 variable per line in liboctinterp.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
103 x0 = y0 = 0.0; |
6a71e5030df5
Follow coding convention of defining and initializing only 1 variable per line in liboctinterp.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
104 a11 = a12 = a21 = a22 = 0.0; |
6a71e5030df5
Follow coding convention of defining and initializing only 1 variable per line in liboctinterp.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
105 det = 0.0; |
6823 | 106 |
107 octave_idx_type k = nelem; // k is a counter of elements | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
108 for (octave_idx_type kp = 0; kp < np; kp++) |
6823 | 109 { |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
110 const double xt = xi(kp); |
6823 | 111 const double yt = yi(kp); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
112 |
6823 | 113 // check if last triangle contains the next point |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
114 if (k < nelem) |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
115 { |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
116 const double dx1 = xt - x0; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
117 const double dx2 = yt - y0; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
118 const double c1 = (a22 * dx1 - a21 * dx2) / det; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
119 const double c2 = (-a12 * dx1 + a11 * dx2) / det; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
120 if (c1 >= -eps && c2 >= -eps && (c1 + c2) <= (1 + eps)) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
121 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
122 values(kp) = double(k+1); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
123 continue; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
124 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
125 } |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
126 |
6823 | 127 // it doesn't, so go through all elements |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
128 for (k = 0; k < nelem; k++) |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
129 { |
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
130 octave_quit (); |
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
131 |
10550 | 132 if (xt >= minx(k) && xt <= maxx(k) && yt >= miny(k) && yt <= maxy(k)) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
133 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
134 // element inside the minimum rectangle: examine it closely |
10550 | 135 x0 = REF (x, k, 0); |
136 y0 = REF (y, k, 0); | |
137 a11 = REF (x, k, 1) - x0; | |
138 a12 = REF (y, k, 1) - y0; | |
139 a21 = REF (x, k, 2) - x0; | |
140 a22 = REF (y, k, 2) - y0; | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
141 det = a11 * a22 - a21 * a12; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
142 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
143 // solve the system |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
144 const double dx1 = xt - x0; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
145 const double dx2 = yt - y0; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
146 const double c1 = (a22 * dx1 - a21 * dx2) / det; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
147 const double c2 = (-a12 * dx1 + a11 * dx2) / det; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
148 if ((c1 >= -eps) && (c2 >= -eps) && ((c1 + c2) <= (1 + eps))) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
149 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
150 values(kp) = double(k+1); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
151 break; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
152 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
153 } //endif # examine this element closely |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
154 } //endfor # each element |
6823 | 155 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
156 if (k == nelem) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
157 values(kp) = lo_ieee_nan_value (); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
158 |
6823 | 159 } //endfor # kp |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
160 |
20939
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
161 return ovl (values); |
6823 | 162 } |
163 | |
164 /* | |
165 %!shared x, y, tri | |
166 %! x = [-1;-1;1]; | |
167 %! y = [-1;1;-1]; | |
168 %! tri = [1, 2, 3]; | |
169 %!assert (tsearch (x,y,tri,-1,-1), 1) | |
170 %!assert (tsearch (x,y,tri, 1,-1), 1) | |
171 %!assert (tsearch (x,y,tri,-1, 1), 1) | |
172 %!assert (tsearch (x,y,tri,-1/3, -1/3), 1) | |
173 %!assert (tsearch (x,y,tri, 1, 1), NaN) | |
174 | |
14501
60e5cf354d80
Update %!tests in DLD-FUNCTIONS/ directory with Octave coding conventions.
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
175 %!error tsearch () |
6823 | 176 */ |