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

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

为了将它们与平滑曲线连接起来，我编写了一个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.

最佳答案

这个答案并不完美，因为我得做一些假设才能使它起作用然而，在绝大多数情况下，它应该按预期工作此外，从你在评论中给出的链接来看，我认为这些假设至少是薄弱的，如果不能通过定义加以验证的话：
一该点形成单个连接区域
2点的质心位于这些点的凸壳中
如果这些假设得到尊重，您可以执行以下操作（最后提供完整的代码）：
步骤1：计算点的重心

Means=mean(boundaryPointSet);

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

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

步骤3：将坐标转换为极坐标

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

步骤4：对Angle进行排序，并使用此排序对Radius进行排序

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

步骤5：返回笛卡尔坐标，重新添加质心坐标：

[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);

注意：由于您的值已经在您的输入文件中排序，我不得不通过对它们进行置换来把它弄乱
输出：
边界
运行时间为0.131808秒。
输入错误：

输出：