PCD点云排序和分割

请教点云问题，在对建筑物点云投影到水平面并进行轮廓提取后，点云如下图所示，点云格式为pcd，同时可注意到pcd点云内部默认的排序方式是无序的，现在我想把下面这个点云按照下面两种方式操作，如您能实现其中一个操作也请不吝赐教，必有偿感谢：
示例点云在下面网盘链接中
链接：https://pan.baidu.com/s/1N-s6VMrTxF-h5M2Wm9TJ5w?pwd=jo35
提取码：jo35
--来自百度网盘超级会员V2的分享

原始点云：__

1. 从其中某一个点开始，把点云顺序按照顺时针或逆时针进行排列__

2. 对点云进行分割，分割成上下左右四个部分，分割是是以右上、右下、左上、左下四个点为边界__

本例的点云仅为示例，希望能找到对方形（操作1和2）、圆形建筑（操作1）等都适用的算法，最好是用C++/PCL实现，其他语言也可以，十分感谢。

随机采样一致性球模型和平面模型
分割平面平面模型分割基于随机采样一致性
圆柱体分割　依据法线信息分割平面上按　圆柱体模型分割得到圆柱体点云
欧氏距离分割平面模型分割平面　平面上按　聚类得到　多个点云团
基于法线差值和曲率差值的区域聚类分割算法
基于颜色的　区域聚类分割算法 pcl::RegionGrowingRGB

PCL（Point Cloud Library）是一个常用的点云处理库，它提供了丰富的点云处理算法和工具。在PCL中，点云排序和分割也是常见的操作。

PCL点云排序可以使用pcl::PointCloud类中的sort函数进行实现，该函数可以按照点的坐标、距离等属性进行排序。例如，可以按照点到原点的距离进行排序：

pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);
// 加载点云数据
pcl::io::loadPCDFile<pcl::PointXYZ> ("cloud.pcd", *cloud);
// 按照点到原点的距离进行排序
std::sort(cloud->points.begin(), cloud->points.end(), [](const pcl::PointXYZ& a, const pcl::PointXYZ& b){
    return std::sqrt(a.x*a.x + a.y*a.y + a.z*a.z) < std::sqrt(b.x*b.x + b.y*b.y + b.z*b.z);
});

PCL点云分割可以使用PCL中的各种分割算法进行实现，常见的分割算法包括基于平面模型的分割、基于聚类的分割等。例如，可以使用基于平面模型的分割算法将点云分割成平面和非平面两部分：

pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);
// 加载点云数据
pcl::io::loadPCDFile<pcl::PointXYZ> ("cloud.pcd", *cloud);
// 创建分割对象
pcl::SACSegmentation<pcl::PointXYZ> seg;
seg.setOptimizeCoefficients (true);
seg.setModelType (pcl::SACMODEL_PLANE);
seg.setMethodType (pcl::SAC_RANSAC);
seg.setMaxIterations (1000);
seg.setDistanceThreshold (0.01);
// 执行分割
pcl::ModelCoefficients::Ptr coefficients (new pcl::ModelCoefficients);
pcl::PointIndices::Ptr inliers (new pcl::PointIndices);
seg.setInputCloud (cloud);
seg.segment (*inliers, *coefficients);
// 提取平面和非平面两部分点云
pcl::ExtractIndices<pcl::PointXYZ> extract;
pcl::PointCloud<pcl::PointXYZ>::Ptr plane_cloud (new pcl::PointCloud<pcl::PointXYZ>);
extract.setInputCloud (cloud);
extract.setIndices (inliers);
extract.setNegative (false);
extract.filter (*plane_cloud);
pcl::PointCloud<pcl::PointXYZ>::Ptr nonplane_cloud (new pcl::PointCloud<pcl::PointXYZ>);
extract.setNegative (true);
extract.filter (*nonplane_cloud);

答：
       对于要求1，可以使用点云库（例如PCL）中的pcl::PointCloud类的Ptr指针作为输入，然后使用pcl::io::savePCDFileASCII()函数将排序后的点云保存为PCD文件。具体的排序方法可以参考：
