Как отсортировать математические векторы по строгому слабому порядку для карты?
Я пытаюсь написать std :: map< Vector3D, double>, где коллинеарные (параллельные или антипараллельные) векторы должны использовать один и тот же ключ.
В качестве функции сравнения я использую следующую функцию (с допуском 1e-9 в isEqualEnough ()), которую я создал с помощью Использование (математического) вектора в std :: map
struct Vector3DComparator
{
bool operator() (const Vector3D& lhsIn, const Vector3D& rhsIn) const
{
Vector3D lhs = lhsIn.absolute(); // make all members positive
Vector3D rhs = rhsIn.absolute();
if ((lhs.z < rhs.z))
return true;
if ((isEqualEnough(lhs.z, rhs.z))
&& (lhs.y < rhs.y))
return true;
if ((isEqualEnough(lhs.z, rhs.z))
&& (isEqualEnough(lhs.y, rhs.y))
&& (lhs.x < rhs.x))
return true;
return false;
}
};
Когда я вставляю нормали куба в свою карту, я должен получить 3 разных значения (потому что меня не волнует направление), но я получаю 4:
- x = 1 y = 0 z = 0
- x = 0 y = 1 z = 0
- x = 0 y = 0 z = 1
- x = 0 y = 2.2e-16 z = 1
Функция сравнения почему-то неверна, но всякий раз, когда я пытаюсь это исправить, я получаю утверждение, говорящее мне: «Выражение: недопустимый компаратор».
Кто-нибудь замечает ошибку?
Решение
Математически невозможно использовать допуск с реляционными операторами и привести к строгому слабому упорядочению. Любой тип критерия сходимости не сможет удовлетворить алгоритмы упорядочения и требования к структурам данных. Причина очень проста: несовместимость двух значений с использованием допуска не дает отношение эквивалентности так как это не переходный. Ты можешь иметь almostEqual(a, b) а также almostEqual(b, c) и все еще ~almostEqual(a, c), Попробуйте это используя a=1.0; b=2.0; c=3.0; tolerance=1.5;, Вы можете посмотреть на этот ответ: Плавающая точка == когда-либо в порядке?.
Вы по-прежнему можете определять отношение эквивалентности для поплавков, используя функции усечения, пола, крыши или округления. Давайте определим для примера less3(a, b) если и только если floor(a * 8) < floor(b * 8) предполагая, что a и b являются двоичными числами с плавающей точкой и не являются NAN, и умножения не дают оба одинаковых бесконечных знака; это сравнивает a и b, используя 3 бита точности (0,125 в десятичном виде). Теперь определимся equiv3(a, b) если и только если !less3(a, b) && ~less3(b, a), Можно показать, что eqiv3(a, b) дает соответствующее отношение эквивалентности. поскольку less3 это отношение порядка и equiv3 отношение эквивалентности, то less3 строгий слабый порядок на поплавках (исключая NAN). Кроме того, в случае a * 8 == +INF && b * 8 == +INF || a * 8 == -INF && b * 8 == -INF вы можете отступить с обычным < оператор на поплавках.
Другие решения
Комбинируя ответ от Жюльена Виллемюра-Фрешетта со ссылкой, размещенной @alterigel, я сделал свою функцию сравнения:
struct Vector3DComparator
{
bool operator() (const Vector3D& lhsIn, const Vector3D& rhsIn) const
{
int p = 100000; // precision factor
Vector3D lhs = lhsIn.absolute(); // make all members positive
Vector3D rhs = rhsIn.absolute();
auto lhsTied = std::tie((int)(lhs.x * p), (int)(lhs.y * p), (int)(lhs.z * p));
auto rhsTied = std::tie((int)(rhs.x * p), (int)(rhs.y * p), (int)(rhs.z * p));
return lhsTied < rhsTied;
}
};
Обратите внимание: этот код содержит плохой стиль, такой как приведение в стиле c, неправильное именование и многое другое. Мои функции и классы отличаются от тех, которые размещены здесь. Я просто убрал все, чтобы было легче понять.
РЕДАКТИРОВАТЬ:
Я заметил еще две ошибки:
Первое: это не всегда работает для почти одинаковых векторов.
Основываясь на последнем комментарии @tetorea к моему вопросу, я изменил функцию, чтобы всегда сравнивать очень похожие значения. Я использую скалярное произведение для этого, поскольку оно равно ± 1 (или, по крайней мере, близко к) для параллельных векторов.
Второе: .absolute () не работал, потому что с этой функцией два вектора (-1,1,0) и (1,1,0) считались параллельными, что явно не так.
В приведенном ниже коде вы можете найти исправленную версию:
struct Vector3DComparator
{
bool operator() (const Vector3D& lhs, const Vector3D& rhs) const
{
if (isEqualEnough(fabs(lhs * rhs), 1.0)) // dot product
return false;
int p = 100000; // precision factor
auto lhsTied = std::tie((int)(lhs.x * p), (int)(lhs.y * p), (int)(lhs.z * p));
auto rhsTied = std::tie((int)(rhs.x * p), (int)(rhs.y * p), (int)(rhs.z * p));
return lhsTied < rhsTied;
}
};