Найти пересечение двух прямоугольников

@Siquel · Регистрация: 08.09.2013

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

Подскажите как можно быстрее написать программу, которая будет искать точки пересечений двух прямоугольников.
Пользователь вводит вершины прямоугольников в таком формате:

2--------------------3
-
-
-
1--------------------4

Пока просто описываю все возможные случаи вручную, их выходит 14 штук не считая когда 2 прямоугольника находятся на смежной грани. Пытался найти в интернете, но вроде все что попадались не рассматривали все возможные случаи.

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
/*
point[0][0]-x1
point[0][1]-y1
point[1][0]-x2
point[1][1]-y2
point[2][0]-x3
point[2][1]-y3
point[3][0]-x4
point[3][1]-y4
*/
void Friend::cross(rect a, rect b){
    if ((a.point[0][1] > b.point[1][1]) || (a.point[1][1] < a.point[0][1]) ||
        (a.point[3][0]<b.point[0][0]) || (a.point[0][0]>b.point[3][0]))
        cout << "Прямоугольники не пересекаются" << endl;
    if ((a.point[2][0]>b.point[0][0]) && (a.point[2][0]<b.point[3][0]) && (a.point[2][1]>b.point[0][1])
        && (a.point[2][1] < b.point[1][1]))
        cout << "Прямоугольник пересекается в точках: " << b.point[0][0] << "," << a.point[2][1] << "  "<<
        a.point[2][0] << "," << b.point[0][1] << endl;
 
    if ((a.point[3][0]>b.point[0][0]) && (a.point[3][0]<b.point[3][0]) && (a.point[3][1]>b.point[0][1])
        && (a.point[3][1] < b.point[1][1]))
        cout << "Прямоугольник пересекается в точках: " << b.point[0][0] << "," << a.point[2][1] << "  " <<
        a.point[3][0] << "," << b.point[1][1] << endl;
}

@D_in_practice · 08.12.2014, 11:36

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
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
#include <iostream>
#include <cmath>
 
const double EPS = 1e-10;
 
int line(double p1[], double p2[], double l[]);//прямая по двум точкам
    //вернет 0 - если точки совпали
    //вернет 1 - если k != inf.        | l[0] = k и l[1] = b, где y = kx + b
    //вернет 2 - если x = c (k == inf) | l[0] = c
 
int cross_line(double line1[], double line2[], double point[], int p = 2);
    //параметр p = 4 если обе прямые наклонные
    //p = 5 если первая вертикальна, p = 7 если вторая, p = 8 обе
    //вернет 0 - если прямые параллельны
    //вернет 1 - если одна общая точка | point[0] = x, point[1] = y
    //вернет 2 - если совпали
 
double max(double a, double b){ return a > b ? a : b;}
 
double min(double a, double b){ return a < b ? a : b;}
 
using namespace std;
 
int main(){
    
    double rect1[4][2] = {{0, 0}, {0, 4}, {5, 4}, {5, 0}};
    double rect2[4][2] = {{2, 5}, {4, 7}, {8, 3}, {6, 1}};
    
    double out[4][2];//если не ошибаюсь точек не более 4-х
    int n_out = 0;
    
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j){
 
            double line1[2], line2[2];
            int p1, p2;
            
            p1 = line(rect1[i], rect1[(i + 1)%4], line1);
            p2 = line(rect2[j], rect2[(j + 1)%4], line2);
            
            //я считаю что данные введены верно
            double point[2];
            if (cross_line(line1, line2, point, p1 + 3*p2) == 1){
                
                //проверим лежит ли точка пересечения прямых на отрезках
                double x = point[0];
                double y = point[1];
                
                double x_min1 = min(rect1[i][0], rect1[(i + 1)%4][0]) - EPS;
                double x_max1 = max(rect1[i][0], rect1[(i + 1)%4][0]) + EPS;
                double y_min1 = min(rect1[i][1], rect1[(i + 1)%4][1]) - EPS;
                double y_max1 = max(rect1[i][1], rect1[(i + 1)%4][1]) + EPS;
                
                double x_min2 = min(rect2[j][0], rect2[(j + 1)%4][0]) - EPS;
                double x_max2 = max(rect2[j][0], rect2[(j + 1)%4][0]) + EPS;
                double y_min2 = min(rect2[j][1], rect2[(j + 1)%4][1]) - EPS;
                double y_max2 = max(rect2[j][1], rect2[(j + 1)%4][1]) + EPS;
                
                if (x_min1 < x && x < x_max1 && y_min1 < y && y < y_max1 &&
                    x_min2 < x && x < x_max2 && y_min2 < y && y < y_max2){
                    
                    out[n_out][0] = point[0];
                    out[n_out][1] = point[1];
                    ++n_out;
                }
            }else if (cross_line(line1, line2, point, p1 + p2) == 2)
                std::cout<<"Имеются стороны лежащие на одной прямой"<<std::endl;
        }
    for (int i = 0; i < n_out; ++i)
        std::cout << out[i][0] << ' ' << out[i][1] << std::endl;
}
 
int line(double p1[], double p2[], double l[]){//прямая по двум точкам
    //вернет 0 - если точки совпали
    //вернет 1 - если k != inf.        | l[0] = k и l[1] = b, где y = kx + b
    //вернет 2 - если x = c (k == inf) | l[0] = c
    
    if (fabs(p1[0] - p2[0]) > EPS){//x1 != x2
        l[0] = (p1[1] - p2[1])/(p1[0] - p2[0]);//k = (y1 - y2)/(x1 - x2)
        l[1] = p1[1] - l[0]*p1[0];//b = y1 - k*x1
        return 1;
    }else if (fabs(p1[1] - p2[1]) < EPS)//y1 == y2
        return 0;
    else{
        l[0] = p1[0];
        return 2;
    }
}
 
int cross_line(double line1[], double line2[], double point[], int p){
    //параметр p = 4 если обе прямые наклонные
    //p = 5 если первая вертикальна, p = 7 если вторая, p = 8 обе
    //вернет 0 - если прямые параллельны
    //вернет 1 - если одна общая точка | point[0] = x, point[1] = y
    //вернет 2 - если совпали
    
    if (p == 4){
        
        if (fabs(line1[0] - line2[0]) < EPS){//k1 == k2
            if (fabs(line1[1] - line2[1]) < EPS)//b1 == b2
                return 2;
            else
                return 0;
        }else{
            point[0] = (line2[1] - line1[1])/(line1[0] - line2[0]);
            point[1] = line1[0]*point[0] + line1[1];
            return 1;
        }
    }else if (p == 5){
        
        point[0] = line1[0];
        point[1] = line2[0]*point[0] + line2[1];
        return 1;
        
    }else if (p == 7){
        
        point[0] = line2[0];
        point[1] = line1[0]*point[0] + line1[1];
        return 1;
        
    }else if (fabs(line1[0] - line2[0]) < EPS)//c1 == c2
        return 2;
    else
        return 0;
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .