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>
5 %% All rights reserved.
6 %% (simplified BSD License)
8 %% Redistribution and use in source and binary forms, with or without
9 %% modification, are permitted provided that the following conditions are met:
11 %% 1. Redistributions of source code must retain the above copyright notice, this
12 %% list of conditions and the following disclaimer.
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.
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.
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.
35 %% @deftypefn {Function File} {@var{edge} =} clipLine (@var{line}, @var{box})
36 %% Clip a line with a box.
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.
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
53 %% line = [30 40 10 0];
54 %% box = [0 100 0 100];
55 %% res = clipLine(line, box)
60 %% @seealso{lines2d, boxes2d, edges2d, clipEdge, clipRay}
63 function edge = clipLine(lin, bb, varargin)
65 % adjust size of two input arguments
67 lin = repmat(lin, 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');
75 nbLines = size(lin, 1);
76 edge = zeros(nbLines, 4);
80 % extract limits of the box
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));
91 % compute intersection with each edge of the box
94 px1 = intersectLines(lin(i,:), [xmin ymin delta 0]);
96 px2 = intersectLines(lin(i,:), [xmax ymin 0 delta]);
98 py1 = intersectLines(lin(i,:), [xmax ymax -delta 0]);
100 py2 = intersectLines(lin(i,:), [xmin ymax 0 -delta]);
102 % remove undefined intersections (case of lines parallel to box edges)
103 points = [px1 ; px2 ; py1 ; py2];
104 points = points(isfinite(points(:,1)), :);
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, :);
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];
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;
123 % if one of the bounding condition is not met, set edge to NaN
131 %! lin = [30 40 10 0];
132 %! bb = [0 100 0 100];
133 %! res = clipLine(lin, bb)
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);
140 %! axis(v+[0 10 -10 0])
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);
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);
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);
177 %!test %multilines % inside, top right corner
178 %! bb = [0 100 0 100];
182 %! 140 -30 10 10; ...
187 %! NaN NaN NaN NaN; ...
188 %! NaN NaN NaN NaN; ...
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);
196 %!test % test clipping of horizontal lines % inside, to the right
197 %! bb = [-1 1 -1 1]*1e10;
200 %! edge = [3-D/2 -D 3+D/2 D];
201 %! clipped = clipLine(lin, bb);
202 %! assert (edge, clipped);
204 %!test % inside, to the right
205 %! bb = [-1 1 -1 1]*100;
206 %! lin = [3 0 1*1e10 2*1e10];
208 %! edge = [3-D/2 -D 3+D/2 D];
209 %! clipped = clipLine(lin, bb);
210 %! assert (edge, clipped, 1e-6);