matlab - 将多边形的一组点压缩成一组较短的点

Question

我有以下多边形，它只是一组二维点，如下所示:-

poly0=[80    60
    90    60
   100    60
   110    60
   110    50
   120    50
   130    50
   140    50
   150    50
   160    50
   170    50
   180    50
   190    50
   200    50
   210    50
   210    60
   210    70
   210    80
   210    90
   220    90
   220   100
   210   100
   210   110
   200   110
   200   120
   190   120
   180   120
   180   130
   170   130
   160   130
   150   130
   140   130
   130   130
   130   120
   120   120
   110   120
   110   110
   100   110
   100   100
    90   100
    90    90
    90    80
    90    70
    80    70
    80    60];

现在我可以使用它来绘制了。

>> line(poly0(:,1), poly0(:,2),'Color','k','LineWidth',3,'LineStyle',':');

这清楚地表明一件事，即我原来的多边形点集是高度冗余的。基本上，上面列举了位于同一条直线上的多个点，这是不需要的。我可以开始检查每对点，如果它们在同一条直线上，我可以删除它们。但这将意味着使用许多 for 循环。我想不出一个智能矢量化的方式。

我如何获得一组新的点，这些点的尺寸比以前的要小得多，但仍然代表完全相同的多边形？我应该只拥有与多边形中的顶点一样多的点。那么换句话说如何从上述数据集中快速找到顶点呢？

PS:这里的顶角是 90 度，但如果您给出解决方案，请不要试图利用这个事实。我想要一个更笼统的答案。

Answer 1

现有的两个答案都有很大的不足:

• Durkee's method仅当后续点之间的距离完全相同时才有效。点必须具有可以完美表示为浮点值的坐标，以便可以发现一条线上的后续点之间的距离是相同的。如果点不等距，则该方法不执行任何操作。此外，不会同时检查多边形的起点和终点，因此如果在多边形的起点/终点形成一条直线，将保留太多点。

• ShadowMan's method更好的是距离不需要相同，并且正确处理了多边形起点/终点的线。然而，它也使用 float 相等比较，这在一般情况下是行不通的。只有使用整数坐标，此方法才能正常工作。此外，它使用 vecnorm(计算平方根)和除法，两者都是相对昂贵的操作(与此处显示的方法相比)。

要判断三点是否构成一条直线，可以使用一个简单的算术规则。假设我们有点 p0、p1 和 p2。从p0到p1的向量和从p0到p2的向量构成平行四边形的基础，其面积可以通过the cross product of the two vectors计算(在 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 的测试必须有一定的公差，因为浮点运算是不精确的。我在这里使用 1e-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