forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Пересечение двух прямоугольников на одной плоскости (http://forum.boolean.name/showthread.php?t=18430)

MoteX 04.08.2013 05:48
Пересечение двух прямоугольников на одной плоскости
 
Всем привет:)Возникла нужда в создании данной функции.
Есть допустим два прямоугольника:)
они естественно на одной плоскости и стороны параллельны друг другу.
Интересует сам алгоритм проверки пересечения.
Пробовал сам ,выходит довольно криво..:dontknow:
Координаты используются такие
(x,y,x2,y2)
x,y - координаты откуда начинается прямоугольник.
x2,y2 - не ширина и высота,это конечные координаты
Надеюсь поможете мне:)

trq 04.08.2013 07:09
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Тут был херовый алгоритм

UPD: Вот например - http://tekpool.wordpress.com/2006/10...-other-or-not/ (warning, там в очевидных местах парсером пропущены символы сравнения)

MoteX 04.08.2013 08:00
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Спасибо:)правда было бы более понятно в "паскалевидном" коде..просто не разобрался :-D

trq 04.08.2013 08:05
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Код, который я написал, не учитывал ситуации, когда второй прямоугольник полностью внутри первого.

MoteX 04.08.2013 08:22
Ответ: Пересечение двух прямоугольников на одной плоскости
 
такой не сложно вроде написать,но мне нужно что бы даже если стороной касается то возвращает true написать функцию..вроде накидал да не работает

MoteX 04.08.2013 08:34
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Сделал так:
Имеются
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
Не работает...чтото я не догоняю

ViNT 04.08.2013 21:22
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Может быть не самый оптимальный, но наиболее очевидный путь - проверить каждую вершину каждого прямоугольника на попадание в другой прямоугольник. Если будет хотя бы одно попадание, значит прямоугольники пересекаются.
Оптимизация:
1. Сделать так, чтобы x всегда был больше x2 и y всегда был больше y2 (алгоритм будет гораздо проще и быстрее);
2. Не обязательно проверять все вершины, достаточно проверять до первого попадания.

Randomize 05.08.2013 06:09
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Код:
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

Phantom 05.08.2013 06:48
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Вы чо, серьёзно обсуждаете решение этой задачи? Тут же даже никакой тригонометрии не надо, тупо сравнить координаты, как вы выше и написали.

MoteX 06.08.2013 17:16
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Всем спасибо) я в своем коде по убирал знаки равно,добавил проверку ровного попадания одинаковый прямоугольников и "один внутри другого"
Конечно не самый производительный вариант,Но пока так:)

MoteX 06.08.2013 17:22
Ответ: Пересечение двух прямоугольников на одной плоскости
 
Randomize, спасибо,твой вариант выполняется в разы быстрее! (что неудивительно) я его переделал т.к. мне нужны не ширина и высота а точные координаты правого нижнего угла,что бы не мучаться не вычислять перед выполнением:)
Памятник таким)


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

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot