|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
04.08.2013, 05:48
|
#1
|
Нуждающийся
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений (для 8 пользователей)
|
Пересечение двух прямоугольников на одной плоскости
Всем привет Возникла нужда в создании данной функции.
Есть допустим два прямоугольника
они естественно на одной плоскости и стороны параллельны друг другу.
Интересует сам алгоритм проверки пересечения.
Пробовал сам ,выходит довольно криво..
Координаты используются такие
(x,y,x2,y2)
x,y - координаты откуда начинается прямоугольник.
x2,y2 - не ширина и высота,это конечные координаты
Надеюсь поможете мне
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
|
(Offline)
|
|
04.08.2013, 07:09
|
#2
|
ПроЭктировщик
Регистрация: 28.11.2012
Сообщений: 171
Написано 113 полезных сообщений (для 317 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Тут был херовый алгоритм
UPD: Вот например - http://tekpool.wordpress.com/2006/10...-other-or-not/ (warning, там в очевидных местах парсером пропущены символы сравнения)
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
04.08.2013, 08:00
|
#3
|
Нуждающийся
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений (для 8 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Спасибо правда было бы более понятно в "паскалевидном" коде..просто не разобрался
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
|
(Offline)
|
|
04.08.2013, 08:05
|
#4
|
ПроЭктировщик
Регистрация: 28.11.2012
Сообщений: 171
Написано 113 полезных сообщений (для 317 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Код, который я написал, не учитывал ситуации, когда второй прямоугольник полностью внутри первого.
|
(Offline)
|
|
04.08.2013, 08:22
|
#5
|
Нуждающийся
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений (для 8 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
такой не сложно вроде написать,но мне нужно что бы даже если стороной касается то возвращает true написать функцию..вроде накидал да не работает
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
|
(Offline)
|
|
04.08.2013, 08:34
|
#6
|
Нуждающийся
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений (для 8 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Сделал так:
Имеются
x1,y1 - левый верхний угол первого прямоугольника
x2,y2 - правый нижний угол первого прямоугольника
ax1,ay1 - левый верхний угол второго прямоугольника
ax2,ay2 - правый нижний угол второго прямоугольника
If (ax1<=x2 AND ax1=>x1 AND ay1=>y1 AND ay1<=y2) Then hit=true
If (ax1<=x2 AND ax1=>x1 AND ay2>=y1 AND ay2<=y2) Then hit=true
If (ax2=>x1 AND ax2<=x2 AND ay1=>y1 AND ay1<=y2) Then hit=true
If (ax2=>x1 AND ax2<=x2 AND ay2>=y1 AND ay2<=y2) Then hit=true
Не работает...чтото я не догоняю
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
|
(Offline)
|
|
04.08.2013, 21:22
|
#7
|
Модератор
Регистрация: 03.04.2007
Сообщений: 2,252
Написано 597 полезных сообщений (для 817 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Может быть не самый оптимальный, но наиболее очевидный путь - проверить каждую вершину каждого прямоугольника на попадание в другой прямоугольник. Если будет хотя бы одно попадание, значит прямоугольники пересекаются.
Оптимизация:
1. Сделать так, чтобы x всегда был больше x2 и y всегда был больше y2 (алгоритм будет гораздо проще и быстрее);
2. Не обязательно проверять все вершины, достаточно проверять до первого попадания.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
05.08.2013, 06:09
|
#8
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,361
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Function RectsOverlap:Bool(x1:Float, y1:Float, w1:Float, h1:Float, x2:Float, y2:Float, w2:Float, h2:Float)
If x1 > (x2 + w2) Or (x1 + w1) < x2 Then Return False
If y1 > (y2 + h2) Or (y1 + h1) < y2 Then Return False
Return True
End Function
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 4090 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
05.08.2013, 06:48
|
#9
|
Элита
Регистрация: 14.06.2008
Адрес: Украина, Киев
Сообщений: 2,273
Написано 754 полезных сообщений (для 1,833 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Вы чо, серьёзно обсуждаете решение этой задачи? Тут же даже никакой тригонометрии не надо, тупо сравнить координаты, как вы выше и написали.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
06.08.2013, 17:16
|
#10
|
Нуждающийся
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений (для 8 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Всем спасибо) я в своем коде по убирал знаки равно,добавил проверку ровного попадания одинаковый прямоугольников и "один внутри другого"
Конечно не самый производительный вариант,Но пока так
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
|
(Offline)
|
|
06.08.2013, 17:22
|
#11
|
Нуждающийся
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений (для 8 пользователей)
|
Ответ: Пересечение двух прямоугольников на одной плоскости
Randomize, спасибо,твой вариант выполняется в разы быстрее! (что неудивительно) я его переделал т.к. мне нужны не ширина и высота а точные координаты правого нижнего угла,что бы не мучаться не вычислять перед выполнением
Памятник таким)
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 04:51.
|