Пересечение отрезков

@Ksan · Регистрация: 02.11.2010

Студворк — интернет-сервис помощи студентам

Есть 2 отрезка, определенные O1(x1, y1, x2, y2) и O2(x1, y1, x2, y2)

Нужно узнать, пересекаются ли они.

Собственно задача не так проста как кажется, тк через прямую (y = kx + b) невозможно создать универсальный алгоритм, тк отрезок может быть и четко вертикальным, а прямая не может быть таковой.
Есть у кого идеи универсального алгоритма, ибо с несколькими ифами меня не устраивает.

@diagon · 29.03.2012, 19:45

Пересечение отрезков.

@Ksan · 29.03.2012, 19:51 **[ТС]**

diagon, букв много, а смысл общий непонятен, на чем это основано. Словами, пожалуйста, словами объясни

@Duha666 · 29.03.2012, 19:54

Строим уравнение прямых(в общем виде). Пересекаем. Проверяем принадлежность точки пересечение обоим отрезкам.

@Nekto · 29.03.2012, 19:58

на паскале: http://delphid.dax.ru/www/exampl34.htm

@CENTRAL_SQUAD · 06.02.2022, 20:03

C++
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
#include <iostream>
#include <cmath>
#include <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
 
struct Point
{
    double x, y;
    Point(): x(0), y(0) {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double operator * (Point other)
{
        return x * other.y - y * other.x;
}
    double operator % (Point other)
{
        return x * other.x + y * other.y;
}
    double operator - (Point other) 
{ 
        return(x-other.x, y-other.y); 
} 
    double operator + (Point other) 
{ 
        return(x+other.x, y+other.y); 
} 
    double len()
{
        return sqrt(x * x + y * y);
}
};
 
int main()
{
    double Ax, Ay, Bx, By, Cx, Cy, Dx, Dy, min_AB_x, min_AB_y, max_AB_x, max_AB_y, min_CD_x, min_CD_y, max_CD_x, max_CD_y, prost1, prost2, prost3, prost4;
    cout << fixed << setprecision(10);
    cin >> Ax;
    cin >> Ay; 
    cin >> Bx;
    cin >> By;
    cin >> Cx;
    cin >> Cy;
    cin >> Dx;
    cin >> Dy;
    
    Point AB(Bx - Ax, By - Ay);
    Point CD(Dx - Cx, Dy - Cy);
    Point AC(Cx - Ax, Cy - Ay);
    Point AD(Dx - Ax, Dy - Ay);
    Point CA(Ax - Cx, Ay - Cy);
    Point CB(Bx - Cx, By - Cy);
    if (AB * CD != 0)
{
        if ((((AB * AC) * (AB * AD)) <= 0) and (((CD * CA) * (CD * CB)) <= 0))
{
            cout << "YES";
}
        else
{
            cout << "NO";
            return 0;
}
}
    else
{
        if (AB * AC != 0)
{
            cout << "NO";
            return 0;
}
        min_AB_x = min(Ax, Bx);
        min_AB_y = min(Ay, By);
        max_AB_x = max(Ax, Bx);
        max_AB_y = max(Ay, By);
        min_CD_x = min(Cx, Dx);
        min_CD_y = min(Cy, Dy);
        max_CD_x = max(Cx, Dx);
        max_CD_y = max(Cy, Dy);
        prost1 = max(min_AB_x, min_CD_x);
        prost2 = max(min_AB_y, min_CD_y);
        prost3 = min(max_AB_x, max_CD_x); 
        prost4 = min(max_AB_y, max_CD_y);
        if ((prost1 <= prost3) and (prost2 <= prost4)) 
{
            cout << "YES";
}
        else
{
            cout << "NO";
}
}
    return 0;
}

@Royal_X · 06.02.2022, 20:06

в игровой индустрии используется такая быстрая функция

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool LineSegmentsIntersection(double x1, double y1, double x2, double y2, 
    double x3, double y3, double x4, double y4)
{
    double _1 = x1 - x2;
    double _2 = x1 - x3;
    double _3 = x3 - x4;
    double _4 = y1 - y2;
    double _5 = y1 - y3;
    double _6 = y3 - y4;
    double d = _1 *_6 - _4 * _3;
    double t = (_2 * _6 - _5 * _3) / d;
    double u = (_2 * _4 - _5 * _1) / d;
    return t >= 0. && t <= 1. && u >= 0. && u <= 1.;
}

@CENTRAL_SQUAD · 06.02.2022, 22:41

C++
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
#include <iostream>
#include <cmath>
#include <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
 
struct Point
{
    double x, y;
    Point(): x(0), y(0) {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double operator * (Point other)
{
        return x * other.y - y * other.x;
}
    double operator % (Point other)
{
        return x * other.x + y * other.y;
}
    double len()
{
        return sqrt(x * x + y * y);
}
};
 
int main()
{
    double Ax, Ay, Bx, By, Cx, Cy, Dx, Dy, min_AB_x, min_AB_y, max_AB_x, max_AB_y, min_CD_x, min_CD_y, max_CD_x, max_CD_y, prost1, prost2, prost3, prost4;
    cout << fixed << setprecision(10);
    cin >> Ax;
    cin >> Ay; 
    cin >> Bx;
    cin >> By;
    cin >> Cx;
    cin >> Cy;
    cin >> Dx;
    cin >> Dy;
    
    Point AB(Bx - Ax, By - Ay);
    Point CD(Dx - Cx, Dy - Cy);
    Point AC(Cx - Ax, Cy - Ay);
    Point AD(Dx - Ax, Dy - Ay);
    Point CA(Ax - Cx, Ay - Cy);
    Point CB(Bx - Cx, By - Cy);
    if (AB * CD != 0)
{
        if ((((AB * AC) * (AB * AD)) <= 0) and (((CD * CA) * (CD * CB)) <= 0))
{
            cout << "YES";
}
        else
{
            cout << "NO";
            return 0;
}
}
    else
{
        if (AB * AC != 0)
{
            cout << "NO";
            return 0;
}
        min_AB_x = min(Ax, Bx);
        min_AB_y = min(Ay, By);
        max_AB_x = max(Ax, Bx);
        max_AB_y = max(Ay, By);
        min_CD_x = min(Cx, Dx);
        min_CD_y = min(Cy, Dy);
        max_CD_x = max(Cx, Dx);
        max_CD_y = max(Cy, Dy);
        prost1 = max(min_AB_x, min_CD_x);
        prost2 = max(min_AB_y, min_CD_y);
        prost3 = min(max_AB_x, max_CD_x); 
        prost4 = min(max_AB_y, max_CD_y);
        if ((prost1 <= prost3) and (prost2 <= prost4)) 
{
            cout << "YES";
}
        else
{
            cout << "NO";
}
}
    return 0;
}

Байт · 06.02.2022, 23:14

Ksan, Насколько я понимаю, это делается так.
Записываются параметрические уравнения отрезков. В векторном виде этот будет так
X1 = A1*t + B1*(1-t) 0<= t <= 1
X2 = A2*s + B2*(1-s) 0>= s <= 1
Решаем уравнение X1 = X2
после покоординатной росписи получим систему уравнений от 2-х переменных s, t
количество уравнений равно размерности пространства
Получив решение, , проверяем, удовлетворение неравенств 0<= t <= 1 0<= s <= 1
Усе!

Добавлено через 6 минут
Кстати, очень похоже на то, написал уважаемый Royal_X,
Просто, я как бы подвел теоретическую базу

А вообще, этот подход эффективно работает на многих геометрических задачах.
Важно понять, что "уравнение" некоторых объектов включает в себя и неравенства

Новые блоги и статьи Все статьи Все блоги /
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .

@Ksan 27 / 27 / 4 Регистрация: 02.11.2010 Сообщений: 370

