std::set пользовательский компаратор для 2D точек

Мне нужен список неповторяющихся 2D-точек, поэтому я использую std::set с пользовательской функцией сравнения. Функция, которую я использую, имеет проблемы после вставки точек, потому что иногда std::find не находит уже вставленные точки.

const double tolerance = 0.1;
struct MyPoint2D
{
  MyPoint2D(double x, double y) : _x(x), _y(y) {}
  double _x, _y;
};
auto compMyPoint2D = [&](const MyPoint2D& pointA, const MyPoint2D& pointB) -> bool
{
  if (pointA._x < pointB._x - tolerance) return true;
  if (pointA._x > pointB._x + tolerance) return false;
  if (pointA._y < pointB._y - tolerance) return true;
  return false;
};
std::set<MyPoint2D, decltype(compMyPoint2D)> orderedMyPoints(compMyPoint2D);
MyPoint2D pointA(0.66,1.14);
MyPoint2D pointB(0.75, 0.0);
MyPoint2D pointC(0.57,1.19);
orderedMyPoints.insert(pointA);
orderedMyPoints.insert(pointB);
orderedMyPoints.insert(pointC);
if (orderedMyPoints.find(pointC)==orderedMyPoints.end())
{
  std::cout << "Not found" << std::endl;
  orderedMyPoints.insert(pointC);
  if (orderedMyPoints.find(pointC)==orderedMyPoints.end())
    std::cout << "Still not found" << std::endl;
}

Нужно ли мне предварительно заказывать 2d-очки перед вставкой в ​​std::set или есть лучшая функция сравнения для 2d-точек?

Мне нужно использовать std::find после вставки всех точек, чтобы получить окончательные индексы точек.

Я использую собственный C++ в Microsoft Visual Studio 2010.


c++ std c++11 stdset
person JordiS    schedule 02.12.2015    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Ваша функция сравнения неверна. Выньте +-толерантность. Это бесполезно при попытке определить абсолютный порядок значений с плавающей запятой. Например, он не обеспечивает транзитивность эквивалентности. То есть, если A == B (т. е. f(A, B) и f(B, A) оба являются ложными) и B == C, то это не обязательно так, что A == C, когда у вас есть эта корректировка допуска.

Просто сделайте это:

if (pointA._x < pointB._x) return true;
if (pointA._x > pointB._x) return false;
if (pointA._y < pointB._y) return true;
return false;
person Benjamin Lindley    schedule 02.12.2015
comment
Спасибо! Моя идея заключалась в том, чтобы использовать std::set для очистки списка точек и получить как одну и ту же точку на две точки ближе, чем допуск (поэтому допуск такой большой, 0,1), но я вижу, что это невозможно сделать с std::set. - person JordiS; 02.12.2015

arrow_upward
3
arrow_downward

Во-первых, если у вас нет причин не делать этого, предпочтительнее просто определить operator< для вашего класса, это означает меньше ввода при использовании std::set и т. д., и означает, что вы можете использовать инфикс <. Во-вторых, как указывает Бенджамин, в tolerance не должно быть необходимости. В-третьих, можно упростить логику сравнения.

У вас должно быть что-то вроде:

bool operator<(const MyPoint2D& lhs, const MyPoint2D& rhs)
{
    return lhs._x < rhs._x || (lhs._x == rhs._x && lhs._y < rhs._y);
}

Тогда вы можете просто использовать std::set<MyPoint2D>.

person Daniel    schedule 02.12.2015
comment
Если A равно {0,1}, а B равно {1,0}, это вернет true как для A < B, так и для B < A, нарушая антисимметрию. - person Benjamin Lindley; 02.12.2015