Удаление дубликатов трехмерных точек в векторе в С++
Я имею дело с облаком точек, т.е. вектором точек, в результате вычисления, который содержит повторяющиеся точки (до 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
Так уникален ли он не работает должным образом или есть ошибка в моем равном состоянии?
Сами точки также содержат нормальные координаты, но они не важны для отбраковки, поэтому я не использовал их в коде.
Ответы
Ответ 1
std::unique
ничего не удаляет, он только перемещает элементы и возвращает итератор "за конец" уникального интервала в модифицированной коллекции.
(Фактическое содержимое коллекции после возвращаемого итератора не указано.)
Вам нужно явно удалить дубликаты:
std::sort(points.begin(), points.end(), comparePoint);
auto unique_end = std::unique(points.begin(), points.end(), equalPoint);
points.erase(unique_end, points.end());
Вам также нужно быть осторожным в сравнении с плавающей запятой.
Ответ 2
Ваша проблема в том, что сравнение чисел с плавающей запятой для равенства всегда является сложным упражнением. Вероятно, вы обнаружите, что ваши очки (например) на самом деле:
1.965100000001 108.77433 2350.9841
1.965099999999 108.77433 2350.9841
... и они не равны.
Если вы хотите рассматривать точки как "равные", если они находятся в пределах 0,00001 друг от друга, возникает проблема, что ваше условие "равенства" не является транзитивным. (0,0000,0,0) "близко" к (0,000009999,0,0) и (-0,00009999,0,0), но эти последние два пункта "далеки" друг от друга. Это трудная проблема для решения в целом. Удачи!
Если вы знаете что-то о значениях координат (например, что они находятся в миллиметрах, а значения точны до 100 нанометров), вы можете округлить до ближайших 100 нм и хранить дольше. Итак:
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 + уникальный (+ erase), должен работать.
Ответ 3
Чтобы стереть дубликаты: вы можете сделать:
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. Компьютеры не отображают идеально реальные числа с плавающей запятой, результат этого факта выражается в усечении, округлении.