Форум: "Потрепаться";
Текущий архив: 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