Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.82/65: Рейтинг темы: голосов - 65, средняя оценка - 4.82
22 / 56 / 9
Регистрация: 29.09.2011
Сообщений: 618

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

14.12.2014, 03:24. Показов 13494. Ответов 49
Метки нет (Все метки)

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

Подойдёт ли мне алгоритм, описаный здесь:
Пересечение треугольников в 3d (пятый пост)?
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
14.12.2014, 03:24
Ответы с готовыми решениями:

Пересечение треугольников
Здравствуйте! Подскажите, пожалуйста, как узнать пересекается треугольник или нет с другими треугольниками. Вот данные: struct...

Пересечение треугольников
Здравствуйте, задумался над такой задачей: Проверить пересекаются ли 2 треугольника. 6 координат задаются пользователем (именно с...

Пересечение треугольников в 3d
Вот например 2 треугольника: (для примера) struct Point { int X; int Y; int Z; };

49
35 / 17 / 10
Регистрация: 13.12.2014
Сообщений: 107
14.12.2014, 03:35
А вам в пространстве надо? или на плоскости?
1
22 / 56 / 9
Регистрация: 29.09.2011
Сообщений: 618
14.12.2014, 04:50  [ТС]
на плоскости
0
 Аватар для D_in_practice
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
14.12.2014, 05:43
Цитата Сообщение от _20_ Посмотреть сообщение
Наличие общей грани нельзя считать пересечением
Это условие особый геморой, с ним программа сильно вырастет.
Без него:
Если хоть одна точка попала внутрь другого т-ка, то они пересекаются.
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
#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);
}
 
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 = 4; b[0].y = 4;
    b[1].x = 5; b[1].y = 1;
    b[2].x = 1; b[2].y = 0;
    
    double sa = s_n(a, 3);//ïëîùàäü ïåðâîãî òðåóãîëüíèêà
    
    int flag = 0;
    for (int i = 0; i < 3; ++i){//òî÷êà âòîðîãî êîòîðóþ áåðåì
        
        double sum = 0;
        for (int j = 0; j < 3; ++j){//òî÷êà ïåðâîãî òð-êà êîòîðóþ íå áåðåì
            
            D_Point c[3];
            for (int k = 0; k < 3; ++k)
                if (k == j)
                    c[k] = b[i];
                else
                    c[k] = a[k];
            
            double sc = s_n(c, 3);//ïëîùàäü íîâîãî òðåóãîëüíèêà
            
            sum += sc;
        }
        
        if (fabs(sa - sum) < EPS){//çíà÷èò òî÷êà âíóòðè òðåóãîëüíèêà
            flag = 1;
            break;
        }
    }
    
    cout << flag << endl;
}
1
22 / 56 / 9
Регистрация: 29.09.2011
Сообщений: 618
14.12.2014, 12:45  [ТС]
Цитата Сообщение от _20_
Наличие общей грани нельзя считать пересечением
К сожалению, это условие попустить нельзя.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
14.12.2014, 12:59
Цитата Сообщение от _20_ Посмотреть сообщение
Надо определить, пересекаются ли треугольники. Наличие общей грани нельзя считать пересечением, но если один треугольник лежит внутри другого, то это пересечение.
Либо треугольники совпадают, либо вершина одного лежит внутри другого, либо середина стороны одного лежит внутри другого, либо существуют пересекающиеся стороны, точка пересечения которых лежит внутри каждой стороны.
1
22 / 56 / 9
Регистрация: 29.09.2011
Сообщений: 618
14.12.2014, 15:19  [ТС]
То есть надо решать систему уравнений для всех сторон всех треугольников. Ещё остайтся возможность, что один лежит внутри другого. Может есть другой способ?
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
14.12.2014, 15:32
Цитата Сообщение от _20_ Посмотреть сообщение
Может есть другой способ?
есть
тупой цикл по трем сторонам, если хотя бы одна точка внутри, значит есть пересечение
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
14.12.2014, 15:42
Цитата Сообщение от _20_ Посмотреть сообщение
Ещё остайтся возможность, что один лежит внутри другого
Этот случай учтен в
Цитата Сообщение от Mr.X Посмотреть сообщение
середина стороны одного лежит внутри другого
Цитата Сообщение от ValeryS Посмотреть сообщение
если хотя бы одна точка внутри, значит есть пересечение
Вы какую точку имеете в виду? Если треугольники совпадают, то никакая точка никакой из сторон не внутри.
1
22 / 56 / 9
Регистрация: 29.09.2011
Сообщений: 618
14.12.2014, 15:57  [ТС]
2 ValeryS:
Вот здесь никакая вершина не лежит внутри другого трегольника, а пересечение есть.

