如何有效地找到离散点集的顺序？

Question

我在一个平面上有一系列离散的点，但是它们的顺序是分散的。这是一个例子：

为了用平滑的曲线将它们连接起来，我写了一个findSmoothBoundary()来实现平滑的边界。

代码

    function findSmoothBoundary(boundaryPointSet)
        %initialize the current point
        currentP = boundaryPointSet(1,:);
        
        %Create a space smoothPointsSet  to store the point
        smoothPointsSet = NaN*ones(length(boundaryPointSet),2);
        %delete the current point from the boundaryPointSet
        boundaryPointSet(1,:) = [];
        ptsNum = 1; %record the number of smoothPointsSet
        
        smoothPointsSet(ptsNum,:) = currentP;

        while ~isempty(boundaryPointSet)
            %ultilize the built-in knnsearch() to 
            %achieve the nearest point of current point
            nearestPidx = knnsearch(boundaryPointSet,currentP);
            currentP = boundaryPointSet(nearestPidx,:);
            ptsNum = ptsNum + 1;
            smoothPointsSet(ptsNum,:) = currentP;
            %delete the nearest point from boundaryPointSet
            boundaryPointSet(nearestPidx,:) = [];
        end
        %visualize the smooth boundary
        plot(smoothPointsSet(:,1),smoothPointsSet(:,2))
        axis equal
    end

虽然findSmoothBoundary()可以正确找到光滑的边界，但是效率要低很多（关于数据，请参见 here)

所以我想知道：

如何高效求离散点阶数？

数据

theta = linspace(0,2*pi,1000)';
boundaryPointSet= [2*sin(theta),cos(theta)];

tic;
findSmoothBoundary(boundaryPointSet)
toc;

%Elapsed time is 4.570719 seconds.

Answer 1

这个答案并不完美，因为我必须做出一些假设才能使其有效。但是，对于绝大多数情况，它应该按预期工作。此外，从您在评论中给出的link，我认为这些假设至少是弱的，如果没有通过定义验证的话：

1.点形成单个连通区域

2。您的点的质心位于这些点的凸包中

如果这些假设得到尊重，您可以执行以下操作（最后提供完整代码）：

第 1 步：计算点的质心

Means=mean(boundaryPointSet);

步骤 2：更改变量以将原点设置为质心

boundaryPointSet(:,1)=boundaryPointSet(:,1)-Means(1);
boundaryPointSet(:,2)=boundaryPointSet(:,2)-Means(2);

Step3 : 将坐标转换为极坐标

[Angles,Radius]=cart2pol(boundaryPointSet(:,1),boundaryPointSet(:,2));

Step4 : 对 Angle 进行排序，并使用此排序对 Radius

进行排序

[newAngles,ids]=sort(Angles);
newRadius=Radius(ids);

Step5 :回到笛卡尔坐标系重新添加质心坐标:

[X,Y]=pol2cart(newAngles,newRadius);
X=X+Means(1);
Y=Y+means(2);

完整代码

%%% Find smooth boundary
fid=fopen('SmoothBoundary.txt');
A=textscan(fid,'%f %f','delimiter',',');

boundaryPointSet=cell2mat(A);

boundaryPointSet(any(isnan(boundaryPointSet),2),:)=[];

idx=randperm(size(boundaryPointSet,1));

boundaryPointSet=boundaryPointSet(idx,:);

tic

plot(boundaryPointSet(:,1),boundaryPointSet(:,2))

%% Find mean value of all parameters

Means=mean(boundaryPointSet);

%% Center values around Mean point

boundaryPointSet(:,1)=boundaryPointSet(:,1)-Means(1);
boundaryPointSet(:,2)=boundaryPointSet(:,2)-Means(2);

%% Get polar coordinates of your points

[Angles,Radius]=cart2pol(boundaryPointSet(:,1),boundaryPointSet(:,2));

[newAngles,ids]=sort(Angles);
newRadius=Radius(ids);

[X,Y]=pol2cart(newAngles,newRadius);
X=X+Means(1);
Y=Y+means(2);    
toc

figure

plot(X,Y);

注意：由于您的值已经在输入文件中排序，我不得不通过排列它们来弄乱它

输出：

Boundary

Elapsed time is 0.131808 seconds.

乱码输入：

输出：

如何有效地找到离散点集的顺序？

How to find the order of discrete point-set efficiently?

performance

matlab

boundary

nearest-neighbor

代码

数据

完整代码

输出：