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

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

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

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

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

@_Ivana · 16.12.2014, 23:47

Во-первых, плюс ValeryS за адекватное отношение к ТС.
А во-вторых, по традиции не понимаю, откуда столько многабукаф кода? Если считать пересечением ненулевую общую площадь, то вот код (если считать пересечением наличие общих точек, то надо будет лишь немного переделать функцию isCross):

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
typedef struct{double x; double y;} point;
 
bool isCross(point p1, point p2, point p3, point p4)
{
    double a = p2.x - p1.x, b = p3.x - p4.x, c = p3.x - p1.x;
    double d = p2.y - p1.y, e = p3.y - p4.y, f = p3.y - p1.y;
    double det = a*e - b*d, t; if (det==0) return false;
    t = (c*e - b*f)/det; if (t<=0 || t>=1) return false;
    t = (a*f - c*d)/det; if (t<=0 || t>=1) return false;
    return true;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    point a[4], b[4];
 
    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;
 
    a[3].x = a[0].x; a[3].y = a[0].y;
    b[3].x = b[0].x; b[3].y = b[0].y;
 
    bool res = false;
    for (int i=0; i<3; i++) for (int j=0; j<3; j++)
        if (isCross(a[i], a[i+1], b[i], b[i+1])) {res = true; break;}
 
    std::cout << "Triangles are crossed: " << res << std::endl;
    system("pause");
    return 0;
}

Добавлено через 6 минут
ЗЫ Очепятка:

C++
1
isCross(a[i], a[i+1], b[i], b[i+1])

читать конечно же как

C++
1
isCross(a[i], a[i+1], b[j], b[j+1])

@AleksRazgul · 17.12.2014, 03:01

Вот компактный и простой в понимании, но отлавливает не все случаи пересечения, а только случаи если хоть одна вершина одного треугольника находится внутри другого.

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
bool BnutriOrNot(float* x1, float* y1, float* x2, float* y2)
//Функция проверяет находится ли хоть одна из вершин треугольника внутри другого треугольника (на границе несчитается)
//x1, y1, x2, y2 - массивы глубиной [3]
//x1,y1 - три точки первого треугольника
//x2,y2 - три точки второго треугольника
//return: true - есть вершина внутри треугольника; false - нет;
{
    float vektorz1;
    float vektorz2;
    float vektorz3;
    bool znak1;
    bool znak2;
    bool znak3;
    bool zero1;
    bool zero2;
    bool zero3;
    for (int i=0;i<3;i++) //перебераем вершины треугольников
    {
        // векторное произведение вектора (стороны пер. треугольника) с вектором до вершины втор. (из первой вершины стороны до вершины)
        vektorz1 = (((x1[1]-x1[0])*(y2[i]-y1[0])) - ((y1[1]-y1[0])*(x2[i]-x1[0])));
        // тоже для тойже вершины (втор. треугольника) с второй стороной пер. треугольника
        vektorz2 = (((x1[2]-x1[1])*(y2[i]-y1[1])) - ((y1[2]-y1[1])*(x2[i]-x1[1])));
        // тоже для тойже вершины (втор. треугольника) с третьей стороной пер. треугольника
        vektorz3 = (((x1[0]-x1[2])*(y2[i]-y1[2])) - ((y1[0]-y1[2])*(x2[i]-x1[2])));
        znak1 = (vektorz1 > 0);
        znak2 = (vektorz2 > 0);
        znak3 = (vektorz3 > 0);
        zero1 = (vektorz1 = 0);
        zero2 = (vektorz2 = 0);
        zero3 = (vektorz3 = 0);
        if (!(zero1 || zero2 || zero3) //вершина ненаходится на ребре
            && ((znak1 == znak2) && (znak1 == znak3))) //вершина с одной стороны от всех векторов (сторон треугольника)
            return true;                               //значит внутри треугольника
 
        // тоже только проверяется вершина первого треугольника относительно сторон второго треугольника
        vektorz1 = (((x2[1]-x2[0])*(y1[i]-y2[0])) - ((y2[1]-y2[0])*(x1[i]-x2[0])));
        vektorz2 = (((x2[2]-x2[1])*(y1[i]-y2[1])) - ((y2[2]-y2[1])*(x1[i]-x2[1])));
        vektorz3 = (((x2[0]-x2[2])*(y1[i]-y2[2])) - ((y2[0]-y2[2])*(x1[i]-x2[2])));
        znak1 = (vektorz1 > 0);
        znak2 = (vektorz2 > 0);
        znak3 = (vektorz3 > 0);
        zero1 = (vektorz1 = 0);
        zero2 = (vektorz2 = 0);
        zero3 = (vektorz3 = 0);
        if (!(zero1 || zero2 || zero3) && ((znak1 == znak2) && (znak1 == znak3))) return true;
    };
    return false;
};

Добавлено через 3 минуты
можно немного дополнить и будет отлавливать случаи когда один треугольник внутри другого, но при этом его вершины находится на сторонах описаного треугольника

