octave_packages/geometry-1.5.0/geom2d/clipEdge.m

   1 %% Copyright (c) 2011, INRA
   2 %% 2010-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{edge2} =} clipEdge (@var{edge}, @var{box})
  36 %% Clip an edge with a rectangular box.
  37 %%
  38 %%   @var{edge}: [x1 y1 x2 y2],
  39 %%   @var{box} : [xmin xmax ; ymin ymax] or [xmin xmax ymin ymax];
  40 %%   return :
  41 %%   @var{edge2} = [xc1 yc1 xc2 yc2];
  42 %%
  43 %%   If clipping is null, return [0 0 0 0];
  44 %%
  45 %%   if @var{edge} is a [nx4] array, return an [nx4] array, corresponding to each
  46 %%   clipped edge.
  47 %%
  48 %% @seealso{edges2d, boxes2d, clipLine}
  49 %% @end deftypefn
  50
  51 function edge2 = clipEdge(edge, bb)
  52
  53   % process data input
  54   if size(bb, 1)==2
  55       bb = bb';
  56   end
  57
  58   % get limits of window
  59   xmin = bb(1);
  60   xmax = bb(2);
  61   ymin = bb(3);
  62   ymax = bb(4);
  63
  64
  65   % convert window limits into lines
  66   lineX0 = [xmin ymin xmax-xmin 0];
  67   lineX1 = [xmin ymax xmax-xmin 0];
  68   lineY0 = [xmin ymin 0 ymax-ymin];
  69   lineY1 = [xmax ymin 0 ymax-ymin];
  70
  71
  72   % compute outcodes of each vertex
  73   p11 = edge(:,1)<xmin; p21 = edge(:,3)<xmin;
  74   p12 = edge(:,1)>xmax; p22 = edge(:,3)>xmax;
  75   p13 = edge(:,2)<ymin; p23 = edge(:,4)<ymin;
  76   p14 = edge(:,2)>ymax; p24 = edge(:,4)>ymax;
  77   out1 = [p11 p12 p13 p14];
  78   out2 = [p21 p22 p23 p24];
  79
  80   % detect edges totally inside window -> no clip.
  81   inside = sum(out1 | out2, 2)==0;
  82
  83   % detect edges totally outside window
  84   outside = sum(out1 & out2, 2)>0;
  85
  86   % select edges not totally outside, and process separately edges totally
  87   % inside window
  88   ind = find(~(inside | outside));
  89
  90
  91   edge2 = zeros(size(edge));
  92   edge2(inside, :) = edge(inside, :);
  93
  94
  95   for i=1:length(ind)
  96       % current edge
  97       iedge = edge(ind(i), :);
  98
  99       % compute intersection points with each line of bounding window
 100       px0 = intersectLineEdge(lineX0, iedge);
 101       px1 = intersectLineEdge(lineX1, iedge);
 102       py0 = intersectLineEdge(lineY0, iedge);
 103       py1 = intersectLineEdge(lineY1, iedge);
 104
 105       % create array of points
 106       points  = [px0; px1; py0; py1; iedge(1:2); iedge(3:4)];
 107
 108       % remove infinite points (edges parallel to box edges)
 109           points  = points(all(isfinite(points), 2), :);
 110
 111       % sort points by x then y
 112       points = sortrows(points);
 113
 114       % get center positions between consecutive points
 115       centers = (points(2:end,:) + points(1:end-1,:))/2;
 116
 117       % find the centers (if any) inside window
 118       inside = find(  centers(:,1)>=xmin & centers(:,2)>=ymin & ...
 119                       centers(:,1)<=xmax & centers(:,2)<=ymax);
 120
 121       % if multiple segments are inside box, which can happen due to finite
 122       % resolution, only take the longest segment
 123       if length(inside)>1
 124           % compute delta vectors of the segments
 125           dv = points(inside+1,:) - points(inside,:);
 126           % compute lengths of segments
 127           len = hypot(dv(:,1), dv(:,2));
 128           % find index of longest segment
 129           [a, I] = max(len); %#ok<ASGLU>
 130           inside = inside(I);
 131       end
 132
 133       % if one of the center points is inside box, then the according edge
 134       % segment is indide box
 135       if length(inside)==1
 136            % restore same direction of edge
 137           if iedge(1)>iedge(3) || (iedge(1)==iedge(3) && iedge(2)>iedge(4))
 138               edge2(i, :) = [points(inside+1,:) points(inside,:)];
 139           else
 140               edge2(i, :) = [points(inside,:) points(inside+1,:)];
 141           end
 142       end
 143
 144   end % end of loop of edges
 145 endfunction
 146
 147 %!demo
 148 %! bb = [0 100 0 100];
 149 %! edge = [-10 10 90 110];
 150 %! ec = clipEdge (edge, bb);
 151 %!
 152 %! drawBox(bb,'color','k');
 153 %! line(edge([1 3]),edge([2 4]),'color','b');
 154 %! line(ec([1 3]),ec([2 4]),'color','r','linewidth',2);
 155 %! axis tight
 156 %! v = axis ();
 157 %! axis(v+[0 10 -10 0])
 158
 159 %!shared bb
 160 %! bb = [0 100 0 100];
 161 %!assert (clipEdge([20 30 80 60], bb), [20 30 80 60],1e-6);
 162 %!assert (clipEdge([0  30 80 60], bb), [0  30 80 60],1e-6);
 163 %!assert (clipEdge([0  30 100 60], bb), [0  30 100 60],1e-6);
 164 %!assert (clipEdge([30 0 80 100], bb), [30 0 80 100],1e-6);
 165 %!assert (clipEdge([0 0 100 100], bb), [0 0 100 100],1e-6);
 166 %!assert (clipEdge([0 100 100 0], bb), [0 100 100 0],1e-6);
 167 %!assert (clipEdge([20 60 120 60], bb), [20 60 100 60],1e-6);
 168 %!assert (clipEdge([-20 60 80 60], bb), [0  60 80 60],1e-6);
 169 %!assert (clipEdge([20 60 20 160], bb), [20 60 20 100],1e-6);
 170 %!assert (clipEdge([20 -30 20 60], bb), [20 0 20 60],1e-6);
 171 %!assert (clipEdge([120 30 180 60], bb), [0 0 0 0],1e-6);
 172 %!assert (clipEdge([-20 30 -80 60], bb), [0 0 0 0],1e-6);
 173 %!assert (clipEdge([30 120 60 180], bb), [0 0 0 0],1e-6);
 174 %!assert (clipEdge([30 -20 60 -80], bb), [0 0 0 0],1e-6);
 175 %!assert (clipEdge([-120 110 190 150], bb), [0 0 0 0],1e-6);
 176 %!assert ([50 50 100 50], clipEdge([50 50 150 50], bb),1e-6);
 177 %!assert ([50 50 0 50], clipEdge([50 50 -50 50], bb),1e-6);
 178 %!assert ([50 50 50 100], clipEdge([50 50 50 150], bb),1e-6);
 179 %!assert ([50 50 50 0], clipEdge([50 50 50 -50], bb),1e-6);
 180 %!assert ([80 50 100 70], clipEdge([80 50 130 100], bb),1e-6);
 181 %!assert ([80 50 100 30], clipEdge([80 50 130 0], bb),1e-6);
 182 %!assert ([20 50 0 70], clipEdge([20 50 -30 100], bb),1e-6);
 183 %!assert ([20 50 0 30], clipEdge([20 50 -30 0], bb),1e-6);
 184 %!assert ([50 80 70 100], clipEdge([50 80 100 130], bb),1e-6);
 185 %!assert ([50 80 30 100], clipEdge([50 80 0 130], bb),1e-6);
 186 %!assert ([50 20 70 0], clipEdge([50 20 100 -30], bb),1e-6);
 187 %!assert ([50 20 30 0], clipEdge([50 20 0 -30], bb),1e-6);
 188 %!assert ([100 50 50 50], clipEdge([150 50 50 50], bb),1e-6);
 189 %!assert ([0 50 50 50], clipEdge([-50 50 50 50], bb),1e-6);
 190 %!assert ([50 100 50 50], clipEdge([50 150 50 50], bb),1e-6);
 191 %!assert ([50 0 50 50], clipEdge([50 -50 50 50], bb),1e-6);
 192 %!assert ([100 70 80 50], clipEdge([130 100 80 50], bb),1e-6);
 193 %!assert ([100 30 80 50], clipEdge([130 0 80 50], bb),1e-6);
 194 %!assert ([0 70 20 50], clipEdge([-30 100 20 50], bb),1e-6);
 195 %!assert ([0 30 20 50], clipEdge([-30 0 20 50], bb),1e-6);
 196 %!assert ([70 100 50 80], clipEdge([100 130 50 80], bb),1e-6);
 197 %!assert ([30 100 50 80], clipEdge([0 130 50 80], bb),1e-6);
 198 %!assert ([70 0 50 20], clipEdge([100 -30 50 20], bb),1e-6);
 199 %!assert ([30 0 50 20], clipEdge([0 -30 50 20], bb),1e-6);
 200 %!assert ([0 20 80 100], clipEdge([-10 10 90 110], bb),1e-6);
 201
 202
 203