Геометрическая задача

← →
vidiv © (2004-08-15 10:03) [0]

На плоскости есть два прямоугольника. Каждый задан координатами всех вершин (для удобства). Стороны прямоугольника могут находиться под любым углом относительно осей координат (свободно размещены). Требуется выяснить пересекаются ли эти прямоугольники. У кого какие соображения на эту тему есть?

← →
YurikGL © (2004-08-15 10:16) [1]

1) Для любого из прямоугольников смотрим, как лежат точки другого внутри или вне. Если хотя бы одна вне, а остальные внутри или наоборот - пересекаются
2) Проверить на пересечение попарно все отрезки из разных прямоугольников

← →
Alx2 © (2004-08-15 10:17) [2]

>vidiv © (15.08.04 10:03)
CombineRgn с флагом RGN_AND и проверкой возвращаемого значения на NULLREGION?
Или нужно именно решение "на бумаге"?

← →
vidiv © (2004-08-15 11:18) [3]

вообще надо просто с таблицы mysql выбрать все прямоугольники которые пересекаются с данным. покачто метод YurikGL самый очевидный, но очень грамоздкий. Может есть какието другие хитрости?

← →
Думкин © (2004-08-15 12:21) [4]

Да, для вершин достаточно лежит ли хоть одна внутри у другого(или наоборот).
А с отрезками - если один целиком во втором?

← →
YurikGL © (2004-08-15 12:23) [5]

> Думкин © (15.08.04 12:21) [4]

> А с отрезками - если один целиком во втором?

Орезки проверяются не пересечение по принципу каждый из первого прямоугольника с каждым из второго. Если прямоугольники будут один в другом то и пересекаться отрезки не будут.

← →
Думкин © (2004-08-15 14:43) [6]

> [5] YurikGL © (15.08.04 12:23)

И? Отрезки не будут, а вот фигуры - будут. Область пересечения - внутренний четырехугольник.

← →
YurikGL © (2004-08-15 14:54) [7]

> Думкин © (15.08.04 14:43) [6]

Я по пересечением прямоугольников понял пересечение их сторон, а не площадей. :)

← →
марсианин © (2004-08-15 20:41) [8]

2 прямоугольника, координаты вершин 1-го -- (x1,y1) .... (x4,y4) - по кругу

второго -- (X1,Y1) .... (X4,Y4)

function IsIntersect(a1,a2,b1,b2:Double):boolean; // персекаются ли 2 отрезка (a1,a2) и (b1,b2)на числовой прямой? begin return ( ( (b1 >= min(a1,a2)) AND (b1 <= max(a1,a2)) ) OR ( (b2 >= min(a1,a2)) AND (b2 <= max(a1,a2)) ) OR ( (a1 >= min(b1,b2)) AND (a1 <= max(b1,b2)) ) OR ( (a2 >= min(b1,b2)) AND (a2 <= max(b1,b2)) ) ) end; //основной код d = sqtr(sqr(x1-x2)+sqr(y1-y2)); c = (x2 - x1)/d //cos s = (y2 - y1)/d //sin a1 = x1*c + y1*s; a2 = x2*c + y2*s; b1 = - x3*s + y3*c; b2 = - x2*s + y2*c; A1 = MIN(X1*c + Y1*s, X2*c + Y2*s, X3*c + Y3*s, X4*c + Y4*s); A2 = MAX(X1*c + Y1*s, X2*c + Y2*s, X3*c + Y3*s, X4*c + Y4*s); B1 = MIN( - X1*s + Y1*c, - X2*s + Y2*c, - X3*s + Y3*c, - X4*s + Y4*c); B2 = MAX( - X1*s + Y1*c, - X2*s + Y2*c, - X3*s + Y3*c, - X4*s + Y4*c); return (IsIntersect(a1,a2,A1,A2) AND IsIntersect(b1,b2,B1,B2)); потом тестируем таким же образом первый прямоугольник относит. второго если ОБЕ проверки вернули true - пр-ки персекаются
этот код не проверял, должно работать...
как-то писал нечто подобное для параллепипедов в 3Д - работало

смысл - фактически переходим в с.к., где оси параллельны сторонам одного пр-ков

← →
Romkin © (2004-08-15 20:55) [9]

div © (15.08.04 11:18) [3] Угу. Здесь все-таки не два прямоугольника :)
Когда идет большая выборка (я так подозреваю), полезно сузить рамки. А это легко сделать методом "бегущей прямой" и похожими.
Я бы сделал вспомогательные таблицы, вот только на MySQL их поддерживать трудно :(
Идея в том, чтобы предварительно максимально сузить выборку, в один или несколько приемов. Ведь если минимальные координаты по x & y одного прямоугольника больше максимальных другого - они явно не пересекаются. А запросом это выяснить можно, если есть таблица минимальных и максимальных координат ;)

