Определение взаиморасположения двух прямых, нахождение точки пересечения (реализации на С++)

C++   5 Январь 2016  Автор статьи: Александр Гавриков 

Пусть даны две прямые, заданные парой точек. В первой строке заданы две точки P_{1} и Q_{1} своими координатами (P_{1}^{x}, P_{1}^{y}) и (Q_{1}^{x}, Q_{1}^{y}), которые образуют первую прямую. Во второй строке заданы другие две точки P_{2} и Q_{2} своими координатами (P_{2}^{x}, P_{2}^{y}) и (Q_{2}^{x}, Q_{2}^{y}), которые образуют вторую прямую. Требуется определить взаиморасположение этих прямых. Две прямые могут пересекаться в единственной точке Res с координатами (Res^{x}, Res^{y}), не иметь общих точек, когда они параллельны, иметь бесконечно много общих точек, когда если они совпадают.

Для решения задачи используются структуры point и line для описания точки и прямой на плоскости соответственно.

Точка на плоскости в структуре данных point определяется двумя координатами x и y вещественного типа. Сравнение вещественных чисел производится через наперед заданную погрешность eps, в текущем решении eps = 1e-8. Структура point имеет следующую сигнатуру.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//структура для описания точки на плоскости
struct point {
    double x, y; //координаты точки

        //конструкторы
    point();
    point(int x, int y);
    point(double x, double y);

    //оператор == для проверки, что точки совпадает и имеют одинаковые координаты
    friend bool operator == (const point& p, const point& q);

    //оператор != для проверки, что точки не совпадает и имеют разные координаты
    friend bool operator != (const point& p, const point& q);
};

Оператор «==» используется для проверки того, совпадают точки или нет. Две точки равны, если имеют одинаковые координаты. Сравнение двух вещественных чисел осуществляется с учетом погрешности по модулю. Если необходимо проверить, что две точки P и Q имеют различные координаты, то используется оператор «!=».

Прямая на плоскости в структуре данных line определяется коэффициентами A, B, C. Коэффициенты задают уравнение прямой на плоскости в виде Ax + By + C = 0. Так как троек (A, B, C) может быть бесконечно много, то производим нормировку прямой. Для этого делим все три коэффициента A, B, C на величину Z = \sqrt{A^2 + B^2}. После этого для построенной прямой будет выполняться A^2 + B^2 = 1. Тем самым порядок коэффициентов A и B уже не будет зависеть от входных координат, а коэффициент C будет того же порядка, что и числа A, B. На практике это приводит к улучшению точности вычислений. После такого преобразования для одной и той же прямой могут получаться две тройки коэффициентов: числа A, B, C равны с точностью до умножения на -1. Для уникальности коэффициентов прямой A, B, C произведем дополнительное преобразование. Если A < -eps (значение A отрицательное) или |A| < eps, B < -eps (значение A равно нулю, значение B отрицательное), то умножаем все три числа на -1. После подобной нормировки для двух совпадающих прямых коэффициенты A, B, C будут уникальными.

Структура line имеет следующую сигнатуру.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//структура для задания прямой на плоскости
struct line {
    //параметры прямой
    double a, b, c;

        //конструкторы
    line();
    line(double a_, double b_, double c_);
    line(point p1, point p2);

    /* метод для определения взаиморасположения двух прямых
     * 0 - прямые не пересекаются и параллельны
     * 1 - прямые пересекаются в одной точке
     * 2 - прямые совпадают и имеют бесконечно много точек
     */

    public: int intersect(line l, point& res);
};

Метод intersect служит для определения взаиморасположения прямых. Вторым параметром является объект res структуры point, который передается по ссылке. В случае когда две прямые пересекаются, координаты точки пересечения будут содержаться в точке res.

Входные данные

В первой строке входного файла заданы две точки P_{1} и Q_{1} своими координатами (P_{1}^{x}, P_{1}^{y}) и (Q_{1}^{x}, Q_{1}^{y}), образующие первую прямую. Во второй строке заданы другие две точки P_{2} и Q_{2} своими координатами (P_{2}^{x}, P_{2}^{y}) и (Q_{2}^{x}, Q_{2}^{y}), образующие вторую прямую. Координаты точек являются вещественными числами.

Выходные данные

Если одна из пар точек однозначно не задает прямую, когда точки P_{1}, Q_{1} или P_{2}, Q_{2} совпадают, то в выходной файл выводится -1.

Если прямые не имеют общих точек пересечения, то есть параллельны и не совпадают, то в выходной файл выводится 0.

Если прямые пересекаются в одной точке, то в первой строке выходного файла выводится число 1, а во второй строке координаты точки их пересечения (Res^{x}, Res^{y}) с точностью до 6 знаков после запятой.

Если прямые имеют бесконечное число точек, то есть совпадают, то в выходной файл выводится 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctime>

using namespace std;

double EPS = 1e-6;

//метод сравнения двух вещественных чисел с заданной погрешностью
bool equal(double x, double y) {
    return abs(x - y) < EPS;
}

//структура для описания точки на плоскости
struct point {
    double x, y; //координаты точки

    point() {
        x = 0;
        y = 0;
    }

    point(int x, int y) {
        this->x = x * 1.0;
        this->y = y * 1.0;
    };

