tsearch_arbitrary.m

function [tn,a12,a13] = tsearch_arbitrary( p, t, x, y )
% TSEARCH_ARBITRARY - finds enclosing triangles and barycentric
% coordinates for an arbitrary grid.
%
% Usage: [tn,a12,a13] = tri2pts( p, t, x, y )
%
% p and t should define a triangular grid as generated by initmesh, pdetool,
% etc. (i.e. many columns, few rows).
%
% x and y are the points at which the triangles should be found.
%
% tn are the indices of the enclosing triangles.
%
% a12 and 13 are the second and third barycentric coordinates.  The first
% can be found as 1 - a12 - a13.  These are useful for interpolation.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 	$Id: tsearch_arbitrary.m 70 2007-02-22 02:24:34Z dmk $	
%
% Copyright (C) 2005 David M. Kaplan
% Licence: GPL (Gnu Public License)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Make p and t correct shape.
p = p';
t = t(1:3,:)';

s = size(x);
x = x(:);
y = y(:);

[tn,a12,a13] = deal( repmat( NaN, size(x) ) );

nt = size(t,1);
nx = length(x);
  
% Calculate as much as possible up front.
p1 = p( t(:,1), : );
v12 = p( t(:,2), : ) - p1;
v13 = p( t(:,3), : ) - p1;
dd = v12(:,1).*v13(:,2) - v12(:,2).*v13(:,1);

% Pick which is easier: points in triangles or triangles around points.
if nx < 0.05 * nt % Experience shows this is only better for just a few pts
  for k = 1:nx % Loop over points
    xx = x(k) - p1(:,1);
    yy = y(k) - p1(:,2);
    
    aa2 = ( v13(:,2).*xx - v13(:,1).*yy ) ./ dd;
    aa3 = ( v12(:,1).*yy - v12(:,2).*xx ) ./ dd;
    
    tt = find( aa2 >= 0 & aa3 >= 0 & (1-aa2-aa3) >= 0 );
    if ~isempty(tt)
      tn(k) = tt(1);
      [a12(k),a13(k)] = deal( aa2(tt(1)), aa3(tt(1)) );
    end
  end
else
  ii = 1:nx;
  for k = 1:nt % Loop over triangles.
    if isempty(ii), break, end
    xx = x - p1(k,1);
    yy = y - p1(k,2);
    aa2 = ( v13(k,2).*xx - v13(k,1).*yy ) ./ dd(k);
    aa3 = ( v12(k,1).*yy - v12(k,2).*xx ) ./ dd(k);
    
    tt = find( aa2 >= 0 & aa3 >= 0 & (1-aa2-aa3) >= 0 );      
    if ~isempty(tt)
      tn(ii(tt)) = k;
      [a12(ii(tt)),a13(ii(tt))] = deal( aa2(tt), aa3(tt) );
      
      ii(tt) = [];
      x(tt) = [];
      y(tt) = [];
    end
  end
end

tn = reshape(tn,s);
a12 = reshape(a12,s);
a13 = reshape(a13,s);