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

C++   5 января 2016  Автор статьи: Александр Гавриков 
geekbrains.ru/

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


//структура для описания точки на плоскости
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 имеет следующую сигнатуру.


//структура для задания прямой на плоскости
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.


#include
#include
#include
#include
#include
#include
#include

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++

geekbrains.ru/
geekbrains.ru/