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>
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{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.
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.
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.
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.
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
56 % @seealso{edges2d, points2d, isPointOnLine}
59 function b = isPointOnEdge(point, edge, varargin)
61 % extract computation tolerance
67 % number of edges and of points
71 % adapt size of inputs if needed, and extract elements for computation
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);
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);
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);
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)
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;
104 lx = repmat(point(:, 1), 1, Ne) - x0;
105 ly = repmat(point(:, 2), 1, Ne) - y0;
108 % test if point is located on supporting line
109 b1 = (abs(lx.*dy - ly.*dx) ./ hypot(dx, dy)) < tol;
111 % compute position of point with respect to edge bounds
112 % use different tests depending on line angle
113 ind = abs(dx) > abs(dy);
115 t(ind) = lx( ind) ./ dx( ind);
116 t(~ind) = ly(~ind) ./ dy(~ind);
118 % check if point is located between edge bounds
119 b = t >- tol & t-1 < tol & b1;
123 %!shared points, vertices, edges
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], :)];
132 %! % Test one point and one edge
133 %! isPointOnEdge(points(1,:), edges(1,:))
134 %! isPointOnEdge(points(3,:), edges(1,:))
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], :)];
143 %! % Test one point and several edges
144 %! isPointOnEdge(points(1,:), edges)'
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], :)];
153 %! % Test several points and one edge
154 %! isPointOnEdge(points, edges(1,:))'
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], :)];
163 %! % Test N points and N edges
164 %! isPointOnEdge(points, edges(1:3,:))'
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], :)];
173 %! % Test NP points and NE edges
174 %! isPointOnEdge(points, edges)
181 %! assert (isPointOnEdge(p0, edge));
183 %! assert (isPointOnEdge(p0, edge));
185 %! assert (isPointOnEdge(p0, edge));
187 %! assert (!isPointOnEdge(p0, edge));
189 %! assert (!isPointOnEdge(p0, edge));
191 %! assert (!isPointOnEdge(p0, edge));
193 %! assert (!isPointOnEdge(p0, edge));
200 %! assert (isPointOnEdge(p0, edge));
202 %! assert (isPointOnEdge(p0, edge));
204 %! assert (isPointOnEdge(p0, edge));
206 %! assert (!isPointOnEdge(p0, edge));
208 %! assert (!isPointOnEdge(p0, edge));
210 %! assert (!isPointOnEdge(p0, edge));
212 %! assert (!isPointOnEdge(p0, edge));
218 %! assert (isPointOnEdge(p1, edge));
219 %! assert (isPointOnEdge(p2, edge));
221 %! assert (isPointOnEdge(p0, edge));
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));
229 %! assert (!isPointOnEdge(p0, edge));
232 %! edge = [10 20 80 20; 20 10 20 80; 20 10 60 70];
234 %! assert ([true ; true ; false], isPointOnEdge(p0, edge));
241 %! assert (isPointOnEdge(p1, edge));
242 %! assert (isPointOnEdge(p2, edge));
244 %! assert (isPointOnEdge(p0, edge));
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));
259 %! assert (isPointOnEdge(p1, edge));
260 %! assert (isPointOnEdge(p2, edge));
262 %! assert (isPointOnEdge(p0, edge));
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));
276 %! p0 = [10 20; 80 20; 50 20;50 21];
277 %! exp = [true;true;true;false];
278 %! assert (exp, isPointOnEdge(p0, edge));
285 %! exp = [true;true;true;true];
286 %! assert (exp, isPointOnEdge(p0, [edge;edge;edge;edge]));
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));