Пересечение треугольников

@_20_ · Регистрация: 29.09.2011

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

Надо определить, пересекаютя ли треугольники. Наличие общей грани нельзя считать пересечением, но если один треугольник лежит внутри другого, то это пересечение.

Подойдёт ли мне алгоритм, описаный здесь:
Пересечение треугольников в 3d (пятый пост)?

ValeryS · 15.12.2014, 00:36

Сообщение от _20_

То есть у вас есть алгоритм, но Вы его никому не покажете?

видать читать не научили

Сообщение от ValeryS

и посему я умолкаю пока не напишу код который

слово "пока" ни очем не говорит?
но у меня есть своя работа и это пока может растянутся на большой срок

а алгоритм прост как "Колумбово яйцо"

Сообщение от ValeryS

тупой цикл по трем сторонам

и что я должен показать? Решение? его пока нет
Мысль я высказал
кстати, Уважаемый, от Вас я даже мысли не услышал, только ссылки какие то, задача то кому нужна?
Мне могут оппонировать Mr.X, D_in_practice, но не Вы, посему я подожду так месяца два, когда сессия закончится, и выложу свое решение(которого у меня пока нет, есть мысли вслух)

Сообщение от _20_

Получается, что Вы уже сами сомневаетесь, что Вы хотели сказать?

в Вашей интерпретации,Да
человек который не понимает разницу между математикой и конкретным языком программирования

Сообщение от ValeryS

поскольку в Си

Сообщение от _20_

что информатики

может я скажу банальность, но информатика не имеет ни какого отношения ни к Си ни к Паскалю, ни к прочему Бейсику
Информатитика есть наука о сборе, обработке и передаче информации
кстати решение о двух треугольниках, тоже информатике не интересно, ей интересно пересекаются данные треугольники(Да) или нет(Нет) что и должна вернуть функция реализованная на Си

@_20_ · 15.12.2014, 02:15 **[ТС]**

Сообщение от ValeryS

Сообщение от ValeryS
и посему я умолкаю пока не напишу код который
слово "пока" ни очем не говорит?
но у меня есть своя работа и это пока может растянутся на большой срок

Ну конечно же, давайте подождём, пока все про эту тему забудут, тогда уже можно будет ничего и не писать. Но Вы конечно же очень хорошо предсталяете себе, как это сделать.
Сколько будет 7х8 ?

@Mr.X · 15.12.2014, 05:43

Сообщение от _20_

Вот здесь есть алгоритм:
http://algolist.manual.ru/math... line2d.php

Чтобы проверить только существование пересечения, достаточно

Сообщение от Mr.X

так проверить для сторон ab и cd:
det(ab, ac) * det(ab, ad) < 0
&& det(cd, cb) * det(cd, ca) < 0
где det(a, b) = a.x * b.y - a.y * b.x;

@D_in_practice · 16.12.2014, 09:47

1. Нахожу все точки пересечения треугольников
2. Если точек больше 2-х значит прересеклись.
Иначе
Создаю многоугольник включающий в себя все тт пересечения и тт наших треугольников.
https://www.cyberforum.ru/cpp-... ost6807894
3. Сравниваю площадь многоугольника, с площадями треугольников.

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
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>
#include <cmath>
 
using namespace std;
 
struct D_Point{
    double x;
    double y;
};
 
double s_n(D_Point a[], int n){
    //ïëîùàäü n - óãîëüíèêà
    double sum = 0;
    for (int i = 0; i < n; ++i){
        double det = a[i % n].x * a[(i + 1) % n].y 
                      - a[(i + 1) % n].x * a[i % n].y;
        sum += det;
    }
    return fabs(sum / 2);
}
 
double max(double a, double b){
    return a > b ? a : b;
}
 
double min(double a, double b){
    return a < b ? a : b;
}
 
