Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > разработка игр, графический дизайн и моделирование > Gamedev - cоздание игр: Unity, OpenGL, DirectX
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 30.11.2011, 00:24   #1
Trinock
Пользователь
 
Регистрация: 19.09.2011
Сообщений: 21
По умолчанию Нужно найти алгоритм для пересечения отрезка с набором прямоугольников

Здравствуйте, задача состоит в следующем: есть направленный отрезок, который задается в 2d пространстве координата своих точек {(x1, y1), (x2, y2)}. Пространство разбивается на прямоугольные клетки, у каждой есть свой номер. Имея координаты концов отрезка нужно узнать, через какие клетки он проходит. Помогите найти алгоритм, решающий такую задачу, думаю задача довольно распространненая и не хотелось бы изобретать велосипед.
Trinock вне форума Ответить с цитированием
Старый 01.12.2011, 06:52   #2
Kostia
Участник клуба
 
Аватар для Kostia
 
Регистрация: 21.11.2007
Сообщений: 1,691
По умолчанию

Можно легко рассчитать номера(координаты) клеток в которые попали концы отрезка, а потом уже рассчитать клетки, которые находятся между. Для этого алгоритм рисования линии пригодится, помню в книжке DirectX и Delphi Фленов приводил алгоритм как попикселям в DirectDarw нарисовать отрезок.
Просто само название алгоритма не помню, если оно вообще есть )))
Kostia вне форума Ответить с цитированием
Старый 01.12.2011, 09:12   #3
Виталий Желтяков
Старожил
 
Аватар для Виталий Желтяков
 
Регистрация: 19.04.2010
Сообщений: 2,702
По умолчанию

Если будет разделение на клетки, то нужно использовать алгоритм А*.
Виталий Желтяков вне форума Ответить с цитированием
Старый 01.12.2011, 11:21   #4
invizor
Пользователь
 
Аватар для invizor
 
Регистрация: 15.11.2010
Сообщений: 53
По умолчанию

Астар это вообще если препятствия есть, хотя может в какой-нибудь книжке и быть описан. Но думаю тут "велосипед изобрести" быстрее:
Предположим что прямоугольники параллельные по x и y и одинаковые.
h[i] это система горизонтальных линий прямоугольника, v[i]- система вертикальных, массивы начинаются в клетке начала отрезка заканчиваются в клетке на конце. Ищем пересечения отрезка с вертикальнами и горизонтальными прямыми (уравнение y=(y2-y1)/(x2-x1)-y2*x1-y1*x2 и вместо x или y подставляются v[i] и h[i]).
Если есть пересечения, записываем в is_v[i] и is_h[i] 1 иначе записываем 0,
пусть есть матрица matr (1 при наличии пересечения 0 при отсутствии), 1 получается тогда и только тогда, когда есть пересечение с двумя отрезками прямоугольника и в прямоугольниках границ отрезка.(для matr[i,j] это v[i],v[i+1],h[i],h[i+1] а также matr[0,0],matr[m,n])
Герои меча и магии собственного производства http://invizor007.000webhostapp.com/...1/hi_v1_3a.rar
Личный сайт http://invizor007.000webhostapp.com/
invizor вне форума Ответить с цитированием
Старый 01.12.2011, 14:31   #5
Trinock
Пользователь
 
Регистрация: 19.09.2011
Сообщений: 21
По умолчанию

Спасибо за помощь, попробую разные варианты.
Trinock вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача на пересечения прямоугольников.желательно экстренно. Llein Паскаль, Turbo Pascal, PascalABC.NET 2 27.10.2011 19:21
Алгоритм подсчета количества точек пересечения отрезков juliaaaa Помощь студентам 2 24.02.2011 19:58
Нужно найти координаты точки пересечения двух отрезков в пространстве... Dima6120 Мультимедиа в Delphi 2 30.07.2010 13:36
Нужно найти ошибку или написать алгоритм по проще! (строки) velamut Помощь студентам 3 18.06.2010 16:09