连接一组点以获得非自相交的非凸多边形 [英] Connecting a set of points to get a non-self-intersecting non-convex polygon

问题描述

我有一组无序的2D点，它们代表建筑物的各个角落.我需要连接它们以获得建筑物的轮廓.

I have an unordered set of 2D points which represents the corners of a building. I need to connect them to get the outline of the building.

这些点是通过组合不同个人收集的不同多边形而获得的.我的想法是使用这些多边形按顺序获取点(例如，获取最大和最小多边形之间的区域并连接点，使其进入该区域).

The points were obtained by combining different polygons collected by different individuals. My idea is to use these polygons to get the points in order (e.g. taking the region between the biggest and smallest polygons and connect the points such that it comes in this region).

我尝试使用最小距离标准，并且还基于角度连接点.但不幸的是，它不起作用.我有用的一件事是点顺序正确的许多多边形的原始数据.那么有可能与这些多边形进行比较以连接这些点吗?如上所述，我的教授提出了采用最大和最小多边形并将中间的区域用作缓冲区的想法.所有的点都将落在该缓冲区中.但是我不确定如何实现.

I tried using the minimum distance criteria and also to connect the points based on angles. But unfortunately it doesn't work. One useful thing which I have is the raw data of many polygons in which the point order is correct. So is there any possibility to compare with those polygons to connect these points? As I mentioned above, my professor gave the idea to take the biggest and the smallest polygons and use the area in between as a buffer. All the points will fall in this buffer area. But I am not sure how to implement this.

X = [364.533 372.267 397.067 408.133 382.471 379.533 329.250 257.200 199.412 195.267 184.385 168.643 157.533 174.500 108.533 99.333 150.733 184.800 138.105 179.474 218.278 232.133 267.714 306.929 312.143 357.733 421.333 431.000 371.867 364.533]; 
Y = [192.027 233.360 228.627 286.693 314.541 292.960 327.450 340.500 348.671 326.693 269.308 330.857 274.493 226.786 239.200 193.467 182.760 101.893 111.000 80.442 74.356 140.360 64.643 56.857 77.786 69.493 133.293 180.427 142.160 192.027];

预期结果是一个闭合的多边形，代表建筑物的平面图.我有15个构建示例，并且代码需要适用于所有人.一些建筑物在拐角之间没有保留正确的角度标准.我正在附上我拥有的数据.我拥有的点是通过整合多边形获得的.因此，有什么方法可以使用此多边形(点按顺序排列)集成前的实际数据

The expected result is a closed polygon which represents the plan of the building. I have 15 building samples and the code needs to work for all. Some buildings don't preserve the right angle criteria between the corners. I am attaching the data which i had. The points i have is obtained by integrating the polygons. So is there any way to use this polygons(in which the points are in order)actual data before integration

推荐答案

答案的概念是旅行商问题".将在这些点周围创建一个缓冲区，并将该缓冲区作为附加条件包括在内.

The concept used for the answer is the 'Travelling salesman problem'. A buffer is created around the points and this buffer is included as an extra criterion.

a=[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];
b=[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 = [a' b'];
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
[s,t] = boundary(polyout);  %%this is the boundary polygon of the buffer 
numPoints = length(clustersCentroids);
x = X; %these are the points to be connected
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);

这篇关于连接一组点以获得非自相交的非凸多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！