int main(){
 
    const double EPS = 1e-10;
    
    D_Point a[3], b[3];
    
    a[0].x = 0; a[0].y = 5;
    a[1].x = 1; a[1].y = 0;
    a[2].x = 3; a[2].y = 2;
    b[0].x =-1; b[0].y = 0;
    b[1].x = 0; b[1].y = 3;
    b[2].x = 2; b[2].y = 4;
    
    D_Point c[8];
    int n = 0;
    
    double flag = 0;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j){
            
            double x11 = a[(i + 1)%3].x;
            double x12 = a[(i + 2)%3].x;
            double y11 = a[(i + 1)%3].y;
            double y12 = a[(i + 2)%3].y;
            
            double x21 = b[(j + 1)%3].x;
            double x22 = b[(j + 2)%3].x;
            double y21 = b[(j + 1)%3].y;
            double y22 = b[(j + 2)%3].y;
            
            //ïåðâàÿ ïðÿìàÿ âåðòèêàëüíà
            if (fabs(x11 - x12) < EPS && fabs(x21 - x22) > EPS){
                if (min(x21, x22) - EPS < x11 && x11 < max(x21, x22) + EPS){
                    double k = (y21 - y22)/(x21 - x22);
                    double b0 = y21 - k*x21;
                    double y = k*x11 + b0;
                    if (min(y21, y22) - EPS < y && y < max(y21, y22) + EPS)
                        if (min(y11, y12) - EPS < y && y < max(y11, y12) + EPS){
                            c[n].x = x11;
                            c[n].y = y;
                            ++n;
                        }   
                }
            //âòîðàÿ ïðÿìàÿ âåðòèêàëüíà
            }else if (fabs(x11 - x12) > EPS && fabs(x21 - x22) < EPS){
                if (min(x11, x12) - EPS < x21 && x21 < max(x11, x12) + EPS){
                    double k = (y11 - y12)/(x11 - x12);
                    double b0 = y11 - k*x11;
                    double y = k*x21 + b0;
                    if (min(y21, y22) - EPS < y && y < max(y21, y22) + EPS)
                        if (min(y11, y12) - EPS < y && y < max(y11, y12) + EPS){
                            c[n].x = x21;
                            c[n].y = y;
                            ++n;
                        }
                }
            //îáå ïðÿìûå âåðòèêàëüíû
            }else if (fabs(x11 - x12) < EPS && fabs(x21 - x22) < EPS){
                if (fabs(x11 - x21) < EPS){
                    double y1 = max(min(y21, y22), min(y11, y12));
                    double y2 = min(max(y21, y22), max(y11, y12));
                    if(y2 > y1){
                        c[n].x = x11;
                        c[n].y = y1;
                        ++n;
                        c[n].x = x11;
                        c[n].y = y2;
                        ++n;
                    }   
                }   
            //îáå ïðÿìûå íàêëîííû
            }else{
                double k1 = (y11 - y12)/(x11 - x12);
                double k2 = (y21 - y22)/(x21 - x22);
                if (fabs(k1 - k2) < EPS){//êîýô íàêëîíà ñîâïàëè
                    double b1 = y11 - k1*x11;
                    double b2 = y21 - k2*x21;
                    if (fabs(b1 - b2) < EPS){//ïðÿìûå ñîâïàëè
                        double x1 = max(min(x21, x22), min(x11, x12));
                        double x2 = min(max(x21, x22), max(x11, x12));
                        if(x2 > x1){
                            c[n].x = x1;
                            c[n].y = k1*x1 + b1;
                            ++n;
                            c[n].x = x2;
                            c[n].y = k1*x2 + b1;
                            ++n;
                        }
                    }
                }else{
                    double b1 = y11 - k1*x11;
                    double b2 = y21 - k2*x21;
                    c[n].x = (b2 - b1)/(k1 - k2);
                    c[n].y = k1*c[n].x + b1;
                    ++n;
                }
            }
        }
    
    if (n >= 3){
        cout << 1 << endl;
    }else{
        
        for (int i = n; i < n + 6; ++i)
        if (i < n + 3)
            c[i] = a[i - n];
        else
            c[i] = b[i - n - 3];
        n += 6;
        
        //1. Ñîðòèðóþ ìàññèâ ïî x ïîòîì ïî y.
        for (int i = n - 1; i >= 0; --i)
            for (int j = 0; j < i; ++j)
                if ((c[j].x > c[j + 1].x) || 
                    (fabs(c[j].x - c[j + 1].x) < EPS && c[j].y > c[j + 1].y)){
                        D_Point temp = c[j];
                        c[j] = c[j + 1];
                        c[j + 1] = temp;
                }
    
        //2. Íàéäåì ïåðâóþ òî÷êó, êîîðäèíàòà x êîòîðîé îòëè÷íà îò íà÷àëüíîé ò. 
        int first = 0;
        while(fabs(c[0].x - c[++first].x) < EPS);
    
        //3. Îòñîðòèðóåì òî÷êè íà÷èíàÿ ñ first ïî óáûâàíèþ êîýôèöèåíòà íàêëîíà
        //ïðÿìîé ïðîâåäåííîé äî êàæäîé òî÷êè, èç òî÷êè ïåðåä first
        //ÿ îòñîðòèðóþ ïî âîçðàñòàíèþ -êîýôôèöèåíò
        //ïðè ðàâíûõ êîýýôèöèåíòàõ áóäåì ñðàâíèâàòü êîîðä x
        D_Point begin = c[first - 1];
        for (int i = n - 1; i >= 0; --i)
            for (int j = first; j < i; ++j){
                double k1 = (begin.y - c[j].y) / (begin.x - a[j].x);
                double k2 = (begin.y - c[j + 1].y) / (begin.x - c[j + 1].x);
                if ((-k1 > -k2) || (fabs(k1 - k2) < EPS && c[j].x >c[j + 1].x)){
                   D_Point temp = c[j];
                    c[j] = c[j + 1];
                    c[j + 1] = temp;
                }
            }
        if (s_n(c, n) < s_n(a, 3) + s_n(b, 3) + EPS)
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }
}

