octave_packages/geometry-1.5.0/geom2d/closed_path.m

   1 %% Copyright (C) 2012 Simeon Simeonov <simeon.simeonov.s@gmail.com>
   2 %%
   3 %%    This program is free software: you can redistribute it and/or modify
   4 %%    it under the terms of the GNU General Public License as published by
   5 %%    the Free Software Foundation, either version 3 of the License, or
   6 %%    any later version.
   7 %%
   8 %%    This program is distributed in the hope that it will be useful,
   9 %%    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 %%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 %%    GNU General Public License for more details.
  12 %%
  13 %%    You should have received a copy of the GNU General Public License
  14 %%    along with this program. If not, see <http://www.gnu.org/licenses/>.
  15
  16 %% -*- texinfo -*-
  17 %% @deftypefn {Function File} {@var{y} =} polygon (@var{x})
  18 %% Returns a simple closed path that passes through all the points in @var{x}.
  19 %% @var{x} is a vector containing 2D coordinates of the points.
  20 %%
  21 %% @end deftypefn
  22
  23 %% Author: Simeon Simeonov <simeon.simeonov.s@gmail.com>
  24
  25 function y = closed_path(x)
  26
  27   if(size(x,1) > 1 && size(x,1) < size(x,2))
  28       x = x';
  29   end
  30
  31   N = size(x,1); % Number of points
  32   idx = zeros(N, 1); % ind contains the indices of the sorted coordinates
  33
  34   a = find(x(:,2)==min(x(:,2)));
  35
  36   if(size(a,1) > 1)
  37       [~, i] = sort(x(a,1));
  38       a = a(i(1));
  39   end
  40
  41   x_1 = x(x(:,2)==x(a,2),:); % find all x with the same y coordinate
  42
  43   if(x(a,1) == min(x(:,1)))
  44       x_2 = x(x(:,1)==x(a,1),:); % find all x with the same x coordinate
  45   else
  46      x_2 = x(a,:);
  47   end
  48
  49   if(size(x_1,1) > 1 || size(x_2,1) > 1)
  50       if(size(x_1,1) > 1)
  51           x_1 = sort(x_1); % Sort by x coordinate
  52           y(1,:) = x(a,:); % original starting point
  53       end
  54
  55       if (size(x_2,1) > 1)
  56           x_2 = sort(x_2, 'descend');
  57       end
  58
  59       x_not = [x_1; x_2];
  60       i = ismember(x,x_not,'rows');
  61       x(i, :) = [];
  62       x = [x_1(size(x_1,1),:); x];
  63       x_1(size(x_1, 1),:) = [];
  64       N = size(x,1);
  65       a = 1;
  66   else
  67       x_1 = [];
  68       x_2 = x(a,:);
  69   end
  70   d = x - repmat(x(a,:), N, 1);
  71   th = d(:,2)./(d(:,1) + d(:,2));
  72
  73   [~, idx0] = ismember(sort(th(th==0)), th);
  74   [~, idx1] = ismember(sort(th(th>0)), th);
  75   [~, idx2] = ismember(sort(th(th<0)), th);
  76
  77   idx = [a; idx0; idx1; idx2];
  78   % I contains the indices of idx in a sorted order. [v i] = sort(idx) then
  79   % i==I.
  80   [~,I,J]= unique(idx);
  81   if(size(I,1) ~= size(J,1))
  82       R = histc(J, 1:size(I,1)); % R(1) will always be 1?
  83       idx_sorted = idx(I);
  84       r = find(R>1);
  85       for ri = r'
  86           idx_repeated = idx_sorted(ri);
  87           idx(idx==idx_repeated) = find(th==th(idx_sorted(ri)));
  88       end
  89   end
  90
  91   y = [x_1; x(idx,:); x_2;];
  92
  93 endfunction
  94
  95 %!demo
  96 %! maxInt = 100;
  97 %! N = 25;
  98 %!
  99 %! for i = 1:5
 100 %!   x = randi(maxInt, N, 2);
 101 %!   y = closed_path(x);
 102 %!   plot(y(:,1), y(:,2), '*');
 103 %!   hold on;
 104 %!   plot(y(:,1), y(:,2));
 105 %! end