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

@_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

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

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
20. Мат мед. Абсентеизм как отдельный тип простоя anaschu 29.05.2026 Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .	19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип anaschu 28.05.2026 Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .	"Прокси" для последовательного порта Eddy_Em 28.05.2026 Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .	Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.
Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .	Модель здравосохранения 17. Планы на выгорание anaschu 23.05.2026 Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .	Изменение цветов в палитре gif файла aka фавикона russiannick 23.05.2026 Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .

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

	Пересечение треугольников 14.12.2014, 03:24. Показов 13798. Ответов 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