@SatanaXIII · 16.12.2014, 10:52

Не по теме:

Сообщение от D_in_practice

Если точек больше 2-х значит прересеклись

А если у них только одна общая вершина, то это как называется? Просто спрашиваю. Зачем именно две точки для пересечения? Одной недостаточно?

@D_in_practice · 16.12.2014, 10:58

если три точки значит точно пересеклись,
если 2 точки или одна может быть просто касание или один треугольник в другом
если нет точек может оказаться что один треугольник в другом.
И конечно может оказаться что я чего то не учел.

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

@Mr.X · 16.12.2014, 11:00

D_in_practice, треугольники, имеющие общую сторону

C++
1
2
3
4
5
6
7
    a[0].x = 0; a[0].y = 0;
    a[1].x = 0; a[1].y = 1;
    a[2].x = -1; a[2].y = 0;
 
    b[0].x = 0; b[0].y = 0;
    b[1].x = 0; b[1].y = 1;
    b[2].x = 1; b[2].y = 0;

ваша программа считает пересекающимися.

@SatanaXIII · 16.12.2014, 11:39

D_in_practice, я извиняюсь за тупизм, то разве касание треугольников не есть их пересечение? Это всмысле именно математически разные понятия?

@Mr.X · 16.12.2014, 12:19

Сообщение от SatanaXIII

D_in_practice, я извиняюсь за тупизм, то разве касание треугольников не есть их пересечение? Это всмысле именно математически разные понятия?

Треугольники пересекаются, если площадь общей части больше нуля.

@SatanaXIII · 16.12.2014, 12:30

Сообщение от Mr.X

Треугольники пересекаются, если площадь общей части больше нуля.

Один же больше нуля. Следовательно при одной лишь точке соприкосновения (вершина, к примеру) треугольники считаются пересекающимися.
Меня смутил ответ D_in_practice. Я думал есть какая-то разница в терминах: пересекаются, соприкасаются. Конкретно такая, что соприкасающиеся нельзя назвать пересекающимися.

@Алексей89 · 16.12.2014, 12:40

Я, с позволения вставлю свои 5 копеек.
Не так давно я решал похожую задачу в Матлабе...
Мне видится 2 уровня абстракции при решении данной задачи.
1. Можно оперировать сторонами треугольника как "прямыми проходящими через 2 точки". Если эти прямые пересекаются то для системы из двух уравнений этих прямых существует решение. Если прямые совпадают, то существует бесконечное множество решений. Минипроблемка в том, что любые не параллельные прямые где-нибудь да и пересекутся, поэтому при решении задачи таким способом нужно составить вагончик условий принадлежности точек пересечений к границам отрезков (сторон), кроме того особого внимания потребует случай, когда 1 треугольник вписан во второй. С этой позиции наиболее ультимативным выглядит решение, которое предложил ValeryS, единственный случай который придётся учесть отдельно - это упомянутая "звезда Давида".
2. уровень абстракции: Можно оперировать треугольниками, как двумерными фигурами. Если бы скажем решалась задача о пересечении двух окружностей, то нужно было бы объединить в одну систему уравнения для этих окружностей и если система имеет решение - значит они пересекаются.
В случае же с треугольниками, каждый можно задать системой из трёх неравенств (Если при работе с каждой прямой описывать где верх, где низ, и где другие прямые, то это уже само по себе громоздко), однако, забегая вперёд, могу сказать что самый простой способ сделать это - усреднить координаты вершин Треугольника, и полученные координаты центра треугольника подставить по очереди в уравнения прямой для каждой из сторон. Таким образом можно получить три неравенства и объеденить их в систему.
Получив две системы неравенств их надо будет объединить в одну, и если полученная система из 6 неравенств будет иметь решение - значит они пересекаются. В этом случае последнее, что тебе останется - это проверить не касаются ли они только стороной.