	Пересечение отрезков 29.03.2012, 19:40. Показов 18618. Ответов 8 Метки нет (Все метки) Есть 2 отрезка, определенные O1(x1, y1, x2, y2) и O2(x1, y1, x2, y2) Нужно узнать, пересекаются ли они. Собственно задача не так проста как кажется, тк через прямую (y = kx + b) невозможно создать универсальный алгоритм, тк отрезок может быть и четко вертикальным, а прямая не может быть таковой. Есть у кого идеи универсального алгоритма, ибо с несколькими ифами меня не устраивает. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	29.03.2012, 19:45
	Пересечение отрезков. 0

@Ksan 27 / 27 / 4 Регистрация: 02.11.2010 Сообщений: 370
	29.03.2012, 19:51 [ТС]
	diagon, букв много, а смысл общий непонятен, на чем это основано. Словами, пожалуйста, словами объясни 0

@Duha666 53 / 53 / 19 Регистрация: 10.03.2012 Сообщений: 138
	29.03.2012, 19:54
	Строим уравнение прямых(в общем виде). Пересекаем. Проверяем принадлежность точки пересечение обоим отрезкам. 0

@Nekto 347 / 292 / 37 Регистрация: 23.03.2012 Сообщений: 838
	29.03.2012, 19:58
	на паскале: http://delphid.dax.ru/www/exampl34.htm 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	06.02.2022, 23:14
	Ksan, Насколько я понимаю, это делается так. Записываются параметрические уравнения отрезков. В векторном виде этот будет так X1 = A1t + B1(1-t) 0<= t <= 1 X2 = A2s + B2(1-s) 0>= s <= 1 Решаем уравнение X1 = X2 после покоординатной росписи получим систему уравнений от 2-х переменных s, t количество уравнений равно размерности пространства Получив решение, , проверяем, удовлетворение неравенств 0<= t <= 1 0<= s <= 1 Усе! Добавлено через 6 минут Кстати, очень похоже на то, написал уважаемый Royal_X, Просто, я как бы подвел теоретическую базу А вообще, этот подход эффективно работает на многих геометрических задачах. Важно понять, что "уравнение" некоторых объектов включает в себя и неравенства 0

Пересечение отрезков

Решение