连接一组点以获得非自相交非凸多边形

Question

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

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

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

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个构建示例，并且代码需要适用于所有人。有些建筑物在拐角之间没有保留正确的角度标准。我正在附上我拥有的数据。我拥有的点是通过整合多边形获得的。那么有没有办法在集成之前使用这个多边形（点按顺序排列）实际数据

Answer 1

编辑

因此，我可以使用下面提到的想法找到解决方案。

备注：我手动添加了一个缺失点。而且，我删除了底部的两个小角。要么这些必须总共是四个角，要么可以将它们视为根本没有角。

我明确指出，由于我的想法包含了假设，因此拐角通常具有90度角。

一般的做法

• 通过下述方法求出点的顺序。
• 对于所有点，在找到的顺序的限制内确定潜在的“邻居”。
• 对于每两个邻居，确定邻居＃1-当前点-邻居＃2之间的角度。理想情况下，该角度应为90度。
• 对于所有候选组合，找到具有最小总距离的组合，即距离（邻居＃1-当前点）+距离（当前点-邻居＃2）。

我意识到，通过在所有点上使用for循环，导致两次绘制所有线条。同样，许多计算可能会被矢量化并从循环中移出。优化不是我现在的意图。;-)

% Point data of building corners; modified!
X = [285.400 372.267 397.067 408.133 382.471 379.533 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 = [130.150 233.360 228.627 286.693 314.541 292.960 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];

% Place approximative center of building at (0, 0)
X = X - mean(X);
Y = Y - mean(Y);
C = [mean(X), mean(Y)];

% Sort points by angle with respect to center
[~, idx] = sort(atan2(X, Y));

% Rearrange points with respect to sorted angles
X = X(idx);
Y = Y(idx);

% Number of data points
n = numel(X);

% Calculate direction vectors for X and Y coordinates
dvX = repmat(X.', 1, n);
dvX = dvX - dvX.';
dvY = repmat(Y.', 1, n);
dvY = dvY - dvY.';

% Calculate distances
dst = sqrt(dvX.^2 + dvY.^2);

% Number of "neighbouring" points to be considered with respect to the order
nn = 8;


figure(1);
hold on;

% Center
plot(C(1), C(2), 'kx', 'MarkerSize', 15);

% Plain points
plot(X, Y, '.', 'MarkerSize', 15);

for k = 1:n

  % Index  
  text(X(k) + 0.05, Y(k) + 0.05, num2str(k), 'FontSize', 12);

  % Set up neighbourhood  
  nbh = mod([k-nn/2:k-1 k+1:k+nn/2], n);
  nbh(nbh == 0) = n;

  % Calculate angles and total distance arrays
  ang = Inf(nn);
  len = Inf(nn);
  for ii = 1:nn
    l = nbh(ii);
    d1 = [dvX(k, l) dvY(k, l)];
    for jj = ii+1:nn
      m = nbh(jj);
      d2 = [dvX(k, m) dvY(k, m)];
      len(ii, jj) = dst(k, l) + dst(k, m);
      ang(ii, jj) = abs(pi/2 - acos(dot(d1, d2) / (norm(d1) * norm(d2))));
    end
  end

  % Find candidates with angle difference < 10 degree
  cand = find(ang < pi/18);

  % For these candidates, find the one with the shortest total distance
  [~, I] = min(len(cand));

  % Get corresponding indices
  [I, J] = ind2sub([nn nn], cand(I));
  cand = nbh([I J]);

  % Lines 
  plot([X(k) X(cand(1))], [Y(k) Y(cand(1))], 'b', 'LineWidth', 1);
  plot([X(k) X(cand(2))], [Y(k) Y(cand(2))], 'b', 'LineWidth', 1);

end

hold off;

输出图像：

近似（！）解决方案是确定由找到的点描述的轮廓的中心，并atan2相对于中心按角度对点进行排序。请参见以下代码段进行可视化：

% Points
X = 2 * rand(1, 15) - 1;
Y = 2 * rand(1, 15) - 1;

% Center
C = [0, 0];

% Determine indices
[~, idx] = sort(atan2(X, Y));

figure(1);
hold on;

% Center
plot(C(1), C(2), 'kx', 'MarkerSize', 15);

% Plain points
plot(X, Y, '.', 'MarkerSize', 15);

% Indices and lines
for k = 1:numel(X)
  text(X(idx(k)) + 0.05, Y(idx(k)) + 0.05, num2str(k), 'FontSize', 12);
  if (k == numel(X))
    plot([X(idx(k)) X(idx(1))], [Y(idx(k)) Y(idx(1))], 'b');
  else
    plot([X(idx(k)) X(idx(k+1))], [Y(idx(k)) Y(idx(k+1))], 'b');
  end
end

hold off;

提供以下输出：

尽管我敢肯定，一定数量的凹面将得到正确处理，但恐怕对于给定的示例（尤其是上半部分），它会失败。这是因为图像不是完美的俯视图，因此角度有些“失真”。

不过，订购也许可以提高您的最小距离方法。