Если ты решаешь задачу, там на конкурс какой-то то второй вариант тебе должен быть более интересен.
Если же тебе просто надо чтобы это работало, то я бы советовал тебе начать с того что предложил ValeryS, а для того, чтобы учесть случай "звезды Давида" тебе нужно будет кроме каждой из вершин, также проверить центр каждого треугольника на предмет принадлежности к другому треугольнику.
Вот и весь рецепт.

Эпилог: Я испытал небывалую гамму чувств, когда, проработав над своей задачей дня 3, на этом-же форуме развил похожую теорию, а в ответ мне сказали что это всё уже решено в стандартной матлабовской функции :-)))

@Mr.X · 16.12.2014, 14:03

Добавлено через 1 минуту
Алексей89, да вы жжете просто! А можете то же самое, но в стихах?

@_20_ · 16.12.2014, 17:22 **[ТС]**

Сообщение от SatanaXIII

D_in_practice, я извиняюсь за тупизм, то разве касание треугольников не есть их пересечение? Это всмысле именно математически разные понятия?
__________________

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

Пока что я так сделал, очень похоже на то, что говорил Mr.X:

Кликните здесь для просмотра всего текста

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
    bool SN6::isLinesAreCrossing(int x11, int y11, int x12, int y12, int x21, int y21, int x22, int y22){
        // x1* y1* - первая линия, x2* y2* - вторая линия.
        if((x11 == x21 && y11 == y21) || (x11 == x22 && y11 == y22) || (x12 == x21 && y12 == y21) || (x12 == x22 && y12 == y22))
            return false;
        int dx1 = x12-x11, dy1 = y12-y11; // Длина проекций первой линии на ось x и y
        int dx2 = x22-x21, dy2 = y22-y21; // Длина проекций второй линии на ось x и y
        int dxx = x11-x21, dyy = y11-y21;
        int div, mul;
 
        if ((div = (int)((double)dy2*dx1-(double)dx2*dy1)) == 0)
          return false; // Линии параллельны...
        if (div > 0) {
          if ((mul = (int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > div)
            return false; // Первый отрезок пересекается за своими границами...
          if ((mul = (int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > div)
             return false; // Второй отрезок пересекается за своими границами...
        }
        if ((mul = -(int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > -div)
          return false; // Первый отрезок пересекается за своими границами...
        if ((mul = -(int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > -div)
          return false; // Второй отрезок пересекается за своими границами...
        return true;
    }
 
 
    bool SN6::isTrianglesAreCrossing(SN6 t2){
        SN6 t1 = *this;
        if(isLinesAreCrossing(t1.x1, t1.y1, t1.x2, t1.y2, t2.x1, t2.y1, t2.x2, t2.y2))  return true;
        if(isLinesAreCrossing(t1.x1, t1.y1, t1.x2, t1.y2, t2.x2, t2.y2, t2.x3, t2.y3))  return true;
        if(isLinesAreCrossing(t1.x1, t1.y1, t1.x2, t1.y2, t2.x3, t2.y3, t2.x1, t2.y1))  return true;
 
        if(isLinesAreCrossing(t1.x2, t1.y2, t1.x3, t1.y3, t2.x1, t2.y1, t2.x2, t2.y2))  return true;
        if(isLinesAreCrossing(t1.x2, t1.y2, t1.x3, t1.y3, t2.x2, t2.y2, t2.x3, t2.y3))  return true;
        if(isLinesAreCrossing(t1.x2, t1.y2, t1.x3, t1.y3, t2.x3, t2.y3, t2.x1, t2.y1))  return true;
 
        if(isLinesAreCrossing(t1.x3, t1.y3, t1.x1, t1.y1, t2.x1, t2.y1, t2.x2, t2.y2))  return true;
        if(isLinesAreCrossing(t1.x3, t1.y3, t1.x1, t1.y1, t2.x2, t2.y2, t2.x3, t2.y3))  return true;
        if(isLinesAreCrossing(t1.x3, t1.y3, t1.x1, t1.y1, t2.x3, t2.y3, t2.x1, t2.y1))  return true;
 
        if(isPointInclude(t2.x1, t2.y1))    return true;
        if(isPointInclude(t2.x2, t2.y2))    return true;
        if(isPointInclude(t2.x3, t2.y3))    return true;
        return t1 == t2;
    }

@D_in_practice · 16.12.2014, 19:27

Сообщение от SatanaXIII

Я думал есть какая-то разница в терминах: пересекаются, соприкасаются. Конкретно такая, что соприкасающиеся нельзя назвать пересекающимися.

Сообщение от D_in_practice

Сообщение от _20_

Наличие общей грани нельзя считать пересечением

Это условие особый геморой, с ним программа сильно вырастет.

Сообщение от Mr.X

то можно так проверить для сторон ab и cd:
det(ab, ac) * det(ab, ad) < 0
&& det(cd, cb) * det(cd, ca) < 0
где det(a, b) = a.x * b.y - a.y * b.x;

Простите так увлекся что сразу не стал рассматривать, не годится для случая, когда все координаты y = 0.
{0, 0}, {1, 0} и {2, 0}, {3, 0} - не пересекаются
{0, 0}, {2, 0} и {1, 0}, {3, 0} - пересекаются
а по формуле выдаст одинаковый результат

Вот рабочий код, ошибок вроде пока не вижу:
1. Нахожу точки пересечения, повторяющиеся не беру.
2. Если точек 3 и больше значит пересеклись.
3. Если точек 0 или 1, то при пересечении один треугольник окажется в другом и площадь фигуры составленная из всех точек будет меньше максимального из треугольников.
4. Если точек 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
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#include <iostream>
#include <cmath>
 
using namespace std;
 
const double EPS = 1e-10;
 
struct D_Point{
    double x;
    double y;
};
 
struct D_Line{
    D_Point p1;
    D_Point p2;
};
 
double S_n(D_Point a[], int n);//ïëîùàäü n - óãîëüíèêà
double Max(double a, double b);
double Min(double a, double b);
int Cross(D_Line l1, D_Line l2, D_Point a[2]);//âåðíåò ÷èñëî òî÷åê ïåðåñå÷åíèÿ
 
int main(){
 
    D_Point a[3], b[3];
    
    a[0].x = 0; a[0].y = 5;
    a[1].x = 1; a[1].y = 0;
    a[2].x = 3; a[2].y = 2;
    b[0].x =-1; b[0].y = 0;
    b[1].x = 0; b[1].y = 3;
    b[2].x = 2; b[2].y = 4;
       
    D_Point c[8];
    int size = 0;
    
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j){
            
            D_Line l1, l2;
            
            l1.p1 = a[(i + 1)%3];
            l1.p2 = a[(i + 2)%3];
            l2.p1 = b[(j + 1)%3];
            l2.p2 = b[(j + 2)%3];
            
            D_Point p[2];
            
            int n = Cross(l1, l2, p);
            
            for (int k = 0; k < n; ++k){
                
                int flag = 0;
                for (int t = 0; t < size; ++t)
                    if (fabs(p[k].x-c[t].x )< EPS && fabs(p[k].y-c[t].y)< EPS){
                        flag = 1;
                        break;
                    }
                
                if (flag == 0)
                    c[size++] = p[k];
            }
        }
    
    if (size >= 3){
        cout << 1 << endl;
    }else{
        
        for (int i = size; i < size + 6; ++i)
        if (i < size + 3)
            c[i] = a[i - size];
        else
            c[i] = b[i - size - 3];
        size += 6;
        
        //1. Ñîðòèðóþ ìàññèâ ïî x ïîòîì ïî y.
        for (int i = size - 1; i >= 0; --i)
            for (int j = 0; j < i; ++j)
                if ((c[j].x > c[j + 1].x) || 
                    (fabs(c[j].x - c[j + 1].x) < EPS && c[j].y > c[j + 1].y)){
                        D_Point temp = c[j];
                        c[j] = c[j + 1];
                        c[j + 1] = temp;
                }
    
        //2. Íàéäåì ïåðâóþ òî÷êó, êîîðäèíàòà x êîòîðîé îòëè÷íà îò íà÷àëüíîé ò. 
        int first = 0;
        while(fabs(c[0].x - c[++first].x) < EPS);
    
        //3. Îòñîðòèðóåì òî÷êè íà÷èíàÿ ñ first ïî óáûâàíèþ êîýôèöèåíòà íàêëîíà
        //ïðÿìîé ïðîâåäåííîé äî êàæäîé òî÷êè, èç òî÷êè ïåðåä first
        //ÿ îòñîðòèðóþ ïî âîçðàñòàíèþ -êîýôôèöèåíò
        //ïðè ðàâíûõ êîýýôèöèåíòàõ áóäåì ñðàâíèâàòü êîîðä x
        D_Point begin = c[first - 1];
        for (int i = size - 1; i >= 0; --i)
            for (int j = first; j < i; ++j){
                double k1 = (begin.y - c[j].y) / (begin.x - a[j].x);
                double k2 = (begin.y - c[j + 1].y) / (begin.x - c[j + 1].x);
                if ((-k1 > -k2) || (fabs(k1 - k2) < EPS && c[j].x >c[j + 1].x)){
                   D_Point temp = c[j];
                    c[j] = c[j + 1];
                    c[j + 1] = temp;
                }
            }
        
        if (size == 6 || size == 7){//íåò òî÷åê ïåðåñå÷åíèÿ èëè 1
            
            if (S_n(c, size) < Max(S_n(a, 3), S_n(b, 3)))
                cout << 1 << endl;
            else
                cout << 0 << endl;
        
        }else{//Äâå òî÷êè ïåðåñå÷åíèÿ
            
            if (fabs(S_n(c, size) - S_n(a, 3) - S_n(b, 3)) < EPS)
                cout << 0 << endl;
            else
                cout << 1 << endl;
        }
    }
}
 
double S_n(D_Point a[], int n){//ïëîùàäü n - óãîëüíèêà
    
    double sum = 0;
    for (int i = 0; i < n; ++i){
        double det = a[i % n].x * a[(i + 1) % n].y 
                      - a[(i + 1) % n].x * a[i % n].y;
        sum += det;
    }
    return fabs(sum / 2);
}
 
double Max(double a, double b){
    return a > b ? a : b;
}
 
double Min(double a, double b){
    return a < b ? a : b;
}
 
int Cross(D_Line l1, D_Line l2, D_Point a[2]){//âåðíåò ÷èñëî òî÷åê ïåðåñå÷åíèÿ
    
    double x11 = l1.p1.x;
    double x12 = l1.p2.x;
    double y11 = l1.p1.y;
    double y12 = l1.p2.y;
            
    double x21 = l2.p1.x;
    double x22 = l2.p2.x;
    double y21 = l2.p1.y;
    double y22 = l2.p2.y;
    
    if (fabs(x11 - x12) < EPS && fabs(x21 - x22) < EPS){
        //îáå ïðÿìûå âåðòèêàëüíû
        if (fabs(x11 - x21) < EPS){
                
            double y1 = Max(Min(y21, y22), Min(y11, y12));
            double y2 = Min(Max(y21, y22), Max(y11, y12));
            
            a[0].x = x11;
            a[0].y = y1;
            a[1].x = x11;
            a[1].y = y2;
            
            return 2;       
        }else return 0;
    
    }else if (fabs(x11 - x12) < EPS && fabs(x21 - x22) > EPS){
        //ïåðâàÿ ïðÿìàÿ âåðòèêàëüíà
        if (Min(x21, x22) - EPS < x11 && x11 < Max(x21, x22) + EPS){
            
            double k = (y21 - y22)/(x21 - x22);
            double b = y21 - k*x21;
            double y = k*x11 + b;
            
            double min1 = Min(y11, y12) - EPS;
            double max1 = Max(y11, y12) + EPS;
            double min2 = Min(y21, y22) - EPS;
            double max2 = Max(y21, y22) + EPS;
            
            if (min1 < y && y < max1 && min2 < y && y < max2){
                
                a[0].x = x11;
                a[0].y = y;
                
                return 1;
            }else return 0;
        }else return 0;
    
    }else if (fabs(x11 - x12) > EPS && fabs(x21 - x22) < EPS){
        //âòîðàÿ ïðÿìàÿ âåðòèêàëüíà
        if (Min(x11, x12) - EPS < x21 && x21 < Max(x11, x12) + EPS){
            
            double k = (y11 - y12)/(x11 - x12);
            double b = y11 - k*x11;
            double y = k*x21 + b;
            
            double min1 = Min(y11, y12) - EPS;
            double max1 = Max(y11, y12) + EPS;
            double min2 = Min(y21, y22) - EPS;
            double max2 = Max(y21, y22) + EPS;
            
            if (min1 < y && y < max1 && min2 < y && y < max2){
                
                a[0].x = x21;
                a[0].y = y;
                
                return 1;
            }else return 0;
        }else return 0;
    
    }else{//ïðÿìûå íàêëîííûå
        
        double k1 = (y11 - y12)/(x11 - x12);
        double k2 = (y21 - y22)/(x21 - x22);
        double b1 = y11 - k1*x11;
        double b2 = y21 - k2*x21;
        
        if (fabs(k1 - k2) < EPS && fabs(b1 - b2) < EPS){//åñëè ïðÿìûå ñîâïàëè
        
            double x1 = Max(Min(x21, x22), Min(x11, x12));
            double x2 = Min(Max(x21, x22), Max(x11, x12));
            
            if (x1 > x2){
                
                a[0].x = x1;
                a[0].y = k1*x1 + b1;
                a[1].x = x2;
                a[1].y = k2*x2 + b2;
                
                return 2;
            }else return 0;
        
        }else if (fabs(k1 - k2) < EPS && fabs(b1 - b2) > EPS)//ïàðàëëåëüíû
            return 0;
        else{
            
            double x = (b2 - b1)/(k1 - k2);
            double y = k1*x + b1;
            
            double x2 = Max(Min(x21, x22), Min(x11, x12)) + EPS;
            double x1 = Min(Max(x21, x22), Max(x11, x12)) - EPS;
            double y2 = Max(Min(y21, y22), Min(y11, y12)) + EPS;
            double y1 = Min(Max(y21, y22), Max(y11, y12)) - EPS;
            
            if (x1 < x && x < x2 && y1 < y && y < y1){
                
                a[0].x = x;
                a[0].y = y;
                
                return 1;
            }else return 0;
        }
    }
}

Добавлю, на словах одно, а когда пишешь код сам, все сразу на свои места встает.

_20_, Вам отдельное спасибо за звезду Давида которую я пропустил, сразу видно человек пытался задачу решить сам.
Всем спасибо

@Mr.X · 16.12.2014, 21:16

D_in_practice, вы меня недопоняли.

Сообщение от Mr.X

Цитата Сообщение от Mr.X Посмотреть сообщение
существуют пересекающиеся стороны, точка пересечения которых лежит внутри каждой стороны.
,
то можно так проверить для сторон ab и cd:
det(ab, ac) * det(ab, ad) < 0
&& det(cd, cb) * det(cd, ca) < 0
где det(a, b) = a.x * b.y - a.y * b.x;

Это критерий того, что стороны непараллельны и пересекаются в точке, которая для обеих сторон является внутренней. Никакие параллельные стороны по этой формуле не пересекаются. Это вы что-то в расчетах ошиблись.

@D_in_practice · 16.12.2014, 21:28

Не по теме:

Mr.X, тогда это только один из 6 возможных случаев, о чем Вы сказали уже.

@Mr.X · 16.12.2014, 21:46

D_in_practice, что-то у меня ваша программа, скопированная без изменений, через раз то 0, то 1 выводит.

Добавлено через 9 минут

Сообщение от D_in_practice

Mr.X, тогда это только один из 6 возможных случаев, о чем Вы сказали уже.

Каких шести?

Сообщение от Mr.X

Либо треугольники совпадают, либо вершина одного лежит внутри другого, либо середина стороны одного лежит внутри другого, либо существуют пересекающиеся стороны, точка пересечения которых лежит внутри каждой стороны.

Здесь четыре всего.

@D_in_practice · 16.12.2014, 22:04

Mr.X, а параллельные стороны не берем, например случай с общей прямой x = 0?

Сообщение от Mr.X

C++
1
2
3
4
5
6
7
    a[0].x = 0; a[0].y = 0;
    a[1].x = 0; a[1].y = 1;
    a[2].x = -1; a[2].y = 0;
 
    b[0].x = 0; b[0].y = 0;
    b[1].x = 0; b[1].y = 1;
    b[2].x = 1; b[2].y = 0;

Сообщение от Mr.X

Никакие параллельные стороны по этой формуле не пересекаются.

Сообщение от Mr.X

точка пересечения которых лежит внутри каждой стороны.

Если Вы напишите программу для всех этих случаев программа будет в 2 раза больше моей последней.

@Mr.X · 16.12.2014, 22:09

Сообщение от D_in_practice

Если Вы напишите программу для всех этих случаев программа будет в 2 раза больше моей последней.

Ну, у вас пока нет правильной, а на неправильные какой смысл ссылаться? Неправильную можно и в одну строчку написать.

@D_in_practice · 16.12.2014, 22:22

Mr.X, Чем это она неправильная? Ну да я ошибся пару раз, но ведь не ошибается только тот кто ничего не делает.
С этой проверкой она 100% работает, но мне кажется что и без нее, это только случаай для 2-х общих точек нужно проверять по нему, и то не факт.

Сообщение от Mr.X

либо вершина одного лежит внутри другого

Не по теме:

Ладно молчу, код некрасивый

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@_20_ 22 / 56 / 9 Регистрация: 29.09.2011 Сообщений: 618

	Пересечение треугольников 14.12.2014, 03:24. Показов 13486. Ответов 49 Метки нет (Все метки) Надо определить, пересекаютя ли треугольники. Наличие общей грани нельзя считать пересечением, но если один треугольник лежит внутри другого, то это пересечение. Подойдёт ли мне алгоритм, описаный здесь: Пересечение треугольников в 3d (пятый пост)? 0

@D_in_practice 343 / 343 / 331 Регистрация: 02.10.2014 Сообщений: 666
	16.12.2014, 10:58
	если три точки значит точно пересеклись, если 2 точки или одна может быть просто касание или один треугольник в другом если нет точек может оказаться что один треугольник в другом. И конечно может оказаться что я чего то не учел. P.S. Первая программа абсолютна не работает, Пересечение треугольников хотя я раньше видел подобное решение на форуме, потому что представьте еврейскую звезду, пересекаются треугольники и нет вершин внутри треугольников. 0

@SatanaXIII Почетный модератор 5851 / 2862 / 392 Регистрация: 01.11.2011 Сообщений: 6,906
	16.12.2014, 11:39
	D_in_practice, я извиняюсь за тупизм, то разве касание треугольников не есть их пересечение? Это всмысле именно математически разные понятия? 0

@Алексей89 34 / 34 / 4 Регистрация: 19.02.2013 Сообщений: 118
	16.12.2014, 12:40
	Я, с позволения вставлю свои 5 копеек. Не так давно я решал похожую задачу в Матлабе... Мне видится 2 уровня абстракции при решении данной задачи. 1. Можно оперировать сторонами треугольника как "прямыми проходящими через 2 точки". Если эти прямые пересекаются то для системы из двух уравнений этих прямых существует решение. Если прямые совпадают, то существует бесконечное множество решений. Минипроблемка в том, что любые не параллельные прямые где-нибудь да и пересекутся, поэтому при решении задачи таким способом нужно составить вагончик условий принадлежности точек пересечений к границам отрезков (сторон), кроме того особого внимания потребует случай, когда 1 треугольник вписан во второй. С этой позиции наиболее ультимативным выглядит решение, которое предложил ValeryS, единственный случай который придётся учесть отдельно - это упомянутая "звезда Давида". 2. уровень абстракции: Можно оперировать треугольниками, как двумерными фигурами. Если бы скажем решалась задача о пересечении двух окружностей, то нужно было бы объединить в одну систему уравнения для этих окружностей и если система имеет решение - значит они пересекаются. В случае же с треугольниками, каждый можно задать системой из трёх неравенств (Если при работе с каждой прямой описывать где верх, где низ, и где другие прямые, то это уже само по себе громоздко), однако, забегая вперёд, могу сказать что самый простой способ сделать это - усреднить координаты вершин Треугольника, и полученные координаты центра треугольника подставить по очереди в уравнения прямой для каждой из сторон. Таким образом можно получить три неравенства и объеденить их в систему. Получив две системы неравенств их надо будет объединить в одну, и если полученная система из 6 неравенств будет иметь решение - значит они пересекаются. В этом случае последнее, что тебе останется - это проверить не касаются ли они только стороной. Если ты решаешь задачу, там на конкурс какой-то то второй вариант тебе должен быть более интересен. Если же тебе просто надо чтобы это работало, то я бы советовал тебе начать с того что предложил ValeryS, а для того, чтобы учесть случай "звезды Давида" тебе нужно будет кроме каждой из вершин, также проверить центр каждого треугольника на предмет принадлежности к другому треугольнику. Вот и весь рецепт. Эпилог: Я испытал небывалую гамму чувств, когда, проработав над своей задачей дня 3, на этом-же форуме развил похожую теорию, а в ответ мне сказали что это всё уже решено в стандартной матлабовской функции :-))) 1

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	16.12.2014, 14:03
	Добавлено через 1 минуту Алексей89, да вы жжете просто! А можете то же самое, но в стихах? 1

@D_in_practice
	16.12.2014, 21:28
	Не по теме: Mr.X, тогда это только один из 6 возможных случаев, о чем Вы сказали уже. 0