Joining a set of points inside a buffer to get a polygon.

I have a set of points which is not in correct order. I need to connect those points to get a closed polygon (The polygon is a plan of the building). I am able to create a buffer around the points which is in the shape of the required polygon. I need to connect points with two conditions. Connect the points to the nearest neighbour so that, the line joining the points should not cross the boundary of the buffer. I have many building samples like this and this is the method which will work for all.

x=[141 188 178 217 229 282 267 307 313 357 372 422 434 365 372 398 411 382 382 233 229 191 185 166 156 183 173 114 97 149 139 139];
y=[109 103 79 76 140 132 64 56 78 72 141 133 180 192 234 228 287 293 315 348 343 348 329 332 270 268 225 240 194 184 108 108];
X=[364.5333 232.1333 397.0667 157.5333 431 421.3333 306.9286 184.3846 357.7333 199.4118 168.6429 179.4737 408.1333 382.4706 150.7333 372.2667 184.8 138.1053 312.1429 108.5333 174.5 195.2667 257.2 99.33333 379.5333 371.8667 329.25 280.7059 267.7143 218.2778];
Y=[192.0267 140.36 228.6267 274.4933 180.4267 133.2933 56.85714 269.3077 69.49333 348.6706 330.8571 80.44211 286.6933 314.5412 182.76 233.36 101.8933 111 77.78571 239.2 226.7857 326.6933 340.5 193.4667 292.96 142.16 327.45 130.5529 64.64286 74.35556];
R = [x' y'];
d = 12;
polyout = polybuffer(R,'lines',d)
figure
 %imshow(I2);
hold on
%plot(R(:,1),R(:,2),'r.','MarkerSize',10)
plot(X,Y,'r.', 'MarkerSize', 15)
plot(polyout)
axis equal
hold off

[KSSV]

Which points you want to join? [X Y] or R?

[Nikhil Jose]

@KSSV [X Y] (Capital letters). R is thze data for creating the buffer. Thanks

Answer 1

[Nikhil Jose]

[s,t] = boundary(polyout);  %%this is the boundary polygon of the buffer 
numPoints = length(clustersCentroids);
x = X;  %points to be joined
y = Y;
x([1 2],:)=x([2 1],:);
y([1 2],:)=y([2 1],:);
figure
plot(x, y, 'bo', 'LineWidth', 2, 'MarkerSize', 17);
grid on;
 imshow(I2);
xlabel('X', 'FontSize', 10);
ylabel('Y', 'FontSize', 10);
% Make a list of which points have been visited
beenVisited = false(1, numPoints);
% Make an array to store the order in which we visit the points.
visitationOrder = ones(1, numPoints);
% Define a filasafe
maxIterations = numPoints + 1;
iterationCount = 1;
% Define a current index.  currentIndex will be 1 to start and then will vary.
currentIndex = 1;
while sum(beenVisited) < numPoints
    visitationOrder(iterationCount) = currentIndex; 
  beenVisited(currentIndex) = true; 
  % Get the x and y of the current point.
  thisX = x(currentIndex);
  thisY = y(currentIndex);
  %text(thisX + 0.01, thisY, num2str(currentIndex), 'FontSize', 35, 'Color', 'r');
  % Compute distances to all other points
  distances = sqrt((thisX - x) .^ 2 + (thisY - y) .^ 2);
  distances(beenVisited)=inf;
   distances(currentIndex) = inf;
  % Don't consider visited points by setting their distance to infinity.
  [out,idx] = sort(distances);
  xx=[x(currentIndex) x(idx(1))]
   yy=[y(currentIndex) y(idx(1))]
  if isempty(polyxpoly(xx,yy,s,t))
   iterationCount = iterationCount + 1;
   currentIndex =idx(1);
  else 
     xx=[x(currentIndex) x(idx(2))]
   yy=[y(currentIndex) y(idx(2))]  
  if isempty(polyxpoly(xx,yy,s,t))
   iterationCount = iterationCount + 1;
   currentIndex =idx(2);
   else 
     xx=[x(currentIndex) x(idx(3))]
   yy=[y(currentIndex) y(idx(3))]  
  if isempty(polyxpoly(xx,yy,s,t))
   iterationCount = iterationCount + 1;
   currentIndex =idx(3);
   else 
     xx=[x(currentIndex) x(idx(4))]
   yy=[y(currentIndex) y(idx(4))]  
  if isempty(polyxpoly(xx,yy,s,t))
   iterationCount = iterationCount + 1;
   currentIndex =idx(4);
  end
  end
  end
  end
end

% Plot lines in that order.
hold on;
orderedX = [x(visitationOrder); x(1)];
orderedY = [y(visitationOrder) ;y(1)];
plot(orderedX,orderedY, 'm-', 'LineWidth', 2);
title('Result', 'FontSize', 10);

The method used here was a modified form of 'travelling salesman problem'. The condition of the buffer is included into this concept.

Answer 2

[KSSV]

X=[364.5333 232.1333 397.0667 157.5333 431 421.3333 306.9286 184.3846 357.7333 199.4118 168.6429 179.4737 408.1333 382.4706 150.7333 372.2667 184.8 138.1053 312.1429 108.5333 174.5 195.2667 257.2 99.33333 379.5333 371.8667 329.25 280.7059 267.7143 218.2778];
Y=[192.0267 140.36 228.6267 274.4933 180.4267 133.2933 56.85714 269.3077 69.49333 348.6706 330.8571 80.44211 286.6933 314.5412 182.76 233.36 101.8933 111 77.78571 239.2 226.7857 326.6933 340.5 193.4667 292.96 142.16 327.45 130.5529 64.64286 74.35556];

%% Order the points 
P = [X' Y'] ; 
c = mean(P); % mean/ central point 
d = P-c ; % vectors connecting the central point and the given points 
th = atan2(d(:,2),d(:,1)); % angle above x axis
[th, idx] = sort(th);   % sorting the angles 
P = P(idx,:); % sorting the given points
P = [P ; P(1,:)]; % add the first at the end to close the polygon 

figure
hold on
plot(X,Y,'b')
plot( P(:,1), P(:,2), 'r');

legend('before sorting','after sorting')

[Nikhil Jose]

@KSSV I already tried sorting the points based on the angles from the centroid. But i was not getting the expected results. I need to somehow make use of the buffer. Is there a way to check "if the line connecting the points is always inside the buffer region?" Thanks

[KSSV]

The buffer must be giving you coordinates of the polygon......with those polygons use inpolygon and check whether point lies inside or outside.

[Nikhil Jose]

The buffer does not give the right coordinates. Because the coordinates used for the buffer is the points from one input dataset which was available to me. the points to be connected is after some integration process. So the coordinates changed during this process.