РЕДАКТИРОВАТЬ
Итак, я мог бы найти решение, используя мою нижеприведенную идею.
Замечания: Я добавил одну отсутствующую точку вручную.И я удалил два крошечных уголка внизу.Либо это должно быть всего четыре угла, либо они могут рассматриваться как углы вообще.
Я прямо заявляю, что, поскольку моя идея включает в себя предположение, что углы обычно имеют угол 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;
Дает следующий вывод:
Хотя я уверен, чтоЯ боюсь, что определенное количество вогнутостей будет правильно обработано для данного примера (особенно для верхней части).Это потому, что изображение не является идеальным видом сверху, поэтому углы немного «искажены».
Тем не менее, возможно, порядок может увеличить ваш подход к минимальному расстоянию.