octave_packages/geometry-1.5.0/geom2d/clipLine.m

   1 %% Copyright (c) 2011, INRA
   2 %% 2007-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{edge} =} clipLine (@var{line}, @var{box})
  36 %% Clip a line with a box.
  37 %%
  38 %%   @var{line} is a straight line given as a 4 element row vector: [x0 y0 dx dy],
  39 %%   with (x0 y0) being a point of the line and (dx dy) a direction vector,
  40 %%   @var{box} is the clipping box, given by its extreme coordinates:
  41 %%   [xmin xmax ymin ymax].
  42 %%   The result is given as an edge, defined by the coordinates of its 2
  43 %%   extreme points: [x1 y1 x2 y2].
  44 %%   If line does not intersect the box, [NaN NaN NaN NaN] is returned.
  45 %%
  46 %%   Function works also if @var{line} is a Nx4 array, if @var{box} is a Nx4 array, or
  47 %%   if both @var{line} and @var{box} are Nx4 arrays. In these cases, @var{edge} is a Nx4
  48 %%   array.
  49 %%
  50 %%   Example:
  51 %%
  52 %% @example
  53 %%   line = [30 40 10 0];
  54 %%   box = [0 100 0 100];
  55 %%   res = clipLine(line, box)
  56 %%   res =
  57 %%       0 40 100 40
  58 %% @end example
  59 %%
  60 %% @seealso{lines2d, boxes2d, edges2d, clipEdge, clipRay}
  61 %% @end deftypefn
  62
  63 function edge = clipLine(lin, bb, varargin)
  64
  65   % adjust size of two input arguments
  66   if size(lin, 1)==1
  67       lin = repmat(lin, size(bb, 1), 1);
  68   elseif size(bb, 1)==1
  69       bb = repmat(bb, size(lin, 1), 1);
  70   elseif size(lin, 1) ~= size(bb, 1)
  71       error('bad sizes for input');
  72   end
  73
  74   % allocate memory
  75   nbLines = size(lin, 1);
  76   edge    = zeros(nbLines, 4);
  77
  78   % main loop on lines
  79   for i=1:nbLines
  80       % extract limits of the box
  81       xmin = bb(i, 1);
  82       xmax = bb(i, 2);
  83       ymin = bb(i, 3);
  84       ymax = bb(i, 4);
  85
  86       % use direction vector for box edges similar to direction vector of the
  87       % line in order to reduce computation errors
  88       delta = hypot(lin(i,3), lin(i,4));
  89
  90
  91           % compute intersection with each edge of the box
  92
  93       % lower edge
  94           px1 = intersectLines(lin(i,:), [xmin ymin delta 0]);
  95       % right edge
  96           px2 = intersectLines(lin(i,:), [xmax ymin 0 delta]);
  97       % upper edge
  98           py1 = intersectLines(lin(i,:), [xmax ymax -delta 0]);
  99       % left edge
 100           py2 = intersectLines(lin(i,:), [xmin ymax 0 -delta]);
 101
 102       % remove undefined intersections (case of lines parallel to box edges)
 103       points = [px1 ; px2 ; py1 ; py2];
 104       points = points(isfinite(points(:,1)), :);
 105
 106       % sort points according to their position on the line
 107       pos = linePosition(points, lin(i,:));
 108       [pos inds] = sort(pos); %#ok<ASGLU>
 109       points = points(inds, :);
 110
 111       % create clipped edge by using the two points in the middle
 112       ind = size(points, 1)/2;
 113       inter1 = points(ind,:);
 114       inter2 = points(ind+1,:);
 115       edge(i, 1:4) = [inter1 inter2];
 116
 117       % check that middle point of the edge is contained in the box
 118       midX = mean(edge(i, [1 3]));
 119       xOk = xmin <= midX && midX <= xmax;
 120       midY = mean(edge(i, [2 4]));
 121       yOk = ymin <= midY && midY <= ymax;
 122
 123       % if one of the bounding condition is not met, set edge to NaN
 124       if ~(xOk && yOk)
 125           edge (i,:) = NaN;
 126       end
 127   end
 128 endfunction
 129
 130 %!demo
 131 %!   lin = [30 40 10 0];
 132 %!   bb = [0 100 0 100];
 133 %!   res = clipLine(lin, bb)
 134 %!
 135 %! drawBox(bb,'color','k');
 136 %! line(lin([1 3]),lin([2 4]),'color','b');
 137 %! line(res([1 3]),res([2 4]),'color','r','linewidth',2);
 138 %! axis tight
 139 %! v = axis ();
 140 %! axis(v+[0 10 -10 0])
 141
 142 %!test % inside, to the right % inside, to the left% outside
 143 %! bb = [0 100 0 100];
 144 %! lin = [30 40 10 0];
 145 %! edge = [0 40 100 40];
 146 %! assert (edge, clipLine(lin, bb), 1e-6);
 147 %! lin = [30 40 -10 0];
 148 %! edge = [100 40 0 40];
 149 %! assert (edge, clipLine(lin, bb), 1e-6);
 150 %! lin = [30 140 10 0];
 151 %! assert (sum(isnan(clipLine(lin, bb)))==4);
 152
 153 %!test % inside, upward % inside, downward % outside
 154 %!  bb = [0 100 0 100];
 155 %!  lin = [30 40 0 10];
 156 %!  edge = [30 0 30 100];
 157 %!  assert (edge, clipLine(lin, bb), 1e-6);
 158 %!  lin = [30 40 0 -10];
 159 %!  edge = [30 100 30 0];
 160 %!  assert (edge, clipLine(lin, bb), 1e-6);
 161 %!  lin = [140 30 0 10];
 162 %!  assert (sum(isnan(clipLine(lin, bb)))==4);
 163
 164 %!test % inside, top right corner% inside, down right corner % outside
 165 %!  bb = [0 100 0 100];
 166 %!  lin = [80 30 10 10];
 167 %!  edge = [50 0 100 50];
 168 %!  assert (edge, clipLine(lin, bb), 1e-6);
 169 %!  lin = [20 70 10 10];
 170 %!  edge = [0 50 50 100];
 171 %!  assert (edge, clipLine(lin, bb), 1e-6);
 172 %!  lin = [140 -30 10 10];
 173 %!  assert (sum(isnan(clipLine(lin, bb)))==4);
 174 %!  lin = [-40 130 10 10];
 175 %!  assert (sum(isnan(clipLine(lin, bb)))==4);
 176
 177 %!test %multilines % inside, top right corner
 178 %!  bb = [0 100 0 100];
 179 %!  lin = [...
 180 %!      80 30 10 10; ...
 181 %!      20 70 10 10; ...
 182 %!      140 -30 10 10; ...
 183 %!      -40 130 10 10];
 184 %!  edge = [...
 185 %!      50 0 100 50; ...
 186 %!      0 50 50 100; ...
 187 %!      NaN NaN NaN NaN; ...
 188 %!      NaN NaN NaN NaN; ...
 189 %!      ];
 190 %!  clipped = clipLine(lin, bb);
 191 %!  assert (4, size(clipped, 1));
 192 %!  assert (edge(1:2, :), clipped(1:2, :), 1e-6);
 193 %!  assert (sum(isnan(clipped(3,:)))==4);
 194 %!  assert (sum(isnan(clipped(4,:)))==4);
 195
 196 %!test % test clipping of horizontal lines % inside, to the right
 197 %!  bb = [-1 1 -1 1]*1e10;
 198 %!  lin = [3 0 1 2];
 199 %!  D = 1e10;
 200 %!  edge = [3-D/2 -D 3+D/2 D];
 201 %!  clipped = clipLine(lin, bb);
 202 %!  assert (edge, clipped);
 203
 204 %!test % inside, to the right
 205 %!  bb = [-1 1 -1 1]*100;
 206 %!  lin = [3 0 1*1e10 2*1e10];
 207 %!  D = 100;
 208 %!  edge = [3-D/2 -D 3+D/2 D];
 209 %!  clipped = clipLine(lin, bb);
 210 %!  assert (edge, clipped, 1e-6);