octave: libinterp/corefcn/tsearch.cc annotate

annotate libinterp/corefcn/tsearch.cc @ 31277:185799b2a566

tsearch.cc: Minor performance improvements tsearch.cc: replaced if-else with conditional operator in inline functions, replaced redeclarations of local variables with one set of declarations and initializations, added more comments. For searching 1e3 points through 1e6 triangles, these minor changes reduced 1.55-1.75 seconds to 1.35-1.45 seconds, so roughly 15% faster. Still O(M*N) for M points and N triangles, but acceptably fast for common use.

author	Arun Giridhar <arungiridhar@gmail.com>
date	Sat, 08 Oct 2022 13:14:02 -0400
parents	796f54d4ddbf
children	e88a07dec498

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: 29958 diff changeset	3 // Copyright (C) 2002-2022 The Octave Project Developers
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	4 //
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/>.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	7 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	8 // This file is part of Octave.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	9 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	10 // Octave is free software: you can redistribute it and/or modify it
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	11 // under the terms of the GNU General Public License as published by
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	12 // the Free Software Foundation, either version 3 of the License, or
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	13 // (at your option) any later version.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	14 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	15 // Octave is distributed in the hope that it will be useful, but
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	16 // WITHOUT ANY WARRANTY; without even the implied warranty of
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	18 // GNU General Public License for more details.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	19 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	20 // You should have received a copy of the GNU General Public License
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	21 // along with Octave; see the file COPYING. If not, see
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	22 // <https://www.gnu.org/licenses/>.
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
21724 aba2e6293dd8 use "#if ..." consistently instead of "#ifdef" and "#ifndef" John W. Eaton <jwe@octave.org> parents: 21301 diff changeset	26 #if defined (HAVE_CONFIG_H)
21301 40de9f8f23a6 Use '#include "config.h"' rather than <config.h>. Rik <rik@octave.org> parents: 21200 diff changeset	27 # include "config.h"
9786 2c279308f6ab fix includes in some src/DLD-FUNCTIONS files John W. Eaton <jwe@octave.org> parents: 9245 diff changeset	28 #endif
2c279308f6ab fix includes in some src/DLD-FUNCTIONS files John W. Eaton <jwe@octave.org> parents: 9245 diff changeset	29
23662 bd77ab816e43 eliminate obsolete file lo-math.h John W. Eaton <jwe@octave.org> parents: 23220 diff changeset	30 #include <cmath>
bd77ab816e43 eliminate obsolete file lo-math.h John W. Eaton <jwe@octave.org> parents: 23220 diff changeset	31
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	32 #include "lo-ieee.h"
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	33
19877 12ecb7212b44 move some files without external dependencies from dldfcn to corefcn John W. Eaton <jwe@octave.org> parents: 19697 diff changeset	34 #include "defun.h"
9786 2c279308f6ab fix includes in some src/DLD-FUNCTIONS files John W. Eaton <jwe@octave.org> parents: 9245 diff changeset	35 #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	36 #include "ovl.h"
9786 2c279308f6ab fix includes in some src/DLD-FUNCTIONS files John W. Eaton <jwe@octave.org> parents: 9245 diff changeset	37
29958 32c3a5805893 move DEFUN and DEFMETHOD functions inside octave namespace John W. Eaton <jwe@octave.org> parents: 29359 diff changeset	38 OCTAVE_NAMESPACE_BEGIN
32c3a5805893 move DEFUN and DEFMETHOD functions inside octave namespace John W. Eaton <jwe@octave.org> parents: 29359 diff changeset	39
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	40 inline double max (double a, double b, double c)
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	41 {
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	42 return (a > b) ? (a > c ? a : c) : (b > c ? b : c);
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	43 }
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	44
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	45 inline double min (double a, double b, double c)
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	46 {
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	47 return (a < b) ? (a < c ? a : c) : (b < c ? b : c);
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	48 }
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	49
25688 b2917b7858ba maint: Use Octave convention for spacing of C++ cast statements. Rik <rik@octave.org> parents: 25054 diff changeset	50 #define REF(x,k,i) x(static_cast<octave_idx_type> (elem((k), (i))) - 1)
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	51
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	52 // for large data set the algorithm is very slow
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	53 // 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	54 // 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	55 // given point
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	56
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	57 // e.g., build up a neighbouring triangle structure and use a simplex-like
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	58 // method to traverse it
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	59
19877 12ecb7212b44 move some files without external dependencies from dldfcn to corefcn John W. Eaton <jwe@octave.org> parents: 19697 diff changeset	60 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	61 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	62 @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	63 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	64
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21724 diff changeset	65 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	66 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	67 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	68 @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	69 @end deftypefn */)
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	70 {
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	71 if (args.length () != 5)
b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	72 print_usage ();
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	73
20799 c349d4c91ce2 eliminate return statements after calls to print_usage John W. Eaton <jwe@octave.org> parents: 20555 diff changeset	74 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	75
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	76 const ColumnVector x (args(0).vector_value ());
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	77 const ColumnVector y (args(1).vector_value ());
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	78 const Matrix elem (args(2).matrix_value ());
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	79 const ColumnVector xi (args(3).vector_value ());
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	80 const ColumnVector yi (args(4).vector_value ());
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	81
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	82 const octave_idx_type nelem = elem.rows ();
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	83
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	84 ColumnVector minx (nelem);
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	85 ColumnVector maxx (nelem);
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	86 ColumnVector miny (nelem);
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	87 ColumnVector maxy (nelem);
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	88 for (octave_idx_type k = 0; k < nelem; k++)
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	89 {
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	90 minx(k) = min (REF (x, k, 0), REF (x, k, 1), REF (x, k, 2)) - eps;
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	91 maxx(k) = max (REF (x, k, 0), REF (x, k, 1), REF (x, k, 2)) + eps;
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	92 miny(k) = min (REF (y, k, 0), REF (y, k, 1), REF (y, k, 2)) - eps;
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	93 maxy(k) = max (REF (y, k, 0), REF (y, k, 1), REF (y, k, 2)) + eps;
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	94 }
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	95
20232 a9574e3c6e9e Deprecate Array::length() and Sparse::length() in favour of ::numel(). Carnë Draug <carandraug@octave.org> parents: 20172 diff changeset	96 const octave_idx_type np = xi.numel ();
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	97 ColumnVector values (np);
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	98
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	99 double x0 = 0.0, y0 = 0.0;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	100 double a11 = 0.0, a12 = 0.0, a21 = 0.0, a22 = 0.0, det = 0.0;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	101 double xt = 0.0, yt = 0.0;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	102 double dx1 = 0.0, dx2 = 0.0, c1 = 0.0, c2 = 0.0;
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	103
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	104 octave_idx_type k = nelem; // k is more than just an index variable.
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	105
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	106 for (octave_idx_type kp = 0; kp < np; kp++) // for each point
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	107 {
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	108 xt = xi (kp);
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	109 yt = yi (kp);
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	110
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	111 // Check if point (xt,yt) is in the triangle that was last examined.
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	112 // This is for inputs where points are in contiguous order,
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	113 // like when the points are sampled from a continuous path.
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	114 if (k < nelem) // This check will be false for the very first point.
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	115 {
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	116 // If we are here, then x0, y0, det all exist from before.
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	117 dx1 = xt - x0;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	118 dx2 = yt - y0;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	119 c1 = (a22 * dx1 - a21 * dx2) / det;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	120 c2 = (-a12 * dx1 + a11 * dx2) / det;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	121 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	122 {
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	123 values (kp) = k+1;
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9786 diff changeset	124 continue;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9786 diff changeset	125 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9786 diff changeset	126 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	127
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	128 // The point is not in the same triangle, so go through all triangles.
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	129 for (k = 0; k < nelem; k++)
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	130 {
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	131 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	132 {
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	133 // Point is inside the triangle's bounding rectangle:
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	134 // See if it's inside the triangle itself.
10550 c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	135 x0 = REF (x, k, 0);
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	136 y0 = REF (y, k, 0);
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	137 a11 = REF (x, k, 1) - x0;
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	138 a12 = REF (y, k, 1) - y0;
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	139 a21 = REF (x, k, 2) - x0;
c48b7048e720 style fixes John W. Eaton <jwe@octave.org> parents: 10154 diff changeset	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
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	144 dx1 = xt - x0;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	145 dx2 = yt - y0;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	146 c1 = (a22 * dx1 - a21 * dx2) / det;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	147 c2 = (-a12 * dx1 + a11 * dx2) / det;
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 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 {
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	150 values (kp) = k+1;
10154 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 }
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	153 } //end see if it's inside the triangle itself
185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	154 } //end for each triangle
6823 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	155
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	156 if (k == nelem)
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 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
31277 185799b2a566 tsearch.cc: Minor performance improvements Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	159 } //end for each point
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 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	162 }
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	163
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	164 /*
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	165 %!shared x, y, tri
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	166 %! x = [-1;-1;1];
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	167 %! y = [-1;1;-1];
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	168 %! tri = [1, 2, 3];
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	169 %!assert (tsearch (x,y,tri,-1,-1), 1)
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	170 %!assert (tsearch (x,y,tri, 1,-1), 1)
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	171 %!assert (tsearch (x,y,tri,-1, 1), 1)
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	172 %!assert (tsearch (x,y,tri,-1/3, -1/3), 1)
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	173 %!assert (tsearch (x,y,tri, 1, 1), NaN)
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	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 9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman] dbateman parents: diff changeset	176 */
29958 32c3a5805893 move DEFUN and DEFMETHOD functions inside octave namespace John W. Eaton <jwe@octave.org> parents: 29359 diff changeset	177
32c3a5805893 move DEFUN and DEFMETHOD functions inside octave namespace John W. Eaton <jwe@octave.org> parents: 29359 diff changeset	178 OCTAVE_NAMESPACE_END

Mercurial > octave

annotate libinterp/corefcn/tsearch.cc @ 31277:185799b2a566