1、选择一个起始点，假设为(x,y,z)。
2、计算所有点到(x,y,z)的向量的叉乘值，即(x2-x1, y2-y1, z2-z1) 叉乘 (x3-x1, y3-y1, z3-z1)，其中(x1,y1,z1)是起始点，(x2,y2,z2)是第一个点，(x3,y3,z3)是第二个点。
3、将叉乘值作为点云的排序字段进行排序，可以使用pcl::PointCloud类的sortByFieldName()函数进行排序。
4、从排序后的点云中选择一个点作为新的起始点，重复步骤2和3，直到达到要求数量的排序点云。
     对于要求2，可以使用PCL中的pcl::VoxelGrid类对点云进行下采样，然后根据下采样后点云的边界框计算四边形的顶点坐标，最后使用pcl::PolygonMesh类构造一个四面体模型，并将其与原始点云进行相交运算，将四面体内部的部分与原始点云相减即可得到分割后的四个部分。具体的实现步骤可以参考以下部分代码思路：

// 加载点云数据  
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);  
pcl::io::loadPCDFile<pcl::PointXYZ>("input.pcd", *cloud);  
  
// 对点云进行下采样  
pcl::VoxelGrid<pcl::PointXYZ> sor;  
sor.setInputCloud(cloud);  
sor.setLeafSize(0.01f, 0.01f, 0.01f);  
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_downsampled(new pcl::PointCloud<pcl::PointXYZ>);  
sor.filter(*cloud_downsampled);  
  
// 计算四边形的顶点坐标  
std::vector<int> indices; // 下采样后点云的边界框顶点索引  
std::vector<float> min_bounds, max_bounds; // 下采样后点云的边界框最小和最大坐标值  
cloud_downsampled->getBounds(min_bounds[0], min_bounds[1], min_bounds[2], max_bounds[0], max_bounds[1], max_bounds[2]);  
float dx = (max_bounds[0] - min_bounds[0]) / 4.0f;  
float dy = (max_bounds[1] - min_bounds[1]) / 4.0f;  
float dz = (max_bounds[2] - min_bounds[2]) / 4.0f;  
float x1 = min_bounds[0] - dx;  
float y1 = min_bounds[1] - dy;  
float z1 = min_bounds[2] - dz;  
float x2 = max_bounds[0] + dx;  
float y2 = min_bounds[1] - dy;  
float z2 = min_bounds[2] - dz;  
float x3 = max_bounds[0] + dx;  
float y3 = max_bounds[1] + dy;  
float z3 = min_bounds[2] - dz;  
float x4 = min_bounds[0] - dx;  
float y4 = max_bounds[1] + dy;  
float z4 = min_bounds[2] - dz;  
int index1 = cloud_downsampled->points.size() - 1;  
int index2 = 0;  
#未完待续

可以借鉴下

 欧式聚类分割（聚类）
聚类方法，通过特征空间确定点与点之间的亲疏程度

算法流程：

找到空间中某点p，有kdTree找到离他最近的n个点，判断这n个点到p的距离。将距离小于阈值r的点p1,p2,p3... 放在类Q里
在 Q里找到一点p1,重复1，找到p22,p23,p24 全部放进Q里
当 Q 再也不能有新点加入了，则完成搜索了


pcl::EuclideanClusterExtraction<pcl::Point XYZ> ec;
ec.setClusterTolerance (0.02); ec.setMinCl
usterSize (100);
ec.setMaxClusterSize (25000); ec.setSearchMethod (tree); ec.setInputCloud (cloud_filtered); ec.extract (cluster_indices);
使用类pcl::ConditionEuclideanClustering实现点云分割，与其他分割方法不同的是该方法的聚类约束条件（欧式距离、平滑度、RGB颜色等）可以由用户自己定义，即当搜索到一个近邻点时，用户可以自定义该邻域点是否合并到当前聚类的条件。

pcl::ConditionalEuclideanClustering<PointTypeFull> cec (true);//创建条件聚类分割对象，并进行初始化。cec.setInputCloud (cloud_with_normals);//设置输入点集
//用于选择不同条件函数
switch(Method)
{
case 1:
cec.setConditionFunction (&enforceIntensitySimilarity); break;
case 2:
cec.setConditionFunction (&enforceCurvatureOrIntensitySimilarity); break;
case 3:
cec.setConditionFunction (&customRegionGrowing); break;
default:
cec.setConditionFunction (&customRegionGrowing); break;
 
}
cec.setClusterTolerance (500.0);//设置聚类参考点的搜索距离
cec.setMinClusterSize (cloud_with_normals->points.size () / 1000);//设置过小聚类的标准cec.setMaxClusterSize (cloud_with_normals->points.size () / 5);//设置过大聚类的标准cec.segment (*clusters);//获取聚类的结果，分割结果保存在点云索引的向量中
cec.getRemovedClusters (small_clusters, large_clusters);//获取无效尺寸的聚类

这个条件的设置是可以由我们自定义的，因为除了距离检查，聚类的点还需要满足一个特殊的自定义的要 求，就是以第一个点为标准作为种子点，候选其周边的点作为它的对比或者比较的对象，如果满足条件就加入到聚类的对象中。

//如果此函数返回true，则将添加候选点到种子点的簇类中。 
bool customCondition(const pcl::PointXYZ& seedPoint, const pcl::PointXYZ& candidatePoin t, float squaredDistance) {
 
        // 在这里你可以添加你自定义的条件 
        return false; 
        return true;
}
区域生长算法（聚类）
区域生长算法： 将具有相似性的点云集合起来构成区域。
首先对每个需要分割的区域找出一个种子点作为生长的起点，然后将种子点周围邻域中与种子有相同或相似性质的点合并到种子像素所在的区域中。而新的点继续作为种子向四周生长，直到再没有满足条件 的像素可以包括进来，一个区域就生长而成了。

算法流程：

计算 法线normal 和 曲率curvatures，依据曲率升序排序；
选择曲率最低的为初始种子点，种子周围的临近点和种子点云相比较；
法线的方向是否足够相近（法线夹角足够 r p y）， 法线夹角阈值；
曲率是否足够小（表面处在同一个弯曲程度），区域差值阈值；
如果满足2，3则该点可用做种子点;
如果只满足2，则归类而不做种子;


 算法是针对小曲率变化面设计的，尤其适合对连续阶梯平面进行分割。

//区域增长聚类分割对象    < 点 ， 法 线 > 
pcl::RegionGrowing<pcl::PointXYZ, pcl::Normal> reg; 
reg.setMinClusterSize (50);    //最小的聚类的点数
reg.setMaxClusterSize (1000000);//最大的聚类的点数
reg.setSearchMethod (tree);    //搜索方式
reg.setNumberOfNeighbours (30); //设置搜索的邻域点的个数
reg.setInputCloud (cloud);    //输入点
//reg.setIndices (indices); 
reg.setInputNormals (normals);    //输入的法线
reg.setSmoothnessThreshold (3.0 / 180.0 * M_PI);//设置平滑度 法线差值阈值
reg.setCurvatureThreshold (1.0);    //设置曲率的阀值
基于颜色的区域生长分割（聚类）
基于颜色的区域生长分割

基于颜色的区域生长分割原理上和基于曲率，法线的分割方法是一致的，只不过比较目标换成了颜色。可以认为，同一个颜色且挨得近，是一类的可能性很大，比较适合用于室内场景分割。尤其是复杂室内场景，颜色分割可以轻松的将连续的场景点云变成不同的物体。哪怕是高低不平的地面，设法用采样一致分割器抽掉平面，颜色分割算法对不同的颜色的物体实现分割。



算法主要分为两步：

分割，当前种子点和领域点之间色差小于色差阀值的视为一个聚类。
合并，聚类之间的色差小于色差阀值和并为一个聚类，且当前聚类中点的数量小于聚类点数量的与最近的聚类合并在一起。
 RBG的距离



//基于颜色的区域生成的对象 
pcl::RegionGrowingRGB<pcl::PointXYZRGB> reg; 
reg.setInputCloud (cloud); 
reg.setIndices (indices); //点云的索引 
reg.setSearchMethod (tree); 
reg.setDistanceThreshold (10);//距离的阀值 
reg.setPointColorThreshold (6);//点与点之间颜色容差 
reg.setRegionColorThreshold (5);//区域之间容差 
reg.setMinClusterSize (600); //设置聚类的大小 
std::vector <pcl::PointIndices> clusters; 
reg.extract (clusters);//
pcl::PointCloud <pcl::PointXYZRGB>::Ptr colored_cloud = reg.getColoredCloud ();
 最小图割的分割
图论中的最小割(min-cut) 广泛应用在网络规划，求解桥问题，图像分割等领域。

最小割算法是图论中的一个概念，其作用是以某种方式，将两个点分开，当然这两个点中间可能是通过无数的点再相连的。 如果要分开最左边的点和最右边的点，红绿两种割法都是可行的， 但是红线跨过了三条线，绿线只跨过了两条。单从跨线数量上来论可以得出绿线这种切割方法更优的结论。但假设线上有不同的权值，那么最优切割则和权值有关了。



 

 http://gfx.cs.princeton.edu/pubs/Golovinskiy_2009_MBS/paper_small.pdf

算法主要思想：

