Как отсортировать математические векторы по строгому слабому порядку для карты? - PullRequest
Новая
       19

Как отсортировать математические векторы по строгому слабому порядку для карты?

0 голосов
/ 22 ноября 2018

Я пытаюсь написать std :: map , где коллинеарные (параллельные или антипараллельные) векторы должны использовать один и тот же ключ.

В качестве функции сравнения я использую следующую функцию (с допуском 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

Функция сравнения как-то не так, но всякий раз, когда я пытаюсь это исправить, я получаю утверждение, говорящее мне "Выражение: недопустимый компаратор".

Кто-нибудь замечает ошибку?

Ответы [ 2 ]

0 голосов
/ 23 ноября 2018

Объединив ответ от Жюльена Виллемюра-Фрешетта со ссылкой, опубликованной @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;
    }
};
0 голосов
/ 22 ноября 2018

Математически невозможно использовать допуск с реляционными операторами и получить строго слабый порядок.Любой критерий сходимости не сможет удовлетворить алгоритмы упорядочения и требования к структурам данных.Причина очень проста: несовместимость двух значений с использованием допуска не дает отношения эквивалентности , поскольку оно не транзитивно .Вы можете иметь 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 вы можете отступить с помощью обычного оператора

...