octave_packages/geometry-1.5.0/geom2d/isPointOnEdge.m

   1 %% Copyright (c) 2011, INRA
   2 %% 2003-2011, David Legland <david.legland@grignon.inra.fr>
   3 %% 2011 Adapted to Octave by Juan Pablo Carbajal <carbajal@ifi.uzh.ch>
   4 %%
   5 %% All rights reserved.
   6 %% (simplified BSD License)
   7 %%
   8 %% Redistribution and use in source and binary forms, with or without
   9 %% modification, are permitted provided that the following conditions are met:
  10 %%
  11 %% 1. Redistributions of source code must retain the above copyright notice, this
  12 %%    list of conditions and the following disclaimer.
  13 %%
  14 %% 2. Redistributions in binary form must reproduce the above copyright notice,
  15 %%    this list of conditions and the following disclaimer in the documentation
  16 %%    and/or other materials provided with the distribution.
  17 %%
  18 %% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  19 %% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20 %% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21 %% ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  22 %% LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23 %% CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24 %% SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25 %% INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26 %% CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27 %% ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28 %% POSSIBILITY OF SUCH DAMAGE.
  29 %%
  30 %% The views and conclusions contained in the software and documentation are
  31 %% those of the authors and should not be interpreted as representing official
  32 %% policies, either expressed or implied, of copyright holder.
  33
  34 %% -*- texinfo -*-
  35 %% @deftypefn {Function File} {@var{b} = } isPointOnEdge (@var{point}, @var{edge})
  36 %% @deftypefnx {Function File} {@var{b} = } isPointOnEdge (@var{point}, @var{edge}, @var{tol})
  37 %% @deftypefnx {Function File} {@var{b} = } isPointOnEdge (@var{point}, @var{edgearray})
  38 %% @deftypefnx {Function File} {@var{b} = } isPointOnEdge (@var{pointarray}, @var{edgearray})
  39 %% Test if a point belongs to an edge.
  40 %
  41 %   with @var{point} being [xp yp], and @var{edge} being [x1 y1 x2 y2], returns TRUE if
  42 %   the point is located on the edge, and FALSE otherwise.
  43 %
  44 %   Specify an optilonal tolerance value @var{tol}. The tolerance is given as a
  45 %   fraction of the norm of the edge direction vector. Default is 1e-14.
  46 %
  47 %   When one of the inputs has several rows, return the result of the test
  48 %   for each element of the array tested against the single parameter.
  49 %
  50 %   When both @var{pointarray} and @var{edgearray} have the same number of rows,
  51 %   returns a column vector with the same number of rows.
  52 %   When the number of rows are different and both greater than 1, returns
  53 %   a Np-by-Ne matrix of booleans, containing the result for each couple of
  54 %   point and edge.
  55 %
  56 %   @seealso{edges2d, points2d, isPointOnLine}
  57 %% @end deftypefn
  58
  59 function b = isPointOnEdge(point, edge, varargin)
  60
  61   % extract computation tolerance
  62   tol = 1e-14;
  63   if ~isempty(varargin)
  64       tol = varargin{1};
  65   end
  66
  67   % number of edges and of points
  68   Np = size(point, 1);
  69   Ne = size(edge, 1);
  70
  71   % adapt size of inputs if needed, and extract elements for computation
  72   if Np == Ne
  73       % When the number of points and edges is the same, the one-to-one test
  74       % will be computed, so there is no need to repeat matrices
  75       dx = edge(:,3) - edge(:,1);
  76       dy = edge(:,4) - edge(:,2);
  77       lx = point(:,1) - edge(:,1);
  78       ly = point(:,2) - edge(:,2);
  79
  80   elseif Np == 1
  81       % one point, several edges
  82       dx = edge(:, 3) - edge(:, 1);
  83       dy = edge(:, 4) - edge(:, 2);
  84       lx = point(ones(Ne, 1), 1) - edge(:, 1);
  85       ly = point(ones(Ne, 1), 2) - edge(:, 2);
  86
  87   elseif Ne == 1
  88       % several points, one edge
  89       dx = (edge(3) - edge(1)) * ones(Np, 1);
  90       dy = (edge(4) - edge(2)) * ones(Np, 1);
  91       lx = point(:, 1) - edge(1);
  92       ly = point(:, 2) - edge(2);
  93
  94   else
  95       % Np points and Ne edges:
  96       % Create an array for each parameter, so that the result will be a
  97       % Np-by-Ne matrix of booleans (requires more memory, and uses repmat)
  98
  99       x0 = repmat(edge(:, 1)', Np, 1);
 100       y0 = repmat(edge(:, 2)', Np, 1);
 101       dx = repmat(edge(:,3)', Np,  1) - x0;
 102       dy = repmat(edge(:,4)', Np,  1) - y0;
 103
 104       lx = repmat(point(:, 1), 1, Ne) - x0;
 105       ly = repmat(point(:, 2), 1, Ne) - y0;
 106   end
 107
 108   % test if point is located on supporting line
 109   b1 = (abs(lx.*dy - ly.*dx) ./ hypot(dx, dy)) < tol;
 110
 111   % compute position of point with respect to edge bounds
 112   % use different tests depending on line angle
 113   ind     = abs(dx) > abs(dy);
 114   t       = zeros(size(dx));
 115   t(ind)  = lx( ind) ./ dx( ind);
 116   t(~ind) = ly(~ind) ./ dy(~ind);
 117
 118   % check if point is located between edge bounds
 119   b = t >- tol & t-1 < tol & b1;
 120
 121 endfunction
 122
 123 %!shared points, vertices, edges
 124
 125 %!demo
 126 %!   % create a point array
 127 %!   points = [10 10;15 10; 30 10];
 128 %!   % create an edge array
 129 %!   vertices = [10 10;20 10;20 20;10 20];
 130 %!   edges = [vertices vertices([2:end 1], :)];
 131 %!
 132 %!   % Test one point and one edge
 133 %!   isPointOnEdge(points(1,:), edges(1,:))
 134 %!   isPointOnEdge(points(3,:), edges(1,:))
 135
 136 %!demo
 137 %!   % create a point array
 138 %!   points = [10 10;15 10; 30 10];
 139 %!   % create an edge array
 140 %!   vertices = [10 10;20 10;20 20;10 20];
 141 %!   edges = [vertices vertices([2:end 1], :)];
 142 %!
 143 %!   % Test one point and several edges
 144 %!   isPointOnEdge(points(1,:), edges)'
 145
 146 %!demo
 147 %!   % create a point array
 148 %!   points = [10 10;15 10; 30 10];
 149 %!   % create an edge array
 150 %!   vertices = [10 10;20 10;20 20;10 20];
 151 %!   edges = [vertices vertices([2:end 1], :)];
 152 %!
 153 %!   % Test several points and one edge
 154 %!   isPointOnEdge(points, edges(1,:))'
 155
 156 %!demo
 157 %!   % create a point array
 158 %!   points = [10 10;15 10; 30 10];
 159 %!   % create an edge array
 160 %!   vertices = [10 10;20 10;20 20;10 20];
 161 %!   edges = [vertices vertices([2:end 1], :)];
 162 %!
 163 %!   % Test N points and N edges
 164 %!   isPointOnEdge(points, edges(1:3,:))'
 165
 166 %!demo
 167 %!   % create a point array
 168 %!   points = [10 10;15 10; 30 10];
 169 %!   % create an edge array
 170 %!   vertices = [10 10;20 10;20 20;10 20];
 171 %!   edges = [vertices vertices([2:end 1], :)];
 172 %!
 173 %!   % Test NP points and NE edges
 174 %!   isPointOnEdge(points, edges)
 175
 176 %!test
 177 %!  p1 = [10 20];
 178 %!  p2 = [80 20];
 179 %!  edge = [p1 p2];
 180 %!  p0 = [10 20];
 181 %!  assert (isPointOnEdge(p0, edge));
 182 %!  p0 = [80 20];
 183 %!  assert (isPointOnEdge(p0, edge));
 184 %!  p0 = [50 20];
 185 %!  assert (isPointOnEdge(p0, edge));
 186 %!  p0 = [9.99 20];
 187 %!  assert (!isPointOnEdge(p0, edge));
 188 %!  p0 = [80.01 20];
 189 %!  assert (!isPointOnEdge(p0, edge));
 190 %!  p0 = [50 21];
 191 %!  assert (!isPointOnEdge(p0, edge));
 192 %!  p0 = [79 19];
 193 %!  assert (!isPointOnEdge(p0, edge));
 194
 195 %!test
 196 %!  p1 = [20 10];
 197 %!  p2 = [20 80];
 198 %!  edge = [p1 p2];
 199 %!  p0 = [20 10];
 200 %!  assert (isPointOnEdge(p0, edge));
 201 %!  p0 = [20 80];
 202 %!  assert (isPointOnEdge(p0, edge));
 203 %!  p0 = [20 50];
 204 %!  assert (isPointOnEdge(p0, edge));
 205 %!  p0 = [20 9.99];
 206 %!  assert (!isPointOnEdge(p0, edge));
 207 %!  p0 = [20 80.01];
 208 %!  assert (!isPointOnEdge(p0, edge));
 209 %!  p0 = [21 50];
 210 %!  assert (!isPointOnEdge(p0, edge));
 211 %!  p0 = [19 79];
 212 %!  assert (!isPointOnEdge(p0, edge));
 213
 214 %!test
 215 %!  p1 = [10 20];
 216 %!  p2 = [60 70];
 217 %!  edge = [p1 p2];
 218 %!  assert (isPointOnEdge(p1, edge));
 219 %!  assert (isPointOnEdge(p2, edge));
 220 %!  p0 = [11 21];
 221 %!  assert (isPointOnEdge(p0, edge));
 222 %!  p0 = [59 69];
 223 %!  assert (isPointOnEdge(p0, edge));
 224 %!  p0 = [9.99 19.99];
 225 %!  assert (!isPointOnEdge(p0, edge));
 226 %!  p0 = [60.01 70.01];
 227 %!  assert (!isPointOnEdge(p0, edge));
 228 %!  p0 = [30 50.01];
 229 %!  assert (!isPointOnEdge(p0, edge));
 230
 231 %!test
 232 %!  edge = [10 20 80 20; 20 10 20 80; 20 10 60 70];
 233 %!  p0 = [20 20];
 234 %!  assert ([true ; true ; false], isPointOnEdge(p0, edge));
 235
 236 %!test
 237 %!  k = 1e15;
 238 %!  p1 = [10 20]*k;
 239 %!  p2 = [60 70]*k;
 240 %!  edge = [p1 p2];
 241 %!  assert (isPointOnEdge(p1, edge));
 242 %!  assert (isPointOnEdge(p2, edge));
 243 %!  p0 = [11 21]*k;
 244 %!  assert (isPointOnEdge(p0, edge));
 245 %!  p0 = [59 69]*k;
 246 %!  assert (isPointOnEdge(p0, edge));
 247 %!  p0 = [9.99 19.99]*k;
 248 %!  assert (!isPointOnEdge(p0, edge));
 249 %!  p0 = [60.01 70.01]*k;
 250 %!  assert (!isPointOnEdge(p0, edge));
 251 %!  p0 = [30 50.01]*k;
 252 %!  assert (!isPointOnEdge(p0, edge));
 253
 254 %!test
 255 %!  k = 1e-10;
 256 %!  p1 = [10 20]*k;
 257 %!  p2 = [60 70]*k;
 258 %!  edge = [p1 p2];
 259 %!  assert (isPointOnEdge(p1, edge));
 260 %!  assert (isPointOnEdge(p2, edge));
 261 %!  p0 = [11 21]*k;
 262 %!  assert (isPointOnEdge(p0, edge));
 263 %!  p0 = [59 69]*k;
 264 %!  assert (isPointOnEdge(p0, edge));
 265 %!  p0 = [9.99 19.99]*k;
 266 %!  assert (!isPointOnEdge(p0, edge));
 267 %!  p0 = [60.01 70.01]*k;
 268 %!  assert (!isPointOnEdge(p0, edge));
 269 %!  p0 = [30 50.01]*k;
 270 %!  assert (!isPointOnEdge(p0, edge));
 271
 272 %!test
 273 %!  p1 = [10 20];
 274 %!  p2 = [80 20];
 275 %!  edge = [p1 p2];
 276 %!  p0 = [10 20; 80 20; 50 20;50 21];
 277 %!  exp = [true;true;true;false];
 278 %!  assert (exp, isPointOnEdge(p0, edge));
 279
 280 %!test
 281 %!  p1 = [10 20];
 282 %!  p2 = [80 20];
 283 %!  edge = [p1 p2];
 284 %!  p0 = [40 20];
 285 %!  exp = [true;true;true;true];
 286 %!  assert (exp, isPointOnEdge(p0, [edge;edge;edge;edge]));
 287
 288 %!test
 289 %!  edge1 = [10 20 80 20];
 290 %!  edge2 = [30 10 30 80];
 291 %!  edges = [edge1; edge2];
 292 %!  p0 = [40 20;30 90];
 293 %!  exp = [true;false];
 294 %!  assert (exp, isPointOnEdge(p0, edges));