# HG changeset patch
# User Arun Giridhar <arungiridhar@gmail.com>
# Date 1715378249 14400
# Node ID 9f0f7a898b732d1dde7edda5b4f9c6affacb7e05
# Parent  36a19bb5cf61ac9cea7de2bc73886a8a02396ce9# Parent  69b9695538fb5daaa16b34b1f623e3d12fa5c13b
maint: Merge default to bytecode-interpreter

diff -r 36a19bb5cf61 -r 9f0f7a898b73 libinterp/corefcn/tsearch.cc
--- a/libinterp/corefcn/tsearch.cc	Fri May 10 17:05:58 2024 -0400
+++ b/libinterp/corefcn/tsearch.cc	Fri May 10 17:57:29 2024 -0400
@@ -51,13 +51,10 @@
 
 #define REF(x,k,i) x(static_cast<octave_idx_type> (elem((k), (i))) - 1)
 
-// for large data set the algorithm is very slow
-// one should presort (how?) either the elements of the points of evaluation
-// to cut down the time needed to decide which triangle contains the
-// given point
-
-// e.g., build up a neighbouring triangle structure and use a simplex-like
-// method to traverse it
+// The algorithm is O(M*N) for M points and N triangles.
+// Faster performance (closer to linear) happens if the points form a
+// contiguous path, such as a person on a walk recording their position every
+// few seconds and querying which map sector they are in.
 
 DEFUN (tsearch, args, ,
        doc: /* -*- texinfo -*-
@@ -67,6 +64,13 @@
 For @code{@var{t} = delaunay (@var{x}, @var{y})}, finds the index in @var{t}
 containing the points @code{(@var{xi}, @var{yi})}.  For points outside the
 convex hull, @var{idx} is NaN.
+
+Programming Note: The algorithm is @qcode{O}(@var{M}*@var{N}) for locating
+@var{M} points in @var{N} triangles.  Performance is typically much faster if
+the points to be located are in a single continuous path; a point is first
+checked against the region its predecessor was found in, speeding up lookups
+for points along a continuous path.
+
 @seealso{delaunay, delaunayn}
 @end deftypefn */)
 {