← →
vidiv © (2004-08-16 08:41) [10]

> Romkin © (15.08.04 20:55) [9]

Проблема не с MySQL, а именно в методе определения условия: пересекаются или нет прямоугольники.

Если использовать метод пересечения всех сторон одного со всеми сторонами другого, то это получается 16 условий. Каждое условие тоже грамосткое: надо найти точку пересечения прямых и проверить лежит ли она на отрезках(т.е. проверяемых сторонах). Получается очень грамоздкое условие... Вся проблема в том чтобы его упростить

← →
Думкин © (2004-08-16 08:48) [11]

> [10] vidiv © (16.08.04 08:41)

Ты уже сутки маешься, неужели не ясно?
> [4] Думкин © (15.08.04 12:21)

Каждый прямоугольник дает 4 условия.
Проверяем на эти 4 условия 4 вершины другого и потом наоборот(если надо).
Если хотя бы одна вершина внутри другого - заканчиваем и говорим - да пересекаются.
Или - что под пересечением подразумевается? Но и тут - если все 4-е внутри - то пересечений сторон нет.

← →
int63 (2004-08-16 10:03) [12]

vidiv © (16.08.04 08:41) [10]

> Проблема не с MySQL, а именно в методе определения условия:
> пересекаются или нет прямоугольники.

Тогда см. [2]

← →
Igorek © (2004-08-16 10:10) [13]

1) Рекоммендую создать таблицу индексирования для факта пересечения.
2) Есть простые предусловия, выполнение которых даст ответ "не пересекаются":
- расстояние между центрами прямоугольников больше суммы половин диагоналей
- расстояние между центрами прямоугольников меньше такой величины: (меньшая сторона большего - полдиагонали меньшего).
3) Лучше все-таки проверять вершины одного на вхождение во второй. В виде ф-ции PtInRect(): Bool. Тогда ее вызываем от 1 до 4 раз. Как только результат будет разный - пересекаются.

Таким образом задача сводится к определению:
"Находится ли точка внутри прямоугольника?"
Решается просто:
Пусть есть прямоугольник ABCD и точка P.
Берем векторы AB, AD, AP.
Составляем уравнение AP=p*AB+k*AD.
Если точка Р внутри, то коефициенты p и k принадлежат диапазону (0..1).
Сами коефициенты находим так:
p = |AB| / AP1
k = |AB| / AP2
, где АР1, AP2 - длины со знаком проекций АР на АВ и AD.
Находим их так:
AP1 = |AP| * cos(BAP)
AP2 = |AP| * cos(DAP)

Ну а угол между тремя точками ты и сам найдешь (напр. возьми разность углов к коорд. оси Ох). :-)

> [13] Igorek © (16.08.04 10:10)

> Стороны прямоугольника могут находиться под любым углом относительно осей координат (свободно размещены).

> Думкин © (16.08.04 10:13) [15]
> > Стороны прямоугольника могут находиться под любым углом
> относительно осей координат (свободно размещены).

Ну да. Ну и что?

> [16] Igorek © (16.08.04 10:53)

> [13] Igorek © (16.08.04 10:10)
> 3) Лучше все-таки проверять вершины одного на вхождение
> во второй. В виде ф-ции PtInRect(): Bool.

> Думкин © (16.08.04 10:56) [17]
> > 3) Лучше все-таки проверять вершины одного на вхождение
> > во второй. В виде ф-ции PtInRect(): Bool.

Слушайте, я чего то не пойму. Что вы конкретно хотите? Что вам не нравится? С чем вы не согласны? Название функции? То что оно совпадает с названием АПИшной для прямоугольников со сторонами паралельними осям?

---
Я фигею с этих русских. Все намеками, поучениями, и вопросами на вопрос...

> [18] Igorek © (16.08.04 11:22)

Именно тем что совпадает.

> ---
> Я фигею с этих русских. Все намеками, поучениями, и вопросами
> на вопрос...

Ну, что же.

Ищущший звезды - найдет звезды
Ищущший дерьмо - найдет дерьмо

Каждвй находит то, чего ищет

= Иконку в system tray (где часы) вставляют функцией Shell_NotifyIcon =

Bye ...
Тенцер А.Л.(с)

Геометрическая задача Найти похожие ветки