在 C++ 中删除向量中 3D 点的重复项
Removing duplicates of 3D points in a vector in C++
我正在处理点云,即点向量,作为计算的结果,它包含重复点(最多为点云大小的 10%)。
我的实现是根据 x、y 和 z 值对这些点进行排序,然后使用 std::unique
函数。然而,生成的云仍然包含重复项,即使排序本身似乎有效。
这里是关键代码
bool comparePoint(pcl::PointXYZINormal p1, pcl::PointXYZINormal p2){
if (p1.x != p2.x)
return p1.x > p2.x;
else if (p1.y != p2.y)
return p1.y > p2.y;
else
return p1.z > p2.z;
}
bool equalPoint(pcl::PointXYZINormal p1, pcl::PointXYZINormal p2){
if (p1.x == p2.x && p1.y == p2.y && p1.z == p2.z)
return true;
return false;
}
void KDsearch::cullDuplePoints(){
std::sort(points.begin(), points.end(), comparePoint);
std::unique(points.begin(), points.end(), equalPoint);
}
这里是输出点云(x、y 和 z 坐标)的部分提取:
1.96828 -535.09515 2794.8391
1.96627 -636.95264 2914.0366
1.96627 -636.95264 2914.0366
1.9651 108.77433 2350.9841
1.9651 108.77433 2350.9841
1.9642299 -206.19427 5618.4629
1.9642299 -206.19427 5618.4629
1.96386 -1880.3784 1346.0654
那么是unique没有正常工作还是我的equal条件有误?
点本身也包含法线坐标,但它们对于剔除并不重要,所以我没有在代码中使用它们。
你的问题是比较浮点数是否相等总是一个困难的练习。您可能会发现您的积分实际上是(例如):
1.965100000001 108.77433 2350.9841
1.965099999999 108.77433 2350.9841
...而且它们不相等。
如果你想将点视为 "equal",如果它们在 0.00001 以内,你会遇到你的 "equality" 条件不可传递的问题。 (0.0000,0,0) 是 "close" 到 (0.000009999,0,0) 和 (-0.00009999,0,0),但后两点彼此 "far"。这是一般情况下很难解决的问题。祝你好运!
如果您对坐标值有所了解(例如,它们以毫米为单位,并且值精确到 100 纳米),您可以四舍五入到最接近的 100 纳米,并存储 long long。所以:
struct IntPoint {
const static double ScaleFactor = 10000;
long long x,y,z;
IntPoint(const pcl::PointXYZINormal &p)
: x(llround(p.x*ScaleFactor ))
, y(llround(p.y*ScaleFactor ))
, z(llround(p.z*ScaleFactor ))
{}
};
将您的点云转换为 IntPoint,然后您的排序 + 唯一(+擦除)应该可以工作。
删除重复项:你可以这样做:
sort(point.begin(), point.end());
point.erase(unique(point.begin(), point.end()), point.end());
或者只是创建一个集,根据定义只包含矢量元素中的唯一元素:
std::set<type> all_unique(point.begin(), point.end());
比较浮点数:考虑浮点数的数学性质1,结合问题2 由他们的机器二进制表示继承,在比较浮点数时,您最终只有一个解决方案,即在精度值 epsilon
.
内比较它们
因此,如果您想比较和排序 float x1
和 float x2
,它们是您的坐标,您可以通过以下方式进行:
x1 - x2 < epsilon
其中 epsilon
是您要查找的准确度。在您的情况下,仅供说明,函数 equalPoint()
可以修改为:
bool equalPoint(pcl::PointXYZINormal p1, pcl::PointXYZINormal p2){
// equal up to the third digit after the decimal point
float eps = 0.001;
if ((p1.x -p2.x) < eps && (p1.y - p2.y) < eps && (p1.z - p2.z) < eps)
return true;
return false;
}
1.它们可以有非常小的差异,不像整数,整数是四舍五入的,可以很容易地进行比较。
2。计算机并不能完美地映射真实的浮点数,这一事实的结果以截断、舍入表示。
std::unique
不会删除任何内容,它只会移动元素和 returns 修改集合中唯一间隔的迭代器 "past the end"。
(返回的迭代器之后的集合的实际内容未指定。)
您需要明确删除重复项:
std::sort(points.begin(), points.end(), comparePoint);
auto unique_end = std::unique(points.begin(), points.end(), equalPoint);
points.erase(unique_end, points.end());
您还需要注意浮点比较。
我正在处理点云,即点向量,作为计算的结果,它包含重复点(最多为点云大小的 10%)。
我的实现是根据 x、y 和 z 值对这些点进行排序,然后使用 std::unique
函数。然而,生成的云仍然包含重复项,即使排序本身似乎有效。
这里是关键代码
bool comparePoint(pcl::PointXYZINormal p1, pcl::PointXYZINormal p2){
if (p1.x != p2.x)
return p1.x > p2.x;
else if (p1.y != p2.y)
return p1.y > p2.y;
else
return p1.z > p2.z;
}
bool equalPoint(pcl::PointXYZINormal p1, pcl::PointXYZINormal p2){
if (p1.x == p2.x && p1.y == p2.y && p1.z == p2.z)
return true;
return false;
}
void KDsearch::cullDuplePoints(){
std::sort(points.begin(), points.end(), comparePoint);
std::unique(points.begin(), points.end(), equalPoint);
}
这里是输出点云(x、y 和 z 坐标)的部分提取:
1.96828 -535.09515 2794.8391
1.96627 -636.95264 2914.0366
1.96627 -636.95264 2914.0366
1.9651 108.77433 2350.9841
1.9651 108.77433 2350.9841
1.9642299 -206.19427 5618.4629
1.9642299 -206.19427 5618.4629
1.96386 -1880.3784 1346.0654
那么是unique没有正常工作还是我的equal条件有误?
点本身也包含法线坐标,但它们对于剔除并不重要,所以我没有在代码中使用它们。
你的问题是比较浮点数是否相等总是一个困难的练习。您可能会发现您的积分实际上是(例如):
1.965100000001 108.77433 2350.9841
1.965099999999 108.77433 2350.9841
...而且它们不相等。
如果你想将点视为 "equal",如果它们在 0.00001 以内,你会遇到你的 "equality" 条件不可传递的问题。 (0.0000,0,0) 是 "close" 到 (0.000009999,0,0) 和 (-0.00009999,0,0),但后两点彼此 "far"。这是一般情况下很难解决的问题。祝你好运!
如果您对坐标值有所了解(例如,它们以毫米为单位,并且值精确到 100 纳米),您可以四舍五入到最接近的 100 纳米,并存储 long long。所以:
struct IntPoint {
const static double ScaleFactor = 10000;
long long x,y,z;
IntPoint(const pcl::PointXYZINormal &p)
: x(llround(p.x*ScaleFactor ))
, y(llround(p.y*ScaleFactor ))
, z(llround(p.z*ScaleFactor ))
{}
};
将您的点云转换为 IntPoint,然后您的排序 + 唯一(+擦除)应该可以工作。
删除重复项:你可以这样做:
sort(point.begin(), point.end());
point.erase(unique(point.begin(), point.end()), point.end());
或者只是创建一个集,根据定义只包含矢量元素中的唯一元素:
std::set<type> all_unique(point.begin(), point.end());
比较浮点数:考虑浮点数的数学性质1,结合问题2 由他们的机器二进制表示继承,在比较浮点数时,您最终只有一个解决方案,即在精度值 epsilon
.
因此,如果您想比较和排序 float x1
和 float x2
,它们是您的坐标,您可以通过以下方式进行:
x1 - x2 < epsilon
其中 epsilon
是您要查找的准确度。在您的情况下,仅供说明,函数 equalPoint()
可以修改为:
bool equalPoint(pcl::PointXYZINormal p1, pcl::PointXYZINormal p2){
// equal up to the third digit after the decimal point
float eps = 0.001;
if ((p1.x -p2.x) < eps && (p1.y - p2.y) < eps && (p1.z - p2.z) < eps)
return true;
return false;
}
1.它们可以有非常小的差异,不像整数,整数是四舍五入的,可以很容易地进行比较。
2。计算机并不能完美地映射真实的浮点数,这一事实的结果以截断、舍入表示。
std::unique
不会删除任何内容,它只会移动元素和 returns 修改集合中唯一间隔的迭代器 "past the end"。
(返回的迭代器之后的集合的实际内容未指定。)
您需要明确删除重复项:
std::sort(points.begin(), points.end(), comparePoint);
auto unique_end = std::unique(points.begin(), points.end(), equalPoint);
points.erase(unique_end, points.end());
您还需要注意浮点比较。