Определение взаиморасположения двух прямых, нахождение точки пересечения (реализации на С++)
Пусть даны две прямые, заданные парой точек. В первой строке заданы две точки и
своими координатами
и
, которые образуют первую прямую. Во второй строке заданы другие две точки
и
своими координатами
и
, которые образуют вторую прямую. Требуется определить взаиморасположение этих прямых. Две прямые могут пересекаться в единственной точке
с координатами
, не иметь общих точек, когда они параллельны, иметь бесконечно много общих точек, когда если они совпадают.
Для решения задачи используются структуры и
для описания точки и прямой на плоскости соответственно.
Точка на плоскости в структуре данных определяется двумя координатами
и
вещественного типа. Сравнение вещественных чисел производится через наперед заданную погрешность
, в текущем решении
. Структура
имеет следующую сигнатуру.
//структура для описания точки на плоскости
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);
};
Оператор используется для проверки того, совпадают точки или нет. Две точки равны, если имеют одинаковые координаты. Сравнение двух вещественных чисел осуществляется с учетом погрешности по модулю. Если необходимо проверить, что две точки
и
имеют различные координаты, то используется оператор
.
Прямая на плоскости в структуре данных определяется коэффициентами
. Коэффициенты задают уравнение прямой на плоскости в виде
. Так как троек
может быть бесконечно много, то производим нормировку прямой. Для этого делим все три коэффициента
на величину
. После этого для построенной прямой будет выполняться
. Тем самым порядок коэффициентов
и
уже не будет зависеть от входных координат, а коэффициент
будет того же порядка, что и числа
,
. На практике это приводит к улучшению точности вычислений. После такого преобразования для одной и той же прямой могут получаться две тройки коэффициентов: числа
равны с точностью до умножения на -1. Для уникальности коэффициентов прямой
произведем дополнительное преобразование. Если
(значение
отрицательное) или
(значение
равно нулю, значение
отрицательное), то умножаем все три числа на
. После подобной нормировки для двух совпадающих прямых коэффициенты
будут уникальными.
Структура имеет следующую сигнатуру.
//структура для задания прямой на плоскости
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);
};
Метод служит для определения взаиморасположения прямых. Вторым параметром является объект
структуры
, который передается по ссылке. В случае когда две прямые пересекаются, координаты точки пересечения будут содержаться в точке
.
В первой строке входного файла заданы две точки и
своими координатами
и
, образующие первую прямую. Во второй строке заданы другие две точки
и
своими координатами
и
, образующие вторую прямую. Координаты точек являются вещественными числами.
Если одна из пар точек однозначно не задает прямую, когда точки ,
или
,
совпадают, то в выходной файл выводится
.
Если прямые не имеют общих точек пересечения, то есть параллельны и не совпадают, то в выходной файл выводится .
Если прямые пересекаются в одной точке, то в первой строке выходного файла выводится число , а во второй строке координаты точки их пересечения
с точностью до
знаков после запятой.
Если прямые имеют бесконечное число точек, то есть совпадают, то в выходной файл выводится .
#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 3 3 0 2 2 0 |
Выходные данные |
1 1.0000 1.0000 |
Случай, когда две прямые параллельны и не совпадают.
Входные данные |
---|
0 0 2 2 0 3 2 5 |
Выходные данные |
0 |
Случай, когда две прямые совпадают.
Входные данные |
---|
0 0 2 2 1 1 3 3 |
Выходные данные |
2 |
Случай, когда первая пара точек и
равны и не задают однозначно прямую, так как через одну точку на плоскости можно провести бесконечно много прямых.
Входные данные |
---|
2 2 2 2 1 1 3 3 |
Выходные данные |
-1 |
Pingback: Аноним()
Pingback: Melanie Glastrong()