Два существующих ответа имеют большие недостатки:
Метод Дурки работает только в том случае, если расстояния между последующими точками в точности совпадают. Точки должны иметь координаты, прекрасно представимые в виде значений с плавающей точкой, чтобы расстояния между последующими точками на линии можно было считать одинаковыми. Если точки не равноудалены, метод ничего не делает. Кроме того, начало и конец многоугольника не проверяются вместе, поэтому, если прямая линия сформирована поперек начала / конца многоугольника, останется слишком много одной точки.
Метод ShadowMan лучше в том смысле, что расстояния не должны быть идентичными, а линия, проходящая через начало / конец многоугольника, обрабатывается правильно. Однако он также использует сравнения равенства с плавающей запятой, которые не будут работать в целом. Только с целочисленными координатами этот метод будет работать правильно. Кроме того, он использует vecnorm (что делает квадратный корень) и деление, оба являются относительно дорогими операциями (по сравнению с методом, показанным здесь).
Чтобы увидеть, образуют ли три точки прямую линию, можно использовать простое арифметическое правило. Допустим, у нас есть точки p0, p1 и p2. Вектор от p0 до p1 и вектор от p0 до p2 образуют основу параллелограмма, площадь которого может быть вычислена путем перекрестного произведения двух векторов (в 2D Под перекрестным произведением понимается использование z=0, а результирующий вектор, имеющий x=0 и y=0, является полезным только значение z; таким образом, двумерное перекрестное произведение, которое мы предполагаем для получения скалярного значения). Его можно вычислить следующим образом:
v1 = p1 - p0;
v2 = p2 - p0;
x = v1(1)*v2(2) - v1(2)*v2(1);
x, перекрестное произведение, будет равно нулю, если два вектора параллельны, что означает, что эти три точки коллинеарны. Но тест на равенство 0 должен иметь некоторый допуск, поскольку арифметика с плавающей точкой является неточной. Я использую 1е-6 в качестве допуска здесь. Используйте значение, которое на несколько порядков меньше расстояния между вашими точками.
Учитывая входной набор точек p, мы можем найти угловые точки с помощью:
p1 = p; % point 1
p0 = circshift(p1,1); % point 0
v1 = p1 - p0; % vector from point 0 to 1
v2 = circshift(p1,-1) - p0; % vector from point 0 to 2
x = v1(:,1).*v2(:,2) - v1(:,2).*v2(:,1); % cross product
idx = abs(x) > 1e-6; % comparison with tolerance
p = p(idx,:); % corner points
Обратите внимание, что этот тест перекрестного произведения не пройден, если две последовательные точки имеют одинаковые координаты (то есть один из векторов имеет нулевую длину). Дополнительный тест был бы необходим, если бы данные могли иметь дублированные точки.
Вот результаты трех методов. Я создал многоугольник с нетривиальными координатами и неравномерно расположенными вершинами. Я также поместил начальный / конечный промежуток в середине прямого края. Эти характеристики имеют целью показать недостатки двух других методов.
Это код, который я использовал для построения графика:
% Make a polygon that will be difficult for the other two methods
p = [0,0 ; 0.5,0 ; 1,0 ; 1,1 ; 0.5,1 ; 0,1];
p = p + rand(size(p))/3;
p(end+1,:) = p(1,:);
q = [];
for ii = 1:size(p,1)-1
t = p(ii,:) + (p(ii+1,:) - p(ii,:)) .* [0;0.1;1/3;0.45;0.5897545;pi/4;exp(1)/3];
q = [q;t];
end
q = circshift(q,3,1);
figure
subplot(2,2,1)
plot(q(:,1),q(:,2),'bo-')
axis equal
title('input')
subplot(2,2,2)
res1 = method1(q);
plot(res1(:,1),res1(:,2),'ro-')
axis equal
title('Durkee''s method')
subplot(2,2,3)
res2 = method2(q);
plot(res2(:,1),res2(:,2),'ro-')
axis equal
title('ShadowMan''s method')
subplot(2,2,4)
res3 = method3(q);
plot(res3(:,1),res3(:,2),'go-')
axis equal
title('correct method')
% Durkee's method: https://stackoverflow.com/a/55603145/7328782
function P = method1(P)
a = logical([1 diff(P(:,1),2)' 1]);
b = logical([1 diff(P(:,2),2)' 1]);
idx = or(a,b);
P = P(idx,:);
end
% ShadowMan's method: https://stackoverflow.com/a/55603040/7328782
function corners = method2(poly0)
poly0Z = circshift(poly0,1);
poly0I = circshift(poly0,-1);
unitVectIn =(poly0 - poly0I)./vecnorm((poly0 - poly0I),2,2);
unitVectOut =(poly0Z - poly0)./vecnorm((poly0Z - poly0),2,2);
cornerIndices = sum(unitVectIn == unitVectOut,2)==0;
corners = poly0(cornerIndices,:);
end
% vecnorm is new to R2017b, I'm still running R2017a.
function p = vecnorm(p,n,d)
% n is always 2
p = sqrt(sum(p.^2,d));
end
function p = method3(p1)
p0 = circshift(p1,1);
v1 = p1 - p0;
v2 = circshift(p1,-1) - p0;
x = v1(:,1).*v2(:,2) - v1(:,2).*v2(:,1);
idx = abs(x) > 1e-6;
p = p1(idx,:);
end