И как же мне здесь картинку выложить, когда он ссылки цензурирует?
Даже с панели редактирования не получается.
Вот так сделаю, вмето пробела точка.
[cut]

2 Mr.X:
То есть, без решения СЛАУ никак?
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
14.12.2014, 16:03
Цитата Сообщение от _20_ Посмотреть сообщение
Вот здесь никакая вершина не лежит внутри другого трегольника, а пересечение есть.
И как же мне здесь картинку выложить, когда он ссылки цензурирует?
Добавлено через 5 минут
Даже с панели редактирования не получается.
Вот так сделаю, вмето пробела точка.
http://radikal ru/fp/6293c7f0465b43358d0d884fd4494ed0
Это учитывается случаем
Цитата Сообщение от Mr.X Посмотреть сообщение
либо существуют пересекающиеся стороны, точка пересечения которых лежит внутри каждой стороны.
1
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
14.12.2014, 16:13
Цитата Сообщение от Mr.X Посмотреть сообщение
Если треугольники совпадают, то никакая точка никакой из сторон не внутри.
этот случай не описан
Цитата Сообщение от _20_ Посмотреть сообщение
Наличие общей грани нельзя считать пересечением, но если один треугольник лежит внутри другого, то это пересечение.
ни один треугольник не лежит внутри другого, но в наличии три общих грани, пересечение или нет?
можно вынести в исключения
Цитата Сообщение от _20_ Посмотреть сообщение
Вот здесь никакая вершина не лежит внутри другого трегольника, а пересечение есть.
я разве говорил про вершины?
у "звезды Давида" все вершины снаружи, а пересечение есть
но при пересечении найдется точка которая лежит внутри другого треугольника
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
14.12.2014, 16:19
Цитата Сообщение от _20_ Посмотреть сообщение
2 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;