    point(double x, double y) {
        this->x = x;
        this->y = y;
    };

    //оператор == для проверки, что точки совпадает и имеют одинаковые координаты
    friend bool operator == (const point& p, const point& q) {
        return equal(p.x, q.x) && equal(p.y, q.y);
    }

    //оператор != для проверки, что точки не совпадает и имеют разные координаты
    friend bool operator != (const point& p, const point& q) {
        return !equal(p.x, q.x) || !equal(p.y, q.y);
    }
};

//структура для задания прямой на плоскости
struct line {
    //параметры прямой
    double a, b, c;

    line() {
        a = 0;
        b = 0;
        c = 0;
    }

    line(double a_, double b_, double c_) {
        //нормировка прямой
        double z = sqrt(a_ * a_ + b_ * b_);
        a_ /= z;
        b_ /= z;
        c_ /= z;
        if (a_ < -EPS || (abs(a_) < EPS && b_ < -EPS)) {
            a_ *= -1;
            b_ *= -1;
            c_ *= -1;
        }
        a = a_;
        b = b_;
        c = c_;
    };

    line(point p1, point p2) {
        //если точки совпадают, то по ним нельзя построить прямую
        if (p1 == p2) {
            return;
        }
        //получение коэффициентов прямой по координатам двух точек
        double a_ = p1.y - p2.y;
        double b_ = p2.x - p1.x;
        double c_ = -1 * (p1.y - p2.y) * p1.x - (p2.x - p1.x) * p1.y;
        //нормировка прямой
        double z = sqrt(a_ * a_ + b_ * b_);
        a_ /= z;
        b_ /= z;
        c_ /= z;
        if (a_ < -EPS || (abs(a_) < EPS && b_ < -EPS)) {
            a_ *= -1;
            b_ *= -1;
            c_ *= -1;
        }
        a = a_;
        b = b_;
        c = c_;
    };

    //вспомогательный метод для вычисления определителя размера 2X2
    private: double det(double x11, double x12, double x21, double x22) {
        return x11 * x22 - x12 * x21;
    };

    /* метод для определения взаиморасположения двух прямых
     * 0 - прямые не пересекаются и параллельны
     * 1 - прямые пересекаются в одной точке
     * 2 - прямые совпадают и имеют бесконечно много точек
     */

    public: int intersect(line l, point& res) {
        double denom = det(a, b, l.a, l.b);
        if (abs(denom) < EPS) {
            //прямые совпадают и имеет бесконечно точек пересечения
            if (equal(c, l.c)) {
                return 2;
            }
            //прямые параллельны и не пересекаются
            return 0;
        }
        //прямые пересекаются в одной точке, вычисляем координаты
        res.x = det(-c, b, -l.c, l.b) / denom;
        res.y = det(a, -c, l.a, -l.c) / denom;
        return 1;
    }
};

point p1, p2; //точки, задающие первую прямую
point q1, q2; //точки, задающие вторую прямую

/* взаиморасположение прямых:
 * -1 - неверные входные данные
 * 0 - прямые не пересекаются и параллельны
 * 1 - прямые пересекаются в одной точке
 * 2 - прямые совпадают и имеют бесконечно много точек
 */

int ans = 0;

line l1, l2; //прямые

point res; //точка пересечения прямых, если она существует

//процедура считывания входных данных с консоли
void readData() {
    //считываем координаты точек, задающих первую прямую
    scanf("%lf %lf %lf %lf", &p1.x, &p1.y, &p2.x, &p2.y);
    //считываем координаты точек, задающих вторую прямую
    scanf("%lf %lf %lf %lf", &q1.x, &q1.y, &q2.x, &q2.y);
}

void solve() {
    //строим прямые по двум точкам
    if (p1 != p2) {
        l1 = line(p1, p2);
    } else {
        //точки p1 и p2 совпадают, по ним невозможности построить прямую
        ans = -1;
    }
    if (q1 != q2) {
        l2 = line(q1, q2);
    } else {
        //точки q1 и q2 совпадают, по ним невозможности построить прямую
        ans = -1;
    }

    //находим взаиморасположения прямых, если обе из них построены
    if (ans != -1) {
        ans = l1.intersect(l2, res);
    }
}

//процедура вывода данных на консоль
void printData() {
    printf("%d\n", ans);

    if (ans == 1) {
        printf("%.6lf %.6lf", res.x, res.y);
    }
}

int main()
{
    readData();
    solve();
    printData();

    return 0;
}

 

Пример 1

Случай, когда две прямые пересекаются.

Входные данные
1 1 3 3
0 2 2 0
Выходные данные
1
1.0000 1.0000

 

 

Пример 2

Случай, когда две прямые параллельны и не совпадают.

Входные данные
0 0 2 2
0 3 2 5
Выходные данные
0

 

 

Пример 3

Случай, когда две прямые совпадают.

Входные данные
0 0 2 2
1 1 3 3
Выходные данные
2

 

 

Пример 4

Случай, когда первая пара точек P_{1} и Q_{1} равны и не задают однозначно прямую, так как через одну точку на плоскости можно провести бесконечно много прямых.

Входные данные
2 2 2 2
1 1 3 3
Выходные данные
-1

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++