Удаление дубликатов трехмерных точек в векторе в С++

Я имею дело с облаком точек, т.е. вектором точек, в результате вычисления, который содержит повторяющиеся точки (до 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());

Чтобы сравнить числа с плавающей запятой: рассмотрим математические свойства чисел ¹ чисел с плавающей запятой, а также проблемы ² унаследованные их машиной двоичное представление, вы получаете только одно решение при сравнении чисел с плавающей запятой, а именно, сравнивая их с точностью до значения 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. Компьютеры не отображают идеально реальные числа с плавающей запятой, результат этого факта выражается в усечении, округлении.}