Нахождение точки пересечения двух прямых (и отрезков)
Время на прочтение
3 мин
Количество просмотров 42K
Введение
Довольно часто при разработке игр возникает необходимость находить точку пересечения прямых, отрезков, лучей и т.д. О том, как реализовать это максимально простым способом, в этой статье.
Популярные способы и их критика
Возможно, многие вспомнят способ из школьной алгебры — составить уравнения двух прямых, приравнять их правые части, найти x, и подставить его в уравнение прямой, чтобы найти y (Подробнее здесь).
Однако данный способ становится достаточно громоздким при написании кода (возможно поэтому вы сейчас читаете эту статью), к тому же, он не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай; если две прямые перпендикулярны осям, требуется повозиться с обработкой и этого случая. Такой код становится длинным и некрасивым.
В поисках более элегантного решения данной проблемы я наткнулся на весьма интересные способы, основанные на векторном умножении ( habr.com/ru/post/267037 ) и ray castinging’е ( ru.wikipedia.org/wiki/Ray_casting#Концепция ). Но на мой взгляд, они неоправданно сложные в вычислительном плане. Поэтому представляю вашему вниманию (и критике) мой способ.
Мой способ
Задача
Даны координаты двух отрезков. Нужно узнать, пересекаются ли отрезки, и если да, в какой точке. Для этой цели напишем функцию.
Решение
Условные обозначения для исключения недопониманий: a — вектор a, a(y) — проекция вектора a на ось Y, a{x1,y1} — вектор a, заданный координатами x1,y1.
Представим наши отрезки в виде двух векторов: a{x2-x1; y2-y1} и b{x3-x4; y3-y4}. Обратите, внимание, что вектор b имеет противоположное от ожидаемого направление. Введём вектор c{x3-x1; y3-y1}. Заметим, что a*k+b*n=c, где k,n — некоторые коэффициенты. Таким образом, получаем систему уравнений:
a(x)*k+b(x)*n=c(x)
a(y)*k+b(y)*n=c(y)
Наша задача сводится к нахождению этих коэффициентов (правда сказать, достаточно найти лишь один из них).
Предлагаю домножить обе части нижнего уравнения на q= -a(x)/a(y). Так после сложения двух уравнений, мы сразу избавимся от k. Нахождение n сведётся к решению обыкновенного линейного уравнения. Важно обратить внимание, что у n может не быть решения.
Внимательный читатель заметит, что при a(y)=0, мы получим ошибку. Пропишем ветвление на этапе нахождения a(y). Этот случай ещё проще, ведь мы сразу получаем уравнение с одной неизвестной.
Рекомендую попробовать вывести n самостоятельно, так будет понятнее, что откуда берётся в коде ниже.
Зная n, можно найти точку пересечения, для этого мы отнимем от координаты точки (x3,y3) вектор b*n
Собираем воедино
float dot[2]; // точка пересечения
bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
float n;
if (y2 - y1 != 0) { // a(y)
float q = (x2 - x1) / (y1 - y2);
float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; } // c(x) + c(y)*q
float fn = (x3 - x1) + (y3 - y1) * q; // b(x) + b(y)*q
n = fn / sn;
}
else {
if (!(y3 - y4)) { return 0; } // b(y)
n = (y3 - y1) / (y3 - y4); // c(y)/b(y)
}
dot[0] = x3 + (x4 - x3) * n; // x3 + (-b(x))*n
dot[1] = y3 + (y4 - y3) * n; // y3 +(-b(y))*n
return 1;
}
Данная функция принимает координаты вершин и возвращает значение 1, если прямые отрезков (именно прямые) пересекаются, иначе 0. Если же вам нужны координаты вершин, вы сможете взять их из массива dot[].
Важно: при введении двух совпадающих прямых, алгоритм выводит отсутствие пересечения. Алгоритм находит точку пересечения прямых, на которых лежат отрезки, поэтому точка может оказаться за пределами отрезка (что вам придётся дополнительно проверить в уже своём коде).
Применим функцию:
int main() {
if (cross(1,1,7,2, 7,3,5,6)) {
std::cout << dot[0] << " " << dot[1] << std::endl;
}
else {
std::cout<<"Not cross!"<<std::endl;
}
return 0;
}
Послесловие
Хоть я и не встретил этот способ в процессе гугления своей проблемы и вывел алгоритм самостоятельно, я не претендую на его полную оригинальность (и правильность). Поэтому добро пожаловать в комментарии!
Permalink
Cannot retrieve contributors at this time
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Задача 43: Напишите программу, которая найдёт точку пересечения двух прямых, | |
// заданных уравнениями y = k1 * x + b1, y = k2 * x + b2; значения b1, k1, b2 и k2 | |
// задаются пользователем. | |
// b1 = 2, k1 = 5, b2 = 4, k2 = 9 -> (-0,5; -0,5) | |
Console.Write(«Введите k1: «); | |
var k1 = Convert.ToDouble(Console.ReadLine()); | |
Console.Write(«Введите b1: «); | |
var b1 = Convert.ToDouble(Console.ReadLine()); | |
Console.Write(«Введите k2: «); | |
var k2 = Convert.ToDouble(Console.ReadLine()); | |
Console.Write(«Введите b2: «); | |
var b2 = Convert.ToDouble(Console.ReadLine()); | |
var x = —(b1 — b2) / (k1 — k2); | |
var y = k1 * x + b1; | |
x = Math.Round(x, 3); | |
y = Math.Round(y, 3); | |
Console.WriteLine($»Пересечение в точке: ({x};{y})«); |
Given points A and B corresponding to line AB and points P and Q corresponding to line PQ, find the point of intersection of these lines. The points are given in 2D Plane with their X and Y Coordinates. Examples:
Input : A = (1, 1), B = (4, 4) C = (1, 8), D = (2, 4) Output : The intersection of the given lines AB and CD is: (2.4, 2.4) Input : A = (0, 1), B = (0, 4) C = (1, 8), D = (1, 4) Output : The given lines AB and CD are parallel.
First of all, let us assume that we have two points (x1, y1) and (x2, y2). Now, we find the equation of line formed by these points. Let the given lines be :
- a1x + b1y = c1
- a2x + b2y = c2
We have to now solve these 2 equations to find the point of intersection. To solve, we multiply 1. by b2 and 2 by b1 This gives us, a1b2x + b1b2y = c1b2 a2b1x + b2b1y = c2b1 Subtracting these we get, (a1b2 – a2b1) x = c1b2 – c2b1 This gives us the value of x. Similarly, we can find the value of y. (x, y) gives us the point of intersection. Note: This gives the point of intersection of two lines, but if we are given line segments instead of lines, we have to also recheck that the point so computed actually lies on both the line segments. If the line segment is specified by points (x1, y1) and (x2, y2), then to check if (x, y) is on the segment we have to just check that
- min (x1, x2) <= x <= max (x1, x2)
- min (y1, y2) <= y <= max (y1, y2)
The pseudo code for the above implementation:
determinant = a1 b2 - a2 b1 if (determinant == 0) { // Lines are parallel } else { x = (c1b2 - c2b1)/determinant y = (a1c2 - a2c1)/determinant }
These can be derived by first getting the slope directly and then finding the intercept of the line.
C++
#include <bits/stdc++.h>
using
namespace
std;
#define pdd pair<double, double>
void
displayPoint(pdd P)
{
cout <<
"("
<< P.first <<
", "
<< P.second
<<
")"
<< endl;
}
pdd lineLineIntersection(pdd A, pdd B, pdd C, pdd D)
{
double
a1 = B.second - A.second;
double
b1 = A.first - B.first;
double
c1 = a1*(A.first) + b1*(A.second);
double
a2 = D.second - C.second;
double
b2 = C.first - D.first;
double
c2 = a2*(C.first)+ b2*(C.second);
double
determinant = a1*b2 - a2*b1;
if
(determinant == 0)
{
return
make_pair(FLT_MAX, FLT_MAX);
}
else
{
double
x = (b2*c1 - b1*c2)/determinant;
double
y = (a1*c2 - a2*c1)/determinant;
return
make_pair(x, y);
}
}
int
main()
{
pdd A = make_pair(1, 1);
pdd B = make_pair(4, 4);
pdd C = make_pair(1, 8);
pdd D = make_pair(2, 4);
pdd intersection = lineLineIntersection(A, B, C, D);
if
(intersection.first == FLT_MAX &&
intersection.second==FLT_MAX)
{
cout <<
"The given lines AB and CD are parallel.n"
;
}
else
{
cout <<
"The intersection of the given lines AB "
"and CD is: "
;
displayPoint(intersection);
}
return
0;
}
Java
class
Point
{
double
x,y;
public
Point(
double
x,
double
y)
{
this
.x = x;
this
.y = y;
}
static
void
displayPoint(Point p)
{
System.out.println(
"("
+ p.x +
", "
+ p.y +
")"
);
}
}
class
Test
{
static
Point lineLineIntersection(Point A, Point B, Point C, Point D)
{
double
a1 = B.y - A.y;
double
b1 = A.x - B.x;
double
c1 = a1*(A.x) + b1*(A.y);
double
a2 = D.y - C.y;
double
b2 = C.x - D.x;
double
c2 = a2*(C.x)+ b2*(C.y);
double
determinant = a1*b2 - a2*b1;
if
(determinant ==
0
)
{
return
new
Point(Double.MAX_VALUE, Double.MAX_VALUE);
}
else
{
double
x = (b2*c1 - b1*c2)/determinant;
double
y = (a1*c2 - a2*c1)/determinant;
return
new
Point(x, y);
}
}
public
static
void
main(String args[])
{
Point A =
new
Point(
1
,
1
);
Point B =
new
Point(
4
,
4
);
Point C =
new
Point(
1
,
8
);
Point D =
new
Point(
2
,
4
);
Point intersection = lineLineIntersection(A, B, C, D);
if
(intersection.x == Double.MAX_VALUE &&
intersection.y == Double.MAX_VALUE)
{
System.out.println(
"The given lines AB and CD are parallel."
);
}
else
{
System.out.print(
"The intersection of the given lines AB "
+
"and CD is: "
);
Point.displayPoint(intersection);
}
}
}
Python3
class
Point:
def
__init__(
self
, x, y):
self
.x
=
x
self
.y
=
y
def
displayPoint(
self
, p):
print
(f
"({p.x}, {p.y})"
)
def
lineLineIntersection(A, B, C, D):
a1
=
B.y
-
A.y
b1
=
A.x
-
B.x
c1
=
a1
*
(A.x)
+
b1
*
(A.y)
a2
=
D.y
-
C.y
b2
=
C.x
-
D.x
c2
=
a2
*
(C.x)
+
b2
*
(C.y)
determinant
=
a1
*
b2
-
a2
*
b1
if
(determinant
=
=
0
):
return
Point(
10
*
*
9
,
10
*
*
9
)
else
:
x
=
(b2
*
c1
-
b1
*
c2)
/
determinant
y
=
(a1
*
c2
-
a2
*
c1)
/
determinant
return
Point(x, y)
A
=
Point(
1
,
1
)
B
=
Point(
4
,
4
)
C
=
Point(
1
,
8
)
D
=
Point(
2
,
4
)
intersection
=
lineLineIntersection(A, B, C, D)
if
(intersection.x
=
=
10
*
*
9
and
intersection.y
=
=
10
*
*
9
):
print
(
"The given lines AB and CD are parallel."
)
else
:
print
(
"The intersection of the given lines AB "
+
"and CD is: "
)
intersection.displayPoint(intersection)
C#
using
System;
public
class
Point
{
public
double
x, y;
public
Point(
double
x,
double
y)
{
this
.x = x;
this
.y = y;
}
public
static
void
displayPoint(Point p)
{
Console.WriteLine(
"("
+ p.x +
", "
+ p.y +
")"
);
}
}
public
class
Test
{
public
static
Point lineLineIntersection(Point A, Point B, Point C, Point D)
{
double
a1 = B.y - A.y;
double
b1 = A.x - B.x;
double
c1 = a1 * (A.x) + b1 * (A.y);
double
a2 = D.y - C.y;
double
b2 = C.x - D.x;
double
c2 = a2 * (C.x) + b2 * (C.y);
double
determinant = a1 * b2 - a2 * b1;
if
(determinant == 0)
{
return
new
Point(
double
.MaxValue,
double
.MaxValue);
}
else
{
double
x = (b2 * c1 - b1 * c2) / determinant;
double
y = (a1 * c2 - a2 * c1) / determinant;
return
new
Point(x, y);
}
}
public
static
void
Main(
string
[] args)
{
Point A =
new
Point(1, 1);
Point B =
new
Point(4, 4);
Point C =
new
Point(1, 8);
Point D =
new
Point(2, 4);
Point intersection = lineLineIntersection(A, B, C, D);
if
(intersection.x ==
double
.MaxValue && intersection.y ==
double
.MaxValue)
{
Console.WriteLine(
"The given lines AB and CD are parallel."
);
}
else
{
Console.Write(
"The intersection of the given lines AB "
+
"and CD is: "
);
Point.displayPoint(intersection);
}
}
}
Javascript
<script>
class Point
{
constructor(x, y)
{
this
.x = x;
this
.y = y;
}
displayPoint(p){
document.write(
"("
+ p.x +
", "
+ p.y +
")"
);
}
}
function
lineLineIntersection(A,B,C,D){
var
a1 = B.y - A.y;
var
b1 = A.x - B.x;
var
c1 = a1*(A.x) + b1*(A.y);
var
a2 = D.y - C.y;
var
b2 = C.x - D.x;
var
c2 = a2*(C.x)+ b2*(C.y);
var
determinant = a1*b2 - a2*b1;
if
(determinant == 0)
{
return
new
Point(Number.MAX_VALUE, Number.MAX_VALUE);
}
else
{
var
x = (b2*c1 - b1*c2)/determinant;
var
y = (a1*c2 - a2*c1)/determinant;
return
new
Point(x, y);
}
}
let A =
new
Point(1, 1);
let B =
new
Point(4, 4);
let C =
new
Point(1, 8);
let D =
new
Point(2, 4);
var
intersection = lineLineIntersection(A, B, C, D);
if
(intersection.x == Number.MAX_VALUE && intersection.y == Number.MAX_VALUE){
document.write(
"The given lines AB and CD are parallel."
);
}
else
{
document.write(
"The intersection of the given lines AB "
+
"and CD is: "
);
intersection.displayPoint(intersection);
}
</script>
Output:
The intersection of the given lines AB and CD is: (2.4, 2.4)
Time Complexity: O(1)
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Aanya Jindal. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Last Updated :
16 Jun, 2022
Like Article
Save Article
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 |
#include <iostream> #include <cmath> #include <iomanip> using namespace std; static const double eps = 1e-7; class Dot { double x, y; public: Dot(double x = 0, double y = 0) { this->x = x; this->y = y; } double get_x() const {return x;} double get_y() const {return y;} }; class Vect { double x, y; public: Vect(double x = 0, double y = 0) { this->x = x; this->y = y; } Vect (const Dot & a, const Dot & b) {x = b.get_x() - a.get_x(); y = b.get_y() - a.get_y();} Vect operator+(const Vect & a); double get_x() const {return x;} double get_y() const {return y;} double get_mod() const {return sqrt(x * x + y * y);} }; Vect Vect::operator+(const Vect & a) { Vect res(this->get_x() + a.get_x(), this->get_y() + a.get_y()); return res; } Vect operator* (double a, const Vect & b) { Vect res(b.get_x() * a, b.get_y() * a); return res; } Vect operator* (const Vect & b, double a) { Vect res(b.get_x() * a, b.get_y() * a); return res; } Dot operator+ (const Dot & dot, const Vect & v) { return Dot(dot.get_x() + v.get_x(), dot.get_y() + v.get_y()); } double scalar_product(const Vect & a, const Vect & b) { return (a.get_x() * b.get_x() + a.get_y() * b.get_y()); } bool is_collinear(const Vect & a, const Vect & b) { return abs((abs(scalar_product(a, b)) - a.get_mod() * b.get_mod())) < ::eps; } class Line { Vect dir; Dot dot; public: Line() { dir = Vect(); dot = Dot(); } Line(const Dot & a, const Dot & b); Line(const Vect & v, const Dot & dot) {dir = v; this->dot = dot;} Vect get_vect() const {return dir;} Dot get_dot() const {return dot;} }; Line::Line(const Dot & a, const Dot & b) { dir = Vect(a, b); dot = a; } Dot i_hate_conditions(const Line & a, const Line & b) { double xa = a.get_dot().get_x(), ya = a.get_dot().get_y(); double xc = a.get_vect().get_x(), yc = a.get_vect().get_y(); double xb = b.get_dot().get_x(), yb = b.get_dot().get_y(); double xd = b.get_vect().get_x(), yd = b.get_vect().get_y(); double t = ((xa - xb) / xd + (yb - ya) / yc * xc / xd) / (1 - yd * xc / yc / xd); Dot res = b.get_dot() + t * b.get_vect(); return res; } //функция вычисления точки пересечения Dot i_hate_conditions_new(const Line & a, const Line & b) { double xa = a.get_dot().get_x(), ya = a.get_dot().get_y(); double xc = a.get_vect().get_x(), yc = a.get_vect().get_y(); double xb = b.get_dot().get_x(), yb = b.get_dot().get_y(); double xd = b.get_vect().get_x(), yd = b.get_vect().get_y(); Dot res; //случай, когда оба направляющих вектора параллельны двум разным осям координат if (((abs(xc) < ::eps) && (abs(yd) < ::eps)) || ((abs(xd) < ::eps) && (abs(yc) < ::eps))) { double x, y; if (abs(a.get_vect().get_x()) < ::eps) { x = a.get_dot().get_x(); y = b.get_dot().get_y(); } else { x = b.get_dot().get_x(); y = a.get_dot().get_y(); } res = Dot(x, y); } else if (abs(yd) < ::eps) { //случай, когда возможно один из векторов параллелен, этим условием выбирается тот, который не параллелен, чтобы избежать деления на 0 double t = (xa - xb + (yb - ya) / yc * xc) / (xd - yd / yc * xc); res = b.get_dot() + b.get_vect() * t; } else { double k = (xa - xb - (ya - yb) / yd * xd) / (yc / yd * xd - xc); res = a.get_dot() + a.get_vect() * k; } return res; } //фунция проверки на совпадение, параллельность и просто пересечение void intersect_lines(const Line & a, const Line & b) { Vect v1 = a.get_vect(); Vect v2 = b.get_vect(); if (is_collinear(v1, v2)) { Vect dif(a.get_dot(), b.get_dot()); if (is_collinear(dif, v1)) { cout << "2" << endl; } else { cout << "0" << endl; } } else { Dot res = i_hate_conditions_new(a, b); cout << fixed; cout << "1 " << setprecision(5) << res.get_x() << ' ' << res.get_y()<< endl; } } int main(int argc, char const *argv[]) { double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; Line l1(Dot(x1, y1), Dot(x2, y2)); cin >> x1 >> y1 >> x2 >> y2; Line l2(Dot(x1, y1), Dot(x2, y2)); intersect_lines(l1, l2); return 0; } |
Перейти к содержанию
На чтение 2 мин Просмотров 381 Опубликовано 06.03.2023
Обновлено 06.03.2023
Задача: Напишите программу, которая найдёт точку пересечения двух прямых, заданных уравнениями y = k1 * x + b1, y = k2 * x + b2; значения b1, k1, b2 и k2 задаются пользователем.
Содержание
- Пример:
- Решение:
- Пояснение:
Пример:
b1 = 2, k1 = 5, b2 = 4, k2 = 9 -> (-0,5; -0,5)
Решение:
Console.WriteLine(«Введите переменную b1: «);
double b1 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine(«Введите переменную k1: «);
double k1 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine(«Введите переменную b2: «);
double b2 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine(«Введите переменную k2: «);
double k2 = Convert.ToDouble(Console.ReadLine());double x = -(b1 — b2) / (k1 — k2);
double y = k1 * x + b1;Console.Write($»n Точка пересечения двух прямых: [{x},{y}]»);
Пояснение:
Надо решить уравнение и найти точку пересечения двух прямых.
Похожий код:
Программист, разработчик с 5 летним опытом работы. Учусь на разработчика игр на Unity и разработчика VR&AR реальности (виртуальной реальности). Основные языки программирования: C#, C++.