octave_packages/geometry-1.5.0/geom2d/isCounterClockwise.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{ccw} = } isCounterClockwise (@var{p1}, @var{p2}, @var{p3})
  36 %% @deftypefnx {Function File} {@var{ccw} = } isCounterClockwise (@var{p1}, @var{p2}, @var{p3},@var{tol})
  37 %% Compute relative orientation of 3 points
  38 %%
  39 %%   Computes the orientation of the 3 points. The returns is:
  40 %%   +1 if the path  @var{p1}-> @var{p2}-> @var{p3} turns Counter-Clockwise (i.e., the point  @var{p3}
  41 %%       is located "on the left" of the line  @var{p1}- @var{p2})
  42 %%   -1 if the path turns Clockwise (i.e., the point  @var{p3} lies "on the right"
  43 %%       of the line  @var{p1}- @var{p2})
  44 %%   0  if the point  @var{p3} is located on the line segment [ @var{p1}  @var{p2}].
  45 %%
  46 %%   This function can be used in more complicated algorithms: detection of
  47 %%   line segment intersections, convex hulls, point in triangle...
  48 %%
  49 %%    @var{ccw} = isCounterClockwise( @var{p1},  @var{p2},  @var{p3}, EPS);
  50 %%   Specifies the threshold used for detecting colinearity of the 3 points.
  51 %%   Default value is 1e-12 (absolute).
  52 %%
  53 %%   Example
  54 %%
  55 %% @example
  56 %%   isCounterClockwise([0 0], [10 0], [10 10])
  57 %%   ans =
  58 %%       1
  59 %%   isCounterClockwise([0 0], [0 10], [10 10])
  60 %%   ans =
  61 %%       -1
  62 %%   isCounterClockwise([0 0], [10 0], [5 0])
  63 %%   ans =
  64 %%       0
  65 %% @end example
  66 %%
  67 %%   @seealso{points2d, isPointOnLine, isPointInTriangle}
  68 %% @end deftypefn
  69
  70 function res = isCounterClockwise(p1, p2, p3, varargin)
  71
  72   % get threshold value
  73   eps = 1e-12;
  74   if ~isempty(varargin)
  75       eps = varargin{1};
  76   end
  77
  78   % ensure all data have same size
  79   np = max([size(p1, 1) size(p2, 1) size(p3,1)]);
  80   if np > 1
  81       if size(p1,1) == 1
  82           p1 = repmat(p1, np, 1);
  83       end
  84       if size(p2,1) == 1
  85           p2 = repmat(p2, np, 1);
  86       end
  87       if size(p3,1) == 1
  88           p3 = repmat(p3, np, 1);
  89       end
  90   end
  91
  92   % init with 0
  93   res = zeros(np, 1);
  94
  95   % extract vector coordinates
  96   x0  = p1(:, 1);
  97   y0  = p1(:, 2);
  98   dx1 = p2(:, 1) - x0;
  99   dy1 = p2(:, 2) - y0;
 100   dx2 = p3(:, 1) - x0;
 101   dy2 = p3(:, 2) - y0;
 102
 103   % check non colinear cases
 104   res(dx1 .* dy2 > dy1 .* dx2) =  1;
 105   res(dx1 .* dy2 < dy1 .* dx2) = -1;
 106
 107   % case of colinear points
 108   ind = abs(dx1 .* dy2 - dy1 .* dx2) < eps;
 109   res(ind( (dx1(ind) .* dx2(ind) < 0) | (dy1(ind) .* dy2(ind) < 0) )) = -1;
 110   res(ind(  hypot(dx1(ind), dy1(ind)) <  hypot(dx2(ind), dy2(ind)) )) =  1;
 111
 112 endfunction
 113
 114 %!shared p0,pu,pd,pl,pr
 115 %!  p0 = [2, 3]; % center point
 116 %!  pu = [2, 4]; % up point
 117 %!  pd = [2, 2]; % down point
 118 %!  pl = [1, 3]; % left point
 119 %!  pr = [3, 3]; % right point
 120
 121 %!assert (+1, isCounterClockwise(pl, p0, pu));
 122 %!assert (+1, isCounterClockwise(pd, p0, pl));
 123 %!assert (+1, isCounterClockwise(pr, p0, pd));
 124 %!assert (+1, isCounterClockwise(pu, p0, pr));
 125
 126 % turn 90° right => return -1
 127 %!assert (-1, isCounterClockwise(pl, p0, pd));
 128 %!assert (-1, isCounterClockwise(pd, p0, pr));
 129 %!assert (-1, isCounterClockwise(pr, p0, pu));
 130 %!assert (-1, isCounterClockwise(pu, p0, pl));
 131
 132 %!test  % turn 90° left => return +1
 133 %!  pts1 = [pl;pd;pr;pu;pl;pd;pr;pu];
 134 %!  pts2 = [p0;p0;p0;p0;p0;p0;p0;p0];
 135 %!  pts3 = [pu;pl;pd;pr;pd;pr;pu;pl];
 136 %!  expected = [1;1;1;1;-1;-1;-1;-1];
 137 %!  result = isCounterClockwise(pts1, pts2, pts3);
 138 %!  assert (result, expected, 1e-6);
 139
 140 % aligned with p0-p1-p2 => return +1
 141 %!assert (+1, isCounterClockwise(pl, p0, pr));
 142 %!assert (+1, isCounterClockwise(pu, p0, pd));
 143 %!assert (+1, isCounterClockwise(pr, p0, pl));
 144 %!assert (+1, isCounterClockwise(pd, p0, pu));
 145
 146 % aligned ]ith p0-p2-p1 => return 0
 147 %!assert (0, isCounterClockwise(pl, pr, p0));
 148 %!assert (0, isCounterClockwise(pu, pd, p0));
 149 %!assert (0, isCounterClockwise(pr, pl, p0));
 150 %!assert (0, isCounterClockwise(pd, pu, p0));
 151
 152 % aligned with p1-p0-p2 => return -1
 153 %!assert (-1, isCounterClockwise(p0, pl, pr));
 154 %!assert (-1, isCounterClockwise(p0, pu, pd));
 155 %!assert (-1, isCounterClockwise(p0, pr, pl));
 156 %!assert (-1, isCounterClockwise(p0, pr, pl));