bugGNU Octave - Bugs: bug #66776, dsearchn ignores tri input

 
 

bug #66776: dsearchn ignores tri input

Submitter:  Nicholas Jankowski <nrjank>
Submitted:  Mon 10 Feb 2025 11:06:24 PM UTC
   
 
Category:  Octave Function Severity:  1 - Wish
Priority:  5 - Normal Item Group:  Feature Request
Status:  Confirmed Assigned to:  None
Originator Name:  Nicholas Jankowski Open/Closed:  * Open
Release:  * dev Release: 
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Wed 12 Mar 2025 02:24:18 AM UTC, comment #2: 

well,  that's... not what I expected.

I mean, it is a really simple algorithm. find all distances between points, retain the smallest. I would imagine at some level that would start to scale badly. But i can see why it doesn't care about a precomputed triangulation.

Nicholas Jankowski <nrjank>
Group Member
Tue 11 Feb 2025 12:26:19 AM UTC, comment #1: 

I just took a look at _dsearchn_.cc and, to my great surprise, it has nothing to do with the Delaunay triangulation.  It is calculating the distances from scratch.  I quote the entire code here because it is fairly short.


DEFUN (__dsearchn__, args, ,
       doc: /* -*- texinfo -*-
@deftypefn {} {[@var{idx}, @var{d}] =} dsearch (@var{x}, @var{xi})
Undocumented internal function.
@end deftypefn */)
{
  if (args.length () != 2)
    print_usage ();

  Matrix x = args(0).matrix_value ().transpose ();
  Matrix xi = args(1).matrix_value ().transpose ();

  if (x.rows () != xi.rows () || x.columns () < 1)
    error ("__dsearchn__: number of rows of X and XI must match");

  octave_idx_type n = x.rows ();
  octave_idx_type nx = x.columns ();
  octave_idx_type nxi = xi.columns ();

  ColumnVector idx (nxi);
  double *pidx = idx.rwdata ();
  ColumnVector dist (nxi);
  double *pdist = dist.rwdata ();

#define DIST(dd, y, yi, m)                      \
  dd = 0.0;                                     \
  for (octave_idx_type k = 0; k < m; k++)       \
    {                                           \
      double yd = y[k] - yi[k];                 \
      dd += yd * yd;                            \
    }                                           \
  dd = sqrt (dd)

  const double *pxi = xi.data ();
  for (octave_idx_type i = 0; i < nxi; i++)
    {
      double d0;
      const double *px = x.data ();
      DIST(d0, px, pxi, n);
      *pidx = 1.;
      for (octave_idx_type j = 1; j < nx; j++)
        {
          px += n;
          double d;
          DIST (d, px, pxi, n);
          if (d < d0)
            {
              d0 = d;
              *pidx = static_cast<double> (j + 1);
            }
          octave_quit ();
        }

      *pdist++ = d0;
      pidx++;
      pxi += n;
    }

  return ovl (idx, dist);
}


WTF?

Rik <rik5>
Group administrator
Mon 10 Feb 2025 11:06:24 PM UTC, original submission:  

this report is a wishlist/feature request to implement tri reuse in the compiled `__dsearchn__`.

as mentioned in bug #66760, dsearch requires and dsearchn optionally accepts an input `tri` that consists of a delaunay triangulation matrix corresponding to the input points x.  the underlying `__dsearchn__` function uses delaunay triangulation to find the nearest point x to a test point xi, but it does not accept a precalculated triangulation and so recomputes the matrix whether or not one has been provided.  dsearch and dsearchn just discard any input tri for the actual call to `__dsearchn__`. for large meshes, this calculation can be expensive, and providing the tri input to shortcut recalculation could be an immense efficiency improvement for large models. 

it may be worth noting that the tsearch.cc also accepts an input delaunay triangulation, so dsearch may be able to borrow some things from it (perhaps at least input validation).

Nicholas Jankowski <nrjank>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by nrjank (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2025-02-11 rik5 Summarydsearchn ignores tri input for dsearchn ignores tri input

    Back to the top

    Powered by Savane 3.14-7003.
    Corresponding source code