Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 16.07.2014, 14:47   #1
Gector
Легенда
 
Аватар для Gector
 
Регистрация: 14.10.2007
Сообщений: 3,878
Написано 2,012 полезных сообщений
(для 5,072 пользователей)
Проверка пересечения треугольника и прямоугольника

Простая задача. Нужно определить есть ли пересечение треугольника с прямоугольником.
В сети все советы сводятся к одному алгоритму:
1) Проверка принадлежности точек треугольника прямоугольнику.
2) Проверка пересечения сторон если первое действие не дало результатов.

Но тут у возник вопрос - а нет ли более упрощенного и менее затратного по вычислениям способа? Само собой не обязательно исключать первый пункт, но можно ли обойтись без поиска пересечений по всем 12 отрезкам? Вопрос скорее по оптимизации. Первый вариант алгоритма я уже решил. Но перед тем как делать лучше узнать о более простых способах.
(Offline)
 
Ответить с цитированием
Старый 16.07.2014, 14:56   #2
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: Проверка пересечения треугольника и прямоугольника

если проекции фигур вдоль всех сторон пересекаются - есть пересечение.
__________________
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо SBJoker за это полезное сообщение:
Gector (16.07.2014), Igor (17.07.2014), Samodelkin (16.07.2014)
Старый 16.07.2014, 15:13   #3
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Проверка пересечения треугольника и прямоугольника

Хотя удобнее фигуры проецировать на нормали к сторонам.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Gector (16.07.2014)
Старый 16.07.2014, 15:23   #4
Gector
Легенда
 
Аватар для Gector
 
Регистрация: 14.10.2007
Сообщений: 3,878
Написано 2,012 полезных сообщений
(для 5,072 пользователей)
Ответ: Проверка пересечения треугольника и прямоугольника

Сообщение от SBJoker Посмотреть сообщение
если проекции фигур вдоль всех сторон пересекаются - есть пересечение.
http://noregret.org/tutor/n/collision/#2
Что-то из этого способа я нашел здесь.
Хотя как мне кажется способ ничуть не менее затратный.
(Offline)
 
Ответить с цитированием
Старый 16.07.2014, 15:31   #5
Nikich
Бывалый
 
Регистрация: 22.12.2011
Сообщений: 844
Написано 150 полезных сообщений
(для 275 пользователей)
Ответ: Проверка пересечения треугольника и прямоугольника

Способ вообще не затратный.
Сразу проверяй твои фигуры по Bounding box'ам. Очевидно, что если коллизии там не будет, то фигуры не касаются друг друга. В противном случае, юзай SAT( то, что ты нашел на сайте).
А если на это дело ещё натянуть какой-нибудь quadtree, работать будет моментально.
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо Nikich за это полезное сообщение:
Gector (16.07.2014), St_AnGer (16.07.2014)
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 13:05.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com