Добавлено через 4 минуты
Цитата Сообщение от ValeryS Посмотреть сообщение
этот случай не описан
Цитата Сообщение от _20_ Посмотреть сообщение
Наличие общей грани нельзя считать пересечением, но если один треугольник лежит внутри другого, то это пересечение.
ни один треугольник не лежит внутри другого, но в наличии три общих грани, пересечение или нет?
можно вынести в исключения
Ну, на самом деле автор пытался сформулировать мысль, что пересекаются треугольники, которые имеют общую точку, лежащую внутри обоих треугольников.
2
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
14.12.2014, 22:23
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, на самом деле автор пытался сформулировать мысль, что пересекаются треугольники, которые имеют общую точку, лежащую внутри обоих треугольников.
Может быть хотя автор об это умолчал у меня есть такая мысль что он сам не знает что такое
Пересечение треугольников
была бы тема в математике,я бы предложил(или нет) нормальное математическое/геометрическое решение
но поскольку в Си то тупой перебор, или я не прав
на самом деле это решается просто методом Монте-Карло, но мне леньа чем не устраивает мое решение, если хоть одна точка на стороне внутри другого треугольника, то имеет место пересечение,за исключением
Цитата Сообщение от Mr.X Посмотреть сообщение
Если треугольники совпадают,
Парируйте
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
14.12.2014, 22:33
Цитата Сообщение от ValeryS Посмотреть сообщение
на самом деле это решается просто методом Монте-Карло,
Ну, этот метод позволит найти пересечение с вероятностью, меньшей ста процентов.
Цитата Сообщение от ValeryS Посмотреть сообщение
а чем не устраивает мое решение, если хоть одна точка на стороне внутри другого треугольника, то имеет место пересечение,за исключением
Цитата Сообщение от Mr.X Посмотреть сообщение
Если треугольники совпадают,
Парируйте
Ну, этих точек бесконечно много, а мы в силах проверить только их счетное подмножество. Нужная может в него не попасть.
1
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
14.12.2014, 22:45
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, этих точек бесконечно много,
С какого перепугу
отрезок есть массив конечных точек, следовательно он сам конечен
шесть отрезков есть тоже конечная величина
почему бесконечность?
нет я догадываюсь что точка есть субстанция которая не имеет размеров, и с этой точки зрения отрезок есть бесконечный массив точек, но мы то находимся все таки в С++ а не в математике, и для нас точка есть конкретная величина, допустим пиксель
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
14.12.2014, 22:51
Цитата Сообщение от ValeryS Посмотреть сообщение
С какого перепугу
отрезок есть массив конечных точек, следовательно он сам конечен
шесть отрезков есть тоже конечная величина
почему бесконечность?
нет я догадываюсь что точка есть субстанция которая не имеет размеров, и с этой точки зрения отрезок есть бесконечный массив точек, но мы то находимся все таки в С++ а не в математике, и для нас точка есть конкретная величина, допустим пиксель
Ваши высказывания малость неадекватные, поэтому не рискну продолжать дискуссию.
0
22 / 56 / 9
Регистрация: 29.09.2011
Сообщений: 618
14.12.2014, 23:20  [ТС]
Цитата Сообщение от ValeryS Посмотреть сообщение
была бы тема в математике,я бы предложил(или нет) нормальное математическое/геометрическое решение
но поскольку в Си то тупой перебор, или я не прав
Хотите ли Вы сказать, что информатики глупее математиков и соершенно не заморачиваются ускорением своих алгоритмов?
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
14.12.2014, 23:36
Цитата Сообщение от _20_ Посмотреть сообщение
Хотите ли Вы сказать,
Цитата Сообщение от Mr.X Посмотреть сообщение
Ваши высказывания малость неадекватные,
критерий истины есть практика, и посему я умолкаю пока не напишу код который
Цитата Сообщение от ValeryS Посмотреть сообщение
тупой цикл по трем сторонам,
лучше или хуже он будет я не знаю, но то что он будет действенным на 100% я уверен

Добавлено через 2 минуты
Цитата Сообщение от _20_ Посмотреть сообщение
Хотите ли Вы сказать, что информатики глупее математиков
глупость несусветная,
решения конкретные и абстракнтныя, ничто не напоминает
1
22 / 56 / 9
Регистрация: 29.09.2011
Сообщений: 618
14.12.2014, 23:54  [ТС]
Цитата Сообщение от ValeryS Посмотреть сообщение
и посему я умолкаю пока не напишу код который
Сообщение от ValeryS
тупой цикл по трем сторонам,
лучше или хуже он будет я не знаю, но то что он будет действенным на 100% я уверен
То есть у вас есть алгоритм, но Вы его никому не покажете? Ералаш напомнило, когда одного школьника хотели расстрелять за то, что он не говорил, сколько будет 7х8.
Вот здесь есть алгоритм:
http://algolist.manual.ru/math... line2d.php
Цитата Сообщение от ValeryS Посмотреть сообщение
Сообщение от _20_
Хотите ли Вы сказать, что информатики глупее математиков
глупость несусветная,
Получается, что Вы уже сами сомневаетесь, что Вы хотели сказать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.12.2014, 23:54
Помогаю со студенческими работами здесь

Определить пересечение треугольников
Помогите определить пересечение треугольников уже неделю сижу class Point { public: float x, y; Point(float _x = 0, float _y =...

Как определить пересечение 2-х треугольников в трехмерном пространстве?
Собсно сабж) Какие есть идеи?

Дано н прямоугольных треугольников с а и б катетами, причем а + б = 9. Составить программу, которая вычисляет суммарную площадь этих треугольников
Дано н прямоугольных треугольников с а и б катетами, причем а + б = 9. Составить программу, которая вычисляет суммарную площадь этих...

Пересечение двух прямых и проверка на пересечение
Доброго времени суток слизал функцию проверки отсюда:/segments_intersection_checking на всякий случай у меня она выглядит так: int...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
модель ЗдравоСохранения 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. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru