PCL 1.14.1中2D凸Hull因点顺序导致Qhull崩溃问题求助

问题背景 #

使用PCL 1.14.1的ConvexHull类对4个点计算2D凸包时，程序运行结果完全依赖点的输入顺序：按某一顺序输入会触发Qhull的精度错误崩溃，更换顺序则正常运行。

崩溃场景代码 #

PointCloud<PointXYZ>::Ptr bbox_ptr(new PointCloud<PointXYZ>);
bbox_ptr->push_back(PointXYZ(0,0,0));
bbox_ptr->push_back(PointXYZ(5939,5939,0));
bbox_ptr->push_back(PointXYZ(0,12000,0));
bbox_ptr->push_back(PointXYZ(0,6000,0));
ConvexHull<PointXYZ> hull;
hull.setInputCloud(bbox_ptr);
hull.setDimension(2);
vector<Vertices> polygons;
PointCloud<PointXYZ>::Ptr surface_hull (new PointCloud<PointXYZ>);
hull.reconstruct(*surface_hull, polygons);

错误输出 #

QH6154 Qhull精度错误：初始单纯形是扁平的（面1与内部点共面）
执行命令：| qhull 
Qhull 2015.2.r 2016/01/18所选选项：
  run-id 2049545305  _pre-merge  _zero-centrum  _max-width 1.2e+04
  Error-roundoff 8e-12  _one-merge 4e-11  _near-inside 2e-10
  Visible-distance 1.6e-11  U-coplanar-distance 1.6e-11  Width-outside 3.2e-11
  _wide-facet 9.7e-11

精度问题（除非使用'Q0'或报错否则已修正）
      2个翻转的面

输入Qhull的点云似乎维度低于2，或计算溢出。

Qhull无法从以下点构建明确的凸单纯形：
- p1(v2): 5.9e+03     0
- p2(v1): 1.2e+04     0
- p0(v0):     0     0

中心点与一个面共面，或一个顶点与相邻面共面。计算距离的最大舍入误差为8e-12。中心点、面及到中心点的距离如下：

center point     5980        0

facet p2 p0 distance=    0
facet p1 p0 distance=    0
facet p1 p2 distance=    0

这些点要么具有最大或最小x坐标，要么最大化k坐标的行列式。试验点首先从最大化某一坐标的点中选择。

各维度的最小和最大坐标：
  0:         0   1.2e+04  difference= 1.2e+04
  1:         0         0  difference=    0

如果输入应为全维度，您有以下几种可能确定初始单纯形的选项：
  - 使用'QJ'来扰动输入使其成为全维度
  - 使用'QbB'将点缩放到单位立方体
  - 使用'QR0'随机旋转输入以获取不同的最大点
  - 使用'Qs'搜索所有点以寻找初始单纯形
  - 使用'En'指定小于8e-12的最大舍入误差
  - 使用'T3'跟踪执行以查看每个点的行列式

如果输入是低维度的：
  - 使用'QJ'来扰动输入使其成为全维度
  - 使用'Qbk:0Bk:0'从输入中删除坐标k。您应选择范围最小的坐标。凸包将具有正确的拓扑结构。
  - 确定包含点的平面，将点旋转到坐标平面，并删除其他坐标。
  - 添加一个或多个点使输入成为全维度。
[pcl::ConvexHull::performReconstrution2D] ERROR: qhull was unable to compute a convex hull for the given point cloud (4)!

正常运行场景代码 #

PointCloud<PointXYZ>::Ptr bbox_ptr(new PointCloud<PointXYZ>);    
bbox_ptr->push_back(PointXYZ(5939,5939,0));
bbox_ptr->push_back(PointXYZ(0,12000,0));
bbox_ptr->push_back(PointXYZ(0,6000,0));
bbox_ptr->push_back(PointXYZ(0,0,0));
ConvexHull<PointXYZ> hull;
hull.setInputCloud(bbox_ptr);
hull.setDimension(2);
vector<Vertices> polygons;
PointCloud<PointXYZ>::Ptr surface_hull (new PointCloud<PointXYZ>);
hull.reconstruct(*surface_hull, polygons);

根本原因 #

PCL的ConvexHull底层依赖Qhull库实现。当调用setDimension(2)时，Qhull会自动选择点云中方差最大的两个维度来构建2D凸包。

在崩溃的输入顺序中，Qhull初始化时误选了x轴和z轴作为计算维度——但所有点的z坐标均为0，导致所选的2D空间实际退化为1维直线。此时Qhull无法构建有效的初始单纯形（2D下需要三个不共线的点），因此触发精度错误。

更换输入顺序后，Qhull的维度选择逻辑选中了x轴和y轴（这两个维度的方差远大于z轴），因此能正常构建凸包。

解决方案 #

1. 使用2D点类型明确维度 #

直接使用PointXY类型代替PointXYZ，从根源上避免维度选择歧义：

PointCloud<PointXY>::Ptr bbox_ptr(new PointCloud<PointXY>);
bbox_ptr->push_back(PointXY(0,0));
bbox_ptr->push_back(PointXY(5939,5939));
bbox_ptr->push_back(PointXY(0,12000));
bbox_ptr->push_back(PointXY(0,6000));
ConvexHull<PointXY> hull;
hull.setInputCloud(bbox_ptr);
vector<Vertices> polygons;
PointCloud<PointXY>::Ptr surface_hull (new PointCloud<PointXY>);
hull.reconstruct(*surface_hull, polygons);

2. 给Qhull添加扰动参数 #

根据错误提示，添加QJ参数轻微扰动点坐标，避免退化的维度选择：

ConvexHull<PointXYZ> hull;
hull.setInputCloud(bbox_ptr);
hull.setDimension(2);
// 启用Qhull的扰动选项，解决退化问题
hull.setQhullOptions("QJ");
vector<Vertices> polygons;
PointCloud<PointXYZ>::Ptr surface_hull (new PointCloud<PointXYZ>);
hull.reconstruct(*surface_hull, polygons);

3. 手动投影到目标平面 #

如果必须使用PointXYZ，可以手动将点投影到xy平面（或目标平面），确保Qhull选择正确的维度：

// 手动构造仅保留xy坐标的点云
PointCloud<PointXYZ>::Ptr proj_cloud(new PointCloud<PointXYZ>);
for (const auto& p : *bbox_ptr) {
    proj_cloud->push_back(PointXYZ(p.x, p.y, 0.0));
}
ConvexHull<PointXYZ> hull;
hull.setInputCloud(proj_cloud);
hull.setDimension(2);
vector<Vertices> polygons;
PointCloud<PointXYZ>::Ptr surface_hull (new PointCloud<PointXYZ>);
hull.reconstruct(*surface_hull, polygons);

内容的提问来源于stack exchange，提问作者Mony Chen