建图：对于给定的点云，算法将包含点云中每一个点的图构造为一组普通顶点和另外两个称为源点和汇点的顶点。每个普通顶点都有边缘，将对应的点与其最近的邻居连接起来。
算法为每条边缘分配权重。有三种不同的权：首先，它将权重分配到云点之间的边缘。这个权重称为平滑成本，由公式计算：


这里dist是点之间的距离。距离点越远，边被切割的可能性就越大。

        3.算法设置数据成本。它包括前景和背景惩罚。第一个是将云点与源顶点连接起来并具有用户定义的常量值的边缘的权重。



 对点云的前景点和背景点进行划分。

// 申明一个Min-cut的聚类对象pcl::MinCutSegmentation<pcl::PointXYZ> clustering; clustering.setInputCloud(cloud);    //设置输入
//创建一个点云，列出所知道的所有属于对象的点
// （前景点）在这里设置聚类对象的中心点（想想是不是可以可以使用鼠标直接选择聚类中心点的方法呢？） pcl::PointCloud<pcl::PointXYZ>::Ptr foregroundPoints(new pcl::PointCloud<pcl::PointXYZ>()); pcl::PointXYZ point;
point.x = 100.0;
point.y = 100.0;
point.z = 100.0;
foregroundPoints->points.push_back(point);
clustering.setForegroundPoints(foregroundPoints);//设置聚类对象的前景点
 
//设置sigma，它影响计算平滑度的成本。它的设置取决于点云之间的间隔（分辨率） clustering.setSigma(0.02);// cet cost = exp(-(dist/cet)^2)
// 设 置 聚 类 对 象 的 半 径 . clustering.setRadius(0.01);// dist2Center / radius
 
//设置需要搜索的临近点的个数，增加这个也就是要增加边界处图的个数
clustering.setNumberOfNeighbours(20);
 
//设置前景点的权重（也就是排除在聚类对象中的点，它是点云之间线的权重，） clustering.setSourceWeight(0.6);
 
 
std::vector <pcl::PointIndices> clusters; clustering.extract(clusters);

基于法线微分的分割
根据不同尺度下法向量特征的差异性，利用pcl::DifferenceOfNormalsEstimation实现点云分割，在处理有较大尺度变化的场景点云分割效果较好，利用不同支撑半径去估算同一点的两个单位法向量，单位法向量的差定义DoN特征

DoN算法：

DoN特征源于观察到基于所给半径估计的表面法向量可以反映曲面的内在几何特征，因此这种分割算法是基于法线估计的，需要计算点云中某一点的法线估计。而通常在计算法线估计的时候都会用到邻域信息，很明显邻域大小的选取会影响法线估计的结果。

而在DoN算法中，邻域选择的大小就被称为support radius。对点云中某一点选取不同的支持半径，即可以得到不同的法线估计，而法线之间的差异，就是是所说的法线差异。



PCL_点云分割_基于法线微分分割

算法流程：

对于输入点云数据中的每一点，利用较大的支撑半径计算法向量；
对于输入点云数据中的每一点，利用较大的支撑半径计算法向量；
对于输入点云数据中的每一点，单位化每一点的法向量差异
过滤所得的向量域（DoN特征向量），分割出目标尺寸对应的点云；
// Create output cloud for DoN results
PointCloud<PointNormal>::Ptr doncloud (new pcl::PointCloud<PointNormal>); copyPointCloud<PointXYZRGB, PointNormal>(*cloud, *doncloud);
 
pcl::DifferenceOfNormalsEstimation<PointXYZRGB, PointNormal, PointNormal> do
n;
don.setInputCloud (cloud); 
don.setNormalScaleLarge (normals_large_scale); 
don.setNormalScaleSmall (normals_small_scale); don.initCompute ();
// Compute DoN 
don.computeFeature (*doncloud);




Difference of Normals as a Multi-Scale Operator in Unorganized Point Clouds

 基于超体素的分割
 超体（super voxel）是一种集合，集合的元素是“体素”。
与体素滤波器中的体类似，其本质是一个个的小方块。与之前提到的所有分割手段不同，超体聚类的目的 并不是分割出某种特定物体，其对点云实施过分割（over segmentation），将场景点云化成很多小块，并 研究每个小块之间的关系。
以八叉树对点云进行划分，获得不同点团之间的邻接关系。与图像相似，点云的邻接关系也有很多，如面 邻接、线邻接、点邻接。

这个算法还是有点复杂的，就算进行排序和分割后，分割相对简单，但是对于非凸多边形也有一定的复杂度。分割的点云有什么实际用途不是特别理解。