function [t,d] = dsearchn(x,tri,xi,outval,coptions,doptions)
%DSEARCHN N-D nearest point search.
%   K = DSEARCHN(X,T,XI) returns the indices K of the closest points in X for
%   each point in XI. X is an m-by-n matrix representing m points in n-D
%   space. XI is a p-by-n matrix, representing p points in n-D space. T is a
%   numt-by-n+1 matrix, a triangulation of the data X generated by DELAUNAYN.
%   The output K is a column vector of length p. 
%
%   K = DSEARCHN(X,T,XI,OUTVAL) returns the indices K of the closest points
%   in X for each point in XI, unless a point is outside the convex hull. 
%   If XI(J,:) is outside the convex hull, then K(J) is assigned OUTVAL, 
%   a scalar double. Inf is often used for OUTVAL. If OUTVAL is [], then
%   K is the same as in the case K = DSEARCHN(X,T,XI).
%
%   K = DSEARCHN(X,T,XI,OUTVAL,COPTIONS) specifies COPTIONS, a cell array of
%   strings to be used as options in Qhull via CONVHULLN.
%   If COPTIONS is [], the default CONVHULLN options will be used.
%   If COPTIONS is {''}, no options will be used, not even the default.
% 
%   K = DSEARCHN(X,T,XI,OUTVAL,COPTIONS,DOPTIONS) specifies DOPTIONS, a
%   cell array of strings to be used as options in Qhull via DELAUNAYN.
%   If DOPTIONS is [], the default DELAUNAYN options will be used.
%   If DOPTIONS is {''}, no options will be used, not even the default.
%  
%   K = DSEARCHN(X,XI) performs the search without using a triangulation.
%   With large X and small XI, this approach is faster and uses much
%   less memory. 
%
%   [K,D] = DSEARCHN(X,...) also returns the distances D to the closest
%   points. D is a column vector of length p. 
%
%   See also delaunayTriangulation, TSEARCHN, QHULL, GRIDDATAN, DELAUNAYN,
%            CONVHULLN.

%   Copyright 1984-2022 The MathWorks, Inc.

if nargin < 2
  error(message('MATLAB:dsearchn:NotEnoughInputs')); 
end
if nargin >= 4
    if ~isempty(outval) && ~isa(outval,'double')
        error(message('MATLAB:dsearchn:OutvalNotScalarDouble'));
    end
    %coptions, doptions are not used, to be removed completely after 18a
    if nargin > 4
        if ~isstring(coptions) && ~iscellstr(coptions)
            error(message('MATLAB:dsearchn:CoptionsNotStringCell'));           
        end
        if nargin > 5 
            if ~isstring(doptions) && ~iscellstr(doptions)
                error(message('MATLAB:dsearchn:DoptionsNotStringCell'));           
            end
        end
    end
end

if nargin == 2 % (x,xi) syntax
    if size(x,2) ~= size(tri,2)
        error(message('MATLAB:dsearchn:XandXIColSizeMismatch'));
    end
end

if nargin >= 3
    if size(x,2) ~= size(xi,2)
        error(message('MATLAB:dsearchn:XandXIColSizeMismatch'));
    end
    if size(x,2) ~= size(tri,2)-1
        error(message('MATLAB:dsearchn:InvalidSizeT'));
    end
end

if nargin == 2 % loop, no triangles, tri is xi in this syntax
    xi = tri;
    t = zeros(size(xi,1),1);
    d = zeros(size(xi,1),1);
    for i = 1:size(xi,1) 
        yi = repmat(xi(i,:),size(x,1),1);
        [d(i),t(i)] = min(sum((x-yi).^2,2));
    end
    if nargout == 2
        d = sqrt(d); 
    end
    return;
end

tsrch_method = 1;
if nargin >= 4 && ~isempty(outval)
    tsrch_method = 3;
end

[t,d] = matlab.internal.math.tsearchn(x',tri,xi',tsrch_method);
if nargout == 2
    d = sqrt(d); 
end
    
% give outval to points outside of the convex hull
if nargin >= 4 && ~isempty(outval)
    outlier_idx = isnan(t);
    t(outlier_idx) = outval;
end
