2 линии пересечения

Question

У меня есть этот код, чтобы узнать состояние 2 линий, есть 3 случая:

1 - линии пересекаются в одной точке

2 - они параллельны

3- особый случай параллели: они идентичны [одна и та же строка]

и вот мой код, но я до сих пор не могу понять эти две части кода

if(!D && (Dx || Dy))
    puts("NONE"); // the lines are parallel
if(!D && !Dx && !Dy)
    puts("LINE"); // they are the same lime

почему, когда определительравен нулю и dx = 0 или dy = 0, тогда они параллельны, а когда d = 0 и dx = 0 и dy = 0, то это одна и та же линия, которую я знаю, когда определитель равен нулю, тогда нет единственного решения, но не можетпонять часть !DX и !DY и DX || DY

Вот полный код

#include <iostream>

using namespace std;

struct point{
    int x , y;
};

struct segment{
    point s , e;
};

int main(){
    int n;
    scanf("%d" , &n);
    puts("INTERSECTING LINES OUTPUT");
    while(n--){
        segment a , b;
        scanf("%d%d%d%d" , &a.s.x , &a.s.y , &a.e.x , &a.e.y);
        scanf("%d%d%d%d" , &b.s.x , &b.s.y , &b.e.x , &b.e.y);
        double a1 , b1 , c1 , a2 , b2 , c2 , D , Dx , Dy;
        a1 = a.e.y - a.s.y;
        b1 = a.s.x - a.e.x;
        c1 = a1 * (a.s.x) + b1 * (a.s.y);

        a2 = b.e.y - b.s.y;
        b2 = b.s.x - b.e.x;
        c2 = a2 * (b.s.x) + b2 * (b.s.y);

        D = a1 * b2 - a2 * b1;
        Dx = c1 * b2 - c2 * b1;
        Dy = a1 * c2 - a2 * c1;

        if(!D && (Dx || Dy))
            puts("NONE"); // the lines are parallel
        if(!D && !Dx && !Dy)
            puts("LINE"); // they are the same line
        else printf("POINT %.2f %.2f\n" , (double)Dx / D , (double) Dy / D);
     }
     return 0;
 }

Answer 1

Обратная связь, которая беспокоится об арифметике с плавающей точкой, находится на точке (Ха!).Поскольку входные данные являются целыми, я мог бы предложить выполнить математику с целочисленными типами.

Задаваемые вами вопросы сводятся к тому, чтобы увидеть, эквивалентны ли две дроби.Я предлагаю следующий класс помощников:

struct ratio {
    int dx;
    int dy;

    ratio(int dxIn, int dyIn) :
        dx(dxIn), dy(dyIn) {
    }

    bool isEquivalent(ratio rhs) const {
        if ((dx == 0 && dy == 0) || (rhs.dx == 0 && rhs.dy == 0))
            return (dx == 0 && dy == 0) && (rhs.dx == 0 && rhs.dy == 0);
        return dx * rhs.dy == dy * rhs.dx;
    }
};

Answer 2

Каждый отрезок линии преобразуется в (a,b,c) координаты для расширенной линии, которые образуют уравнение линии a*x+b*y+c=0.Что вам нужно знать, так это то, что вектор (a,b) ортогонален линии.

Величина D = a1*b2 - a2*b1 является перекрестным произведением между двумя ортогональными векторами.Как вы знаете, перекрестное произведение двух параллельных векторов равно 0.Таким образом, если это так, две линии совпадают или параллельны.

Точка пересечения определяется как (Dx/D,Dy/D), где Dx=b1*c2-b2*c1 и Dy=a2*c1-a1*c2, поэтому, когда все равны нулю Dx=Dy=D=0 точка пересеченияне определено, что означает, что линии совпадают.В противном случае, если только D=0 точка пересечения находится на бесконечности, а линии параллельны.

Остальное просто типично сбивает с толку C синтаксис.

Answer 3

Один способ думать об этом, грубо говоря, состоит в том, что когда D == 0 и Dx == 0 и Dy == 0, то «координаты точки пересечения» Dx / D и Dy / D являются неопределенными формами0/0, который может быть любым числом.Это означает, что линии пересекаются в целом ряде точек, что возможно только в том случае, если они являются одной и той же линией.

С другой стороны, если D == 0 и Dx! = 0 или Dy! = 0(или оба), тогда значение Dx / D или Dy / D (или оба) равно бесконечности.Другими словами, линии пересекаются на бесконечности (только), что является еще одним способом сказать, что линии параллельны и не совпадают.

Проверка, является ли (D) для двойного числа плохой идеей для парыпричин.1) непонятноПонимание этого выражения требует некоторых довольно подробных знаний о преобразованиях типов в языке, что, честно говоря, не у каждого программиста.2) Ошибки округления и другие проблемы числовой нестабильности могут помешать вычислению, и вместо D == 0 у вас есть какой-то крошечный D, не равный 0. Тогда! D считается истинным, даже если оно должно быть ложным без ошибки округления.Вместо этого вы должны сравнить, является ли abs (D) <некоторый допуск, который немного больше 0. </p>

Наконец, ваша программа уязвима к проблемам переполнения: если две линии близки по уклону, но в остальном абсолютно разумны, пересечениеточка может быть очень большой.Это ситуация, которая имеет смысл в чисто математическом контексте, но не так много важна для компьютера.Вместо этого лучше задать вопрос, находится ли пересечение внутри отрезков, определенных точками.Эта проблема обсуждается на странице Википедии .