Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 2004.09.05;
Скачать: [xml.tar.bz2];

Вниз

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

 
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 раз. Как только результат будет разный - пересекаются.


 
Igorek ©   (2004-08-16 10:11) [14]

Таким образом задача сводится к определению:
"Находится ли точка внутри прямоугольника?"
Решается просто:
Пусть есть прямоугольник 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)

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


 
Думкин ©   (2004-08-16 10:13) [15]

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

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


 
Igorek ©   (2004-08-16 10:53) [16]


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

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


 
Думкин ©   (2004-08-16 10:56) [17]

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

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


 
Igorek ©   (2004-08-16 11:22) [18]


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

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

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


 
Думкин ©   (2004-08-16 11:31) [19]

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

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

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


Ну, что же.

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

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

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

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



Страницы: 1 вся ветка

Форум: "Потрепаться";
Текущий архив: 2004.09.05;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.5 MB
Время: 0.027 c
1-1093026733
Makssim
2004-08-20 22:32
2004.09.05
Как программно получить время?


14-1092812751
Мюмзик в мове
2004-08-18 11:05
2004.09.05
нужны словари


1-1093003639
kukuikar
2004-08-20 16:07
2004.09.05
Я изменил Dialogs.pas. Как мне переделать Dialogs.dcu?


11-1080408399
Михаил
2004-03-27 20:26
2004.09.05
Класс Pstrlist


14-1092902502
Rem
2004-08-19 12:01
2004.09.05
Кто что думает по поводу...





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский