Пересечение сегментов линии (только пересечение, без касания)

Я пытаюсь найти «Пересечение сегментов линии». Поэтому я хочу, чтобы приведенная ниже функция возвращала true только в том случае, если обе линии действительно пересекают друг друга, а не в том случае, если они начинаются/заканчиваются в одних и тех же точках. Из того, что я читал, кажется, что это своего рода «тривиальное» математическое решение, но везде, где это упоминалось, это не было объяснено так, как я мог понять.

Ниже приведена функция, которая правильно определяет пересечение сегментов, включая «касающиеся» точки. Есть ли простой способ изменить его под мои нужды?

Был бы очень признателен за вашу помощь!

inline double Dot(sf::Vector2f a, sf::Vector2f  b) { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(sf::Vector2f a, sf::Vector2f b) { return (a.y*b.x) - (a.x*b.y); }

static bool LineCollision(const sf::Vector2f A1, const sf::Vector2f A2,
    const sf::Vector2f B1, const sf::Vector2f B2,
    double* out = 0)
{
    sf::Vector2f a(A2 - A1);
    sf::Vector2f b(B2 - B1);

    double f = PerpDot(a, b);
    if (!f)      // lines are parallel
        return false;

    sf::Vector2f c(B2 - A2);
    double aa = PerpDot(a, c);
    double bb = PerpDot(b, c);

    if (f < 0)
    {
        if (aa > 0)     return false;
        if (bb > 0)     return false;
        if (aa < f)     return false;
        if (bb < f)     return false;
    }
    else
    {
        if (aa < 0)     return false;
        if (bb < 0)     return false;
        if (aa > f)     return false;
        if (bb > f)     return false;
    }

    if (out)
        *out = 1.0 - (aa / f);
    return true;
}

c++ geometry intersection
person user3808217    schedule 11.06.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Чтобы исключить концы сегментов, измените строгое сравнение < и > во всех внутренних if's на <= и >= следующим образом:

    if (aa >= 0)     return false;
person MBo    schedule 11.06.2017
comment
Я думаю, что сравнение чисел с плавающей запятой на точное равенство не является хорошей идеей - person ivan kuklin; 11.06.2017
comment
@ivan kuklin Если вы имеете в виду сравнение с некоторым допуском - данный алгоритм не способен правильно обрабатывать проблемы числовой стабильности с использованием допусков. Есть специальные геом. алгоритмы преодоления этих проблем (если это важно). - person MBo; 12.06.2017