order_loop

ORDER_LOOP Order a list of points on a loop
 P = ORDER_LOOP(PP) orders clockwise a matrix PP (N x D) of N points in D 
 dimensions that constitute a continues loop, under the assumption that 
 the distance between two neighbouring points is always smaller than 
 distance between any non-neighbouring points.

 [P,idx] = ORDER_LOOP(PP, CLK) orders the loop clockwise if
   CLK == 1 and counter-clockwise if CLK == 0.
 idx is the sort index of the points

0001 function [p n] = order_loop(pp,clk)
0002 %ORDER_LOOP Order a list of points on a loop
0003 % P = ORDER_LOOP(PP) orders clockwise a matrix PP (N x D) of N points in D
0004 % dimensions that constitute a continues loop, under the assumption that
0005 % the distance between two neighbouring points is always smaller than
0006 % distance between any non-neighbouring points.
0007 %
0008 % [P,idx] = ORDER_LOOP(PP, CLK) orders the loop clockwise if
0009 %   CLK == 1 and counter-clockwise if CLK == 0.
0010 % idx is the sort index of the points
0011 
0012 % (C) 2012 Bartlomiej Grychtol.
0013 % License: GPL version 2 or version 3
0014 % $Id: order_loop.m 5459 2017-05-03 00:35:43Z aadler $
0015 
0016 if ischar(pp) && strcmp(pp,'UNIT_TEST'); do_unit_test; return, end;
0017 
0018 if nargin == 1
0019    clk = 1;
0020 end
0021 if size(pp,1) <= 1;  % only one element in loop, no need to order
0022   p = pp; n=size(pp,1);
0023   return
0024 end
0025 
0026 D = distmat(pp) + diag(inf*ones(length(pp),1));
0027 p = zeros(size(pp));
0028 n = zeros(size(pp,1),1);
0029 N = 1:size(pp,1);
0030 p(1,:) = pp(1,:);
0031 idx1 = 1;
0032 n(1) = 1;
0033 for i = 1:length(pp)-1
0034    [jnk,idx2] = min(D(idx1,:));
0035    p(i+1,:) = pp(idx2,:);
0036    D(:,idx1) = [];
0037    D(idx1,:) = [];
0038    pp(idx1,:) = [];
0039    N(idx1)   = [];
0040    if idx2 > idx1
0041       idx1 = idx2-1;
0042    else
0043       idx1 = idx2;
0044    end
0045    n(i+1) = N(idx1);
0046 end
0047 ctr = mean(p);
0048 tmp = p - repmat(ctr,length(p),1);
0049 [th,r]=cart2pol(tmp(:,1),tmp(:,2)); % OCTAVE BUG in 3.7 - needs 2 outputs
0050 th = unwrap(th);
0051 
0052 if th(1) < th(end)
0053    %counter-clockwise
0054    p = flipud(p);
0055 end
0056 
0057 if clk == -1
0058    p = flipud(p);
0059 end
0060 
0061 
0062 function do_unit_test
0063 t = linspace(0,2*pi,101); t(end) = [];
0064 p1(:,1) = sin(t);
0065 p1(:,2) = 4*cos(t);
0066 n = randperm(100);
0067 p2 = p1(n,:);
0068 p3 = order_loop(p2);
0069 expect1= circshift(p1,-n(1));
0070 expect2= circshift(p1,-n(1)+1);
0071 %% No idea why it could be either -- AA, May2015
0072 unit_test_cmp('order_loop:t2', ...
0073     all(all(p3==expect1)) | all(all(p3== expect2)),1);
0074 
0075