Mercurial > octave
annotate scripts/geometry/tsearchn.m @ 27919:1891570abac8
update Octave Project Developers copyright for the new year
In files that have the "Octave Project Developers" copyright notice,
update for 2020.
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Mon, 06 Jan 2020 22:29:51 -0500 |
parents | b442ec6dda5c |
children | bd51beb6205e |
rev | line source |
---|---|
27919
1891570abac8
update Octave Project Developers copyright for the new year
John W. Eaton <jwe@octave.org>
parents:
27918
diff
changeset
|
1 ## Copyright (C) 2007-2020 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
|
2 ## |
b442ec6dda5c
use centralized file for copyright info for individual contributors
John W. Eaton <jwe@octave.org>
parents:
26376
diff
changeset
|
3 ## See the file COPYRIGHT.md in the top-level directory of this distribution |
b442ec6dda5c
use centralized file for copyright info for individual contributors
John W. Eaton <jwe@octave.org>
parents:
26376
diff
changeset
|
4 ## or <https://octave.org/COPYRIGHT.html/>. |
b442ec6dda5c
use centralized file for copyright info for individual contributors
John W. Eaton <jwe@octave.org>
parents:
26376
diff
changeset
|
5 ## |
6823 | 6 ## |
7 ## This file is part of Octave. | |
8 ## | |
24534
194eb4bd202b
maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents:
23220
diff
changeset
|
9 ## Octave is free software: you can redistribute it and/or modify it |
6823 | 10 ## 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
|
11 ## 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
|
12 ## (at your option) any later version. |
6823 | 13 ## |
14 ## Octave is distributed in the hope that it will be useful, but | |
15 ## WITHOUT ANY WARRANTY; without even the implied warranty of | |
22755
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22323
diff
changeset
|
16 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22323
diff
changeset
|
17 ## GNU General Public License for more details. |
6823 | 18 ## |
19 ## You should have received a copy of the GNU General Public License | |
7016 | 20 ## 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
|
21 ## <https://www.gnu.org/licenses/>. |
6823 | 22 |
23 ## -*- texinfo -*- | |
20852
516bb87ea72e
2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents:
20158
diff
changeset
|
24 ## @deftypefn {} {@var{idx} =} tsearchn (@var{x}, @var{t}, @var{xi}) |
516bb87ea72e
2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents:
20158
diff
changeset
|
25 ## @deftypefnx {} {[@var{idx}, @var{p}] =} tsearchn (@var{x}, @var{t}, @var{xi}) |
20158
7503499a252b
doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
26 ## Search for the enclosing Delaunay convex hull. |
7503499a252b
doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
27 ## |
7503499a252b
doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
28 ## For @code{@var{t} = delaunayn (@var{x})}, finds the index in @var{t} |
7503499a252b
doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
29 ## containing the points @var{xi}. For points outside the convex hull, |
7503499a252b
doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
30 ## @var{idx} is NaN. |
7503499a252b
doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
31 ## |
21546
f7f97d7e9294
doc: Wrap m-file docstrings to 79 characters + newline (80 total).
Rik <rik@octave.org>
parents:
20852
diff
changeset
|
32 ## If requested @code{tsearchn} also returns the Barycentric coordinates |
f7f97d7e9294
doc: Wrap m-file docstrings to 79 characters + newline (80 total).
Rik <rik@octave.org>
parents:
20852
diff
changeset
|
33 ## @var{p} of the enclosing triangles. |
6823 | 34 ## @seealso{delaunay, delaunayn} |
35 ## @end deftypefn | |
36 | |
37 function [idx, p] = tsearchn (x, t, xi) | |
21758
ffad2baa90f7
maint: Use newlines to make code more readable.
Rik <rik@octave.org>
parents:
21751
diff
changeset
|
38 |
6823 | 39 if (nargin != 3) |
40 print_usage (); | |
41 endif | |
42 | |
14872
c2dbdeaa25df
maint: use rows() and columns() to clarify m-files.
Rik <octave@nomad.inbox5.com>
parents:
14868
diff
changeset
|
43 nt = rows (t); |
6823 | 44 [m, n] = size (x); |
14872
c2dbdeaa25df
maint: use rows() and columns() to clarify m-files.
Rik <octave@nomad.inbox5.com>
parents:
14868
diff
changeset
|
45 mi = rows (xi); |
10548
479536c5bb10
Replace lowercase nan with NaN for visual cue in scripts
Rik <code@nomad.inbox5.com>
parents:
9245
diff
changeset
|
46 idx = NaN (mi, 1); |
479536c5bb10
Replace lowercase nan with NaN for visual cue in scripts
Rik <code@nomad.inbox5.com>
parents:
9245
diff
changeset
|
47 p = NaN (mi, n + 1); |
6823 | 48 |
49 ni = [1:mi].'; | |
50 for i = 1 : nt | |
51 ## Only calculate the Barycentric coordinates for points that have not | |
52 ## already been found in a triangle. | |
53 b = cart2bary (x (t (i, :), :), xi(ni,:)); | |
54 | |
55 ## Our points xi are in the current triangle if | |
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21546
diff
changeset
|
56 ## (all (b >= 0) && all (b <= 1)). However as we impose that |
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21546
diff
changeset
|
57 ## sum (b,2) == 1 we only need to test all(b>=0). Note need to add |
6823 | 58 ## a small margin for rounding errors |
59 intri = all (b >= -1e-12, 2); | |
60 idx(ni(intri)) = i; | |
61 p(ni(intri),:) = b(intri, :); | |
62 ni(intri) = []; | |
63 endfor | |
21758
ffad2baa90f7
maint: Use newlines to make code more readable.
Rik <rik@octave.org>
parents:
21751
diff
changeset
|
64 |
6823 | 65 endfunction |
66 | |
67 function Beta = cart2bary (T, P) | |
68 ## Conversion of Cartesian to Barycentric coordinates. | |
24560
1c1adf6ab75d
doc: Fix issues in geometry, polynomial, and interpolation chapters (bug #52835).
Rik <rik@octave.org>
parents:
23219
diff
changeset
|
69 ## Given a reference simplex in N dimensions represented by an |
1c1adf6ab75d
doc: Fix issues in geometry, polynomial, and interpolation chapters (bug #52835).
Rik <rik@octave.org>
parents:
23219
diff
changeset
|
70 ## N+1-by-N matrix, an arbitrary point P in Cartesian coordinates, |
1c1adf6ab75d
doc: Fix issues in geometry, polynomial, and interpolation chapters (bug #52835).
Rik <rik@octave.org>
parents:
23219
diff
changeset
|
71 ## represented by an N-by-1 column vector can be written as |
6823 | 72 ## |
73 ## P = Beta * T | |
74 ## | |
24560
1c1adf6ab75d
doc: Fix issues in geometry, polynomial, and interpolation chapters (bug #52835).
Rik <rik@octave.org>
parents:
23219
diff
changeset
|
75 ## Where Beta is an N+1 vector of the barycentric coordinates. A criteria |
6823 | 76 ## on Beta is that |
77 ## | |
78 ## sum (Beta) == 1 | |
79 ## | |
80 ## and therefore we can write the above as | |
81 ## | |
14868
5d3a684236b0
maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents:
14363
diff
changeset
|
82 ## P - T(end, :) = Beta(1:end-1) * (T(1:end-1,:) - ones (N,1) * T(end,:)) |
6823 | 83 ## |
84 ## and then we can solve for Beta as | |
85 ## | |
14868
5d3a684236b0
maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents:
14363
diff
changeset
|
86 ## Beta(1:end-1) = (P - T(end,:)) / (T(1:end-1,:) - ones (N,1) * T(end,:)) |
5d3a684236b0
maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents:
14363
diff
changeset
|
87 ## Beta(end) = sum (Beta) |
6823 | 88 ## |
24560
1c1adf6ab75d
doc: Fix issues in geometry, polynomial, and interpolation chapters (bug #52835).
Rik <rik@octave.org>
parents:
23219
diff
changeset
|
89 ## Note code below is generalized for multiple values of P, one per row. |
6823 | 90 [M, N] = size (P); |
14868
5d3a684236b0
maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents:
14363
diff
changeset
|
91 Beta = (P - ones (M,1) * T(end,:)) / (T(1:end-1,:) - ones (N,1) * T(end,:)); |
5d3a684236b0
maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents:
14363
diff
changeset
|
92 Beta (:,end+1) = 1 - sum (Beta, 2); |
21758
ffad2baa90f7
maint: Use newlines to make code more readable.
Rik <rik@octave.org>
parents:
21751
diff
changeset
|
93 |
6823 | 94 endfunction |
95 | |
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
96 |
6823 | 97 %!shared x, tri |
98 %! x = [-1,-1;-1,1;1,-1]; | |
99 %! tri = [1, 2, 3]; | |
100 %!test | |
101 %! [idx, p] = tsearchn (x,tri,[-1,-1]); | |
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
102 %! assert (idx, 1); |
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
103 %! assert (p, [1,0,0], 1e-12); |
6823 | 104 %!test |
105 %! [idx, p] = tsearchn (x,tri,[-1,1]); | |
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
106 %! assert (idx, 1); |
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
107 %! assert (p, [0,1,0], 1e-12); |
6823 | 108 %!test |
109 %! [idx, p] = tsearchn (x,tri,[1,-1]); | |
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
110 %! assert (idx, 1); |
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
111 %! assert (p, [0,0,1], 1e-12); |
6823 | 112 %!test |
113 %! [idx, p] = tsearchn (x,tri,[-1/3,-1/3]); | |
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
114 %! assert (idx, 1); |
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
115 %! assert (p, [1/3,1/3,1/3], 1e-12); |
6823 | 116 %!test |
117 %! [idx, p] = tsearchn (x,tri,[1,1]); | |
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
118 %! assert (idx, NaN); |
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
119 %! assert (p, [NaN, NaN, NaN]); |