Connect Randomly Ordered 2D Points into a Minimal Nearest-Neighbor Closed Contour 1.0

Connects randomly ordered 2D points into a minimal nearest neighbor contour.points2contourTristan UrsellFebruary 2012 [Xout,Yout]=points2contour(Xin,Yin,P,direction) Given any list of 2D points (Xin,Yin), construct a singly connected nearest-neighbor path in either the 'cw' or 'ccw' directions. The code has been written to handle square and hexagon grid points, as well as any non-grid arrangement of points. 'P' sets the point to begin looking for the contour from the original ordering of (Xin,Yin), and 'direction' sets the direction of the contour, with options 'cw' and 'ccw', specifying clockwise and counter-clockwise, respectively. There are many (Inf) situations where there is no unique mapping of points into a connected contour -- e.g. any time there are more than 2 nearest neighbor points, or in situations where the nearest neighbor matrix is non-symmetric. Picking a different P will result in a different contour. Likewise, in cases where one point is far from its neighbors, it may be orphaned, and only connected into the path at the end, giving strange results. The input points can be of any numerical class. Note that this will *not* neccessarily form the shortest path between all the points -- that is the NP-Hard Traveling Salesman Problem, for which there is no deterministic solution. This will, however, find the shortest path for points with a symmetric nearest neighbor matrix. see also: bwtraceboundary Example 1: continuous pointsN=200;P=1;theta=linspace(0,2*pi*(1-1/N),N);[~,I]=sort(rand(1,N));R=2+sin(5*theta(I))/3;Xin=R.*cos(theta(I));Yin=R.*sin(theta(I));[Xout,Yout]=points2contour(Xin,Yin,P,'cw');figure;hold onplot(Xin,Yin,'b-')plot(Xout,Yout,'r-','Linewidth',2)plot(Xout(2:end-1),Yout(2:end-1),'k.','Markersize',15)plot(Xout(1),Yout(1),'g.','Markersize',15)plot(Xout(end),Yout(end),'r.','Markersize',15)xlabel('X')ylabel('Y')axis equal tighttitle(['Black = original points, Blue = original ordering, Red = new ordering, Green starting points'])box on Example 2: square gridP=1;Xin=[1,2,3,4,4,4,4,3,2,1,1,1];Yin=[0,0,0,0,1,2,3,3,2,2,1,0];[Xout,Yout]=points2contour(Xin,Yin,P,'cw');figure;hold onplot(Xin,Yin,'b-')plot(Xout,Yout,'r-','Linewidth',2)plot(Xout(2:end-1),Yout(2:end-1),'k.','Markersize',15)plot(Xout(1),Yout(1),'g.','Markersize',15)plot(Xout(end),Yout(end),'r.','Markersize',15)xlabel('X')ylabel('Y')axis equal tightbox on Example 3: continuous points, pathological caseN=200;P=1;theta=linspace(0,2*pi*(1-1/N),N);[~,I]=sort(rand(1,N));R=2+sin(5*theta(I))/3;Xin=(1+rand(1,N)/2).*R.*cos(theta(I));Yin=(1+rand(1,N)/2).*R.*sin(theta(I));[Xout,Yout]=points2contour(Xin,Yin,P,'cw'); figure;hold onplot(Xin,Yin,'b-')plot(Xout,Yout,'r-','Linewidth',2)plot(Xout(2:end-1),Yout(2:end-1),'k.','Markersize',15)plot(Xout(1),Yout(1),'g.','Markersize',15)plot(Xout(end),Yout(end),'r.','Markersize',15)xlabel('X')ylabel('Y')axis equal tighttitle(['Black = original points, Blue = original ordering, Red = new ordering, Green = starting points'])box on

Requirements:	No special requirements
Platforms:	Matlab
Keyword:	Bwtraceboundary,  Deterministic,  Nphard,  Problem,  Salesman,  Solution,  Symmetric,  Traveling
Users rating:	0/10