Condense a set of points of a polygon into a shorter set of points

Question

I have the following polygon which is just a set of 2D points as follows:-

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];

Now I can plot it using.

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

This clearly shows one thing that my original set of polygon points is highly redundant. Basically, multiple points lying on the same straight line are enumerated above which is not needed. I could start checking each pair of points and if they are on the same straight line I could remove them. But that would mean using many for loops. I cannot come up with a smart vectorized way.

How do I get a new set of points which is much shorter in size than the previous but which still represents the exact same polygon? I should only have as many points as there are vertices in the polygon. So in other words how to find the vertices from the above data set in a quick way?

PS: Here the vertex angles are 90 degrees, but if you give a solution don't try to exploit that fact. I want a more general answer.

Answer 1

现有的两个答案有很大的缺点：

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

• ShadowMan的方法更好，因为距离不必相同，并且正确处理了多边形起点/终点的线。但是，它也使用浮点相等比较，通常无法正常工作。只有使用整数坐标，此方法才能正常工作。此外，它使用vecnorm（做平方根）和除法（相对于此处显示的方法而言）都是相对昂贵的操作。

要查看三个点是否形成一条直线，可以使用简单的算术规则。假设我们有点p0，p1和p2。从载体p0到p1和从矢量p0以p2形成平行四边形，其面积可以通过计算的基础的两个向量的叉积（在图2D中，叉积被理解为使用z=0，具有所得到的向量x=0和y=0，只有z值是有用的；因此，我们假设产生一个标量值的2D叉积）。可以如下计算：

v1 = p1 - p0;
v2 = p2 - p0;
x = v1(1)*v2(2) - v1(2)*v2(1);

x如果两个向量平行，则叉积为零，这意味着三个点是共线的。但是，由于浮点算术不精确，因此对于等于0的相等性测试必须具有一定的容差。我在这里使用1e-6作为公差。使用的值比点之间的距离小几个数量级。

给定一组输入点p，我们可以使用以下方法找到角点：

v1 = p1 - p0;
v2 = p2 - p0;
x = v1(1)*v2(2) - v1(2)*v2(1);

请注意，如果两个连续的点具有相同的坐标（即向量之一的长度为零），则该叉积测试将失败。如果数据可能有重复的点，则有必要进行额外的测试。

这是这三种方法的结果。我创建了一个具有非平凡坐标且顶点间距不相等的多边形。我还将开始/结束间隙放在一条直线边缘的中间。这些特性旨在显示其他两种方法的缺点。

这是我用来生成图形的代码：

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