在MATLAB中连接随机点而不相交的线

6

我需要帮助解决这个问题。我有随机生成的点(示例见图片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: 输入图像描述

有什么解决办法吗?


2
使用随机点,不能保证一定存在解决方案。 - Tarik
1
@AnderBiguri 我不同意。即使我们无法解决一般情况,仍然可以提出一些实用的方法并证明其有用。 - Shai
1
@Shai,我只是提出了一个观点,以便澄清如何处理没有完美解决方案的情况。 - Tarik
2个回答

9

我认为对于一般情况,想要得出一个解决方案可能会非常困难。但是,如果您的点“分散均匀”,那么有一个非常简单的解决方案。

如果您按照连接该点和点云中心的向量在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]);

此算法在多个点相对于点云中心具有相同角度时将失效。
以下是包含20个随机点的示例:
P = rand(2,50);

enter image description here


4
您可以从我给出的另一个答案中适应代码,用于生成任意边数的随机简单多边形。这里的区别在于您已经选择了点集,因此隐含了您想要的边数(即与唯一点的数量相同)。下面是代码示例:
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]);

enter image description here

需要注意两点:

  • 一些点集(比如你在这里选择的那些)可能没有唯一解。请注意我的代码连接了顶部的4个点,与你连接的方式略有不同。
  • 我使用了 TriRepDelaunayTri 类,这两个类可能会在未来的 MATLAB 版本中被移除,以支持 delaunayTriangulation 类。

这个程序基本上是在Delaunay三角剖分的边缘上找到哈密顿回路吗? - knedlsepp
@knedlsepp 是的。它通过从Delaunay三角剖分(凸包)中修剪三角形来实现,直到得到所需数量的边,这意味着最终将连接所有点。 - gnovice
不错。我刚刚尝试使用这个提交和 d = delaunayTriangulation(P); g = graph(d.edges); C = hamiltonian_cycle(g);,但问题是,对于超过20个节点,它比你的方法需要更长时间。(以秒计算而非毫秒。) - knedlsepp

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接