0

这是我的第一篇文章，所以请善待。

我有一个具有 3~10 个坐标的矩阵，我想将这些点连接成一个最大尺寸的多边形。

我尝试使用 fill() [1] 生成图，但如何计算该图的面积？有没有办法将绘图转换回矩阵？

你会推荐我什么？

先感谢您！

[1]

x1 = [ 0.0, 0.5, 0.5 ];
y1 = [ 0.5, 0.5, 1.0 ];
填充（x1，y1，'r'）；

[更新]

感谢您对 MatlabDoug 的回答，但我认为我的问题表述得不够清楚。我想连接所有这些点以成为最大尺寸的多边形。

有什么新想法吗？

4

4 回答 4

3 
 x1 = rand(1,10)
 y1 = rand(1,10)

 vi = convhull(x1,y1)
 polyarea(x1(vi),y1(vi))

 fill ( x1(vi), y1(vi), 'r' ); 
 hold on
 plot(x1,y1,'.')
 hold off

这里发生的是 CONVHULL 告诉我们哪些顶点 (vi) 在凸包（包围所有点的最小多边形）上。知道哪些在凸包上，我们向 MATLAB 询问具有 POLYAREA 的区域。

最后，我们使用您的 FILL 命令绘制多边形，然后 PLOT 将点放置在那里进行确认。

于 2009-10-02T15:57:12.580 回答
1

你说你只有 3...10 个点可以连接。在这种情况下，我建议你只取所有可能的组合，用 polyarea 计算面积并取最大的一个。

只有当您的点数增加或者您必须经常计算它以便计算时间很重要时，才值得花一些时间在更好的算法上。但是我认为很难想出一个算法并证明它的完整性。

于 2009-10-06T09:21:09.180 回答
1

我同意 groovingandi 关于尝试所有多边形的建议；您只需要确保检查多边形的有效性（没有自相交等）。

现在，如果你想处理很多点......正如 MatlabDoug 指出的那样，凸包是一个很好的起点。请注意，凸包给出了一个多边形，其面积是可能的最大值。当然，问题在于船体内部可能有一些点不是多边形的一部分。我提出了以下贪心算法，但我不确定它是否能保证最大面积多边形。

其基本思想是从凸包开始作为候选最终多边形，将未使用的点对应的三角形雕刻出来，直到所有点都属于最终多边形。在每个阶段，都会删除可能的最小三角形。

Given: Points P = {p1, ... pN}, convex hull H = {h1, ..., hM}
       where each h is a point that lies on the convex hull.
       H is a subset of P, and it is also ordered such that adjacent
       points in the list of H are edges of the convex hull, and the
       first and last points form an edge.
Let Q = H
while(Q.size < P.size)
    % For each point, compute minimum area triangle
    T = empty heap of triangles with value of their area
    For each P not in Q
        For each edge E of Q
            If triangle formed by P and E does not contain any other point
                Add triangle(P,E) with value area(triangle(P,E))
    % Modify the current polygon Q to carve out the triangle
    Let t=(P,E) be the element of T with minimum area
    Find the ordered pair of points that form the edge E within Q
    (denote them Pa and Pb)
    Replace the pair (Pa,Pb) with (Pa,E,Pb)

现在，实际上您不需要堆用于T，只需将数据附加到四个列表：一个用于 P，一个用于 Pa，一个用于 Pb，一个用于区域。要测试一个点是否在三角形内，您只需要针对形成三角形边的线测试每个点，并且您只需要测试不在 Q 中的点。最后，要计算最终多边形的面积，您可以对其进行三角剖分（就像使用delaunay函数一样，并总结三角剖分中每个三角形的面积），或者您可以找到凸包的面积，并在雕刻出三角形时减去它们的面积。

再说一次，我不知道这个贪心算法是否能保证找到最大面积的多边形，但我认为它应该在大部分时间都有效，而且很有趣。

于 2009-10-06T09:29:10.210 回答
0

正如 Amro 评论的那样，找到正确的分数顺序是困难的部分。这个功能够用吗？

function [idx] = Polyfy(x, y)
% [idx] = Polyfy(x, y)
% Given vectors x and y that contain pairs of points, find the order that
% joins them into a polygon. fill(x(idx),y(idx),'r') should show no holes.

%ensure column vectors
if (size(x,1) == 1)
  x = x';
end
if (size(y,1) == 1)
  y = y';
end

% vectors from centroid of points to each point
vx = x - mean(x);
vy = y - mean(y);
% unit vectors from centroid towards each point
v = (vx + 1i*vy)./abs(vx + 1i*vy);
vx = real(v);
vy = imag(v);

% rotate all unit vectors by first
rot = [vx(1) vy(1) ; -vy(1) vx(1)];
v = (rot*[vx vy]')';

% find angles from first vector to each vector
angles = atan2(v(:,2), v(:,1));
[angles, idx] = sort(angles);
end

这个想法是找到点的质心，然后找到从质心到每个点的向量。您可以将这些向量视为三角形的边。多边形由一组三角形组成，其中每个向量仅用作“左”和“右”一次，并且没有跳过任何向量。这归结为按质心周围的角度对向量进行排序。

我选择通过将向量归一化为单位长度，选择其中一个作为旋转向量，然后旋转其余的来做到这一点。这让我可以简单地使用 atan2 来找到角度。可能有一种更快和/或更优雅的方式来做到这一点，但我对三角身份感到困惑。最后，对这些角度进行排序可为点提供正确的顺序以形成所需的多边形。

这是测试功能：

function [x, y] = TestPolyArea(N)
x = rand(N,1);
y = rand(N,1);
[indexes] = Polyfy(x, y);
x2 = x(indexes);
y2 = y(indexes);
a = polyarea(x2, y2);
disp(num2str(a));
fill(x2, y2, 'r');
hold on
plot(x2, y2, '.');
hold off
end

通过 N = 100 左右可以得到一些非常狂野的图片！

于 2009-10-06T09:05:35.237 回答