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

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

C++

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

Статья
Комментарии (2)

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

Pingback: Аноним()
Pingback: Melanie Glastrong()

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

на Delphi
на Java
на C++

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

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

на Delphi

на Java

на C++