在没有相交线的情况下连接MATLAB中的随机点

Question

我需要帮助解决这个问题。我有随机生成的点（图片#1 上的示例），我想用线连接它们（图片#2 上的示例）。线不能相交，连接后的点应该看起来像一个不规则的区域。

%Generating random points
xn = randi([3 7],1,10);
yn = randi([3 6],1,10);

%Generated points
xn = [6,3,7,7,6,6,6,4,6,3];
yn = [5,3,4,3,3,6,5,4,6,3];

图片#1：

结果应该是这样的：图片#2：

知道如何解决这个问题吗？

Answer 1

我想对于一般情况来说，想出一个解决方案是非常困难的。但是，假设您的观点是分散的 "nicely"，那么有一个非常简单的解决方案。

如果根据连接点和点云中心的向量的 x 轴上方的角度对点进行排序，则：

P = [xn;yn]; %// group the points as columns in a matrix
c = mean(P,2); %// center point relative to which you compute the angles
d = bsxfun(@minus, P, c ); %// vectors connecting the central point and the dots
th = atan2(d(2,:),d(1,:)); %// angle above x axis
[st si] = sort(th); 
sP = P(:,si); %// sorting the points

仅此而已。绘制结果：

sP = [sP sP(:,1)]; %// add the first point again to close the polygon
figure;plot( sP(1,:), sP(2,:), 'x-');axis([0 10 0 10]);

如果多个点与点云的中心 w.r.t 具有相同角度，则此算法将失败。

一个有20个随机点的例子：

P = rand(2,50);

Answer 2

您可以改编 another answer I gave 中的代码来生成任意边数的随机简单多边形。这里的区别在于您已经选择了一组点，因此隐含了您想要的边数（即与唯一点数相同）。代码如下所示：

xn = [6,3,7,7,6,6,6,4,6,3];  % Sample x points
yn = [5,3,4,3,3,6,5,4,6,3];  % Sample y points
[~, index] = unique([xn.' yn.'], 'rows', 'stable');  % Get the unique pairs of points
x = xn(index).';
y = yn(index).';
numSides = numel(index);
dt = DelaunayTri(x, y);
boundaryEdges = freeBoundary(dt);
numEdges = size(boundaryEdges, 1);

while numEdges ~= numSides
    if numEdges > numSides
        triIndex = vertexAttachments(dt, boundaryEdges(:,1));
        triIndex = triIndex(randperm(numel(triIndex)));
        keep = (cellfun('size', triIndex, 2) ~= 1);
    end
    if (numEdges < numSides) || all(keep)
        triIndex = edgeAttachments(dt, boundaryEdges);
        triIndex = triIndex(randperm(numel(triIndex)));
        triPoints = dt([triIndex{:}], :);
        keep = all(ismember(triPoints, boundaryEdges(:,1)), 2);
    end
    if all(keep)
        warning('Couldn''t achieve desired number of sides!');
        break
    end
    triPoints = dt.Triangulation;
    triPoints(triIndex{find(~keep, 1)}, :) = [];
    dt = TriRep(triPoints, x, y);
    boundaryEdges = freeBoundary(dt);
    numEdges = size(boundaryEdges, 1);
end

boundaryEdges = [boundaryEdges(:,1); boundaryEdges(1,1)];
x = dt.X(boundaryEdges, 1);
y = dt.X(boundaryEdges, 2);

这是生成的多边形：

patch(x,y,'w');
hold on;
plot(x,y,'r*');
axis([0 10 0 10]);

注意两点：

某些点集（例如您在此处选择的点集）将没有唯一解。请注意我的代码如何以与您略有不同的方式连接前 4 个点。
我使用了 TriRep and DelaunayTri classes, both of which may be removed in future MATLAB releases in favor of the delaunayTriangulation class.

在没有相交线的情况下连接MATLAB中的随机点

Connecting random points in MATLAB without intersecting lines

arrays

matlab

geometry

computational-geometry