@AleksRazgul · 17.12.2014, 03:09

варианты

@_Ivana · 17.12.2014, 03:15

я лохЪ. Посмотрел на картинки и понял, что в моем случае функция выдаст "нет", если один треугольник будет лежать внутри другого

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

@_20_ · 17.12.2014, 03:28 **[ТС]**

А чем Вам мой не нравиться (честно стянутый с алголиста)? Есть ли какие - нибудь недостатки? (33 пост).

@AleksRazgul · 17.12.2014, 04:21

_20_, он не нравится тем что спрятан под спойлер

. А если серьезно хотелось бы узнать что за функция isPointInclude?

@_20_ · 18.12.2014, 10:59 **[ТС]**

Вот она (весь код целиком):

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
    bool SN6::isPointInclude(int x, int y){
        SN6 t = *this;
        if (       (t.x1 - t.x2) * (y - t.y2) - (x - t.x2) * (t.y1 - t.y2) < 0
                && (t.x2 - t.x3) * (y - t.y3) - (x - t.x3) * (t.y2 - t.y3) < 0
                && (t.x3 - t.x1) * (y - t.y1) - (x - t.x1) * (t.y3 - t.y1) < 0)
            return true;
        else
            return false;
    }
 
    bool SN6::operator ==(SN6 t){
        return t.x1 == this->x1 && t.y1 == this->y1 && t.x2 == this->x2 && t.y2 == this->y2 && t.x3 == this->x3 && t.y3 == this->y3;
    }
 
    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;
    }

Добавлено через 3 минуты
Проверяет, находится ли точка внутри треугольника.

@AleksRazgul · 18.12.2014, 13:59

_20_, функция работает не во всех случаях.

. Для неё есть важное условие вершины треугольника должны быть перечислены против часовой стрелки.

@AleksRazgul · 18.12.2014, 14:08

Можете сами посмотреть:

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
struct Triangle
{
    float x1;
    float y1;
    float x2;
    float y2;
    float x3;
    float y3;
};
 
bool InOrOut(Triangle* t, float x, float y)
{
    if ((t->x1 - t->x2) * (y - t->y2) - (x - t->x2) * (t->y1 - t->y2) < 0
        && (t->x2 - t->x3) * (y - t->y3) - (x - t->x3) * (t->y2 - t->y3) < 0
        && (t->x3 - t->x1) * (y - t->y1) - (x - t->x1) * (t->y3 - t->y1) < 0)
        return true;
    else return false;
}
 
int main()
{
    Triangle ltriangle;
    ltriangle.x1 = -1;
    ltriangle.y1 = -1;
    ltriangle.x2 = 3;   //с этими работает
    ltriangle.y2 = -1;  // правильно внутри
    ltriangle.x3 = 2;   //
    ltriangle.y3 = 2;   //
//  ltriangle.x2 = 2;   //с этими не работает (поменяли вершины местами)
//  ltriangle.y2 = 2;   // выдает снаружи (а должно быть внутри)
//  ltriangle.x3 = 3;   //
//  ltriangle.y3 = -1;  //
 
    bool lresult = InOrOut(&ltriangle, 2, 1);
    if (lresult) cout<<"In"<<endl;
    else cout<<"Out"<<endl;
    system("pause");
};

@Данг · 29.10.2017, 15:48

А можно комменты в коде как-нибудь восстановить? Очень поможете

Новые блоги и статьи Все статьи Все блоги /
Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .

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

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

@AleksRazgul 35 / 17 / 10 Регистрация: 13.12.2014 Сообщений: 107
	17.12.2014, 03:09
	варианты Изображения 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	17.12.2014, 03:15
	я лохЪ. Посмотрел на картинки и понял, что в моем случае функция выдаст "нет", если один треугольник будет лежать внутри другого Надо добавить проверку этого условия по или к моей функции, выдающей факт пересечения каких-либо сторон. 0

@_20_ 22 / 56 / 9 Регистрация: 29.09.2011 Сообщений: 618
	17.12.2014, 03:28 [ТС]
	А чем Вам мой не нравиться (честно стянутый с алголиста)? Есть ли какие - нибудь недостатки? (33 пост). 1

@AleksRazgul 35 / 17 / 10 Регистрация: 13.12.2014 Сообщений: 107
	17.12.2014, 04:21
	_20_, он не нравится тем что спрятан под спойлер . А если серьезно хотелось бы узнать что за функция isPointInclude? 0

@AleksRazgul 35 / 17 / 10 Регистрация: 13.12.2014 Сообщений: 107
	18.12.2014, 13:59
	_20_, функция работает не во всех случаях. . Для неё есть важное условие вершины треугольника должны быть перечислены против часовой стрелки. Изображения 0

@Данг 0 / 0 / 0 Регистрация: 20.12.2015 Сообщений: 5
	29.10.2017, 15:48
	А можно комменты в коде как-нибудь восстановить? Очень поможете 0