Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Алгоритм  (Прочитано 13935 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mfcer__
Команда клуба

ru
Offline Offline

« : 28-08-2006 08:40 » 

Задан прямоугольник №1 двумя точками
(minX, minY) и (maxX, maxY)

Таким же образом заданы еще несколько десятков прямоугольников

Каким образом можно найти прямоугольники с которыми пересекается или которых содержит внутри себя прямоугольник №1?

прямоугольники определены как на положительной так и на отрицательных осях
необходимо придумать условия для всех случаев  Не понял желательно используя только условия без вычисления других координат прямоугольников, то есть используя только minX, minY, maxX, maxY
Записан
Alf
Гость
« Ответ #1 : 28-08-2006 08:43 » 

Надо полагать, стороны прямоугольников параллельны осям координат?
« Последнее редактирование: 28-08-2006 08:44 от Alf » Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #2 : 28-08-2006 09:02 » 

да, забыл написать в условиях  Да-да

также
(minX, minY) и (maxX, maxY)

проще их назвать
(x1, y1) и (x2, y2)

могут ввести в заблуждения (это просто две точки первая определяет точку верхнуюю слева, а вторая нижнию справа, то что они min и max для осей координат верно не всегда)
« Последнее редактирование: 28-08-2006 09:19 от Mfcer__ » Записан
Alf
Гость
« Ответ #3 : 28-08-2006 09:42 » 

Тогда все совсем просто.

Предположим, что координаты углов первого прямоугольника X1min, Y1min, X1max и Y1max. Для второго аналогично.

Тогда проверка, лежит ли второй полностью внутри первого, выглядит так:

Код:
(X2min > X1min) & (X2max < X1max) & (Y2min > Y1min) & (Y2max < Y1max)

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

Код:
(X2max < X1min) | (X2min > X1max) | (Y2max < Y1 min) | (Y2min > Y1max)

Если оба условия ложны, прямоугольники пересекаются.
« Последнее редактирование: 28-08-2006 09:46 от Alf » Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #4 : 28-08-2006 09:57 » 

спасибо !!!  Класс!
будет ли это правильным если координаты отрицательные и если вдаваться в конретику координаты это широта и долгота?
« Последнее редактирование: 28-08-2006 10:00 от Mfcer__ » Записан
Alf
Гость
« Ответ #5 : 28-08-2006 10:54 » 

Широта и долгота роли не играют, знак координат - тоже. Особенно если использовать проекцию.В которой меридианы и параллели взаимно ортогональны. Если мне не изменяет память, этопроекция Меркатора, но надо в Яндексе посмотреть.

Вообще, наверное, нагляднее будет набросать рисунок, который я представлял себе, выписывая условия:



Первое условие соответствует случаю, когда второй прямоугольник целиком лежит в области 0, т.е. его левый нижний угол правее и выше левого нижнего угла первого прямоугольника, а верхний правый - ниже и левее.

Второе условие разделяется на несколько подусловий:

(X2max < X1min) - второй прямоугольник полностью левее первого, т.е. находится в областях 1, 2, 3;
(X2min > X1max) - второй прямоугольник полностью правее (5, 6, 7);
(Y2max < Y1 min) - второй прямоугольник ниже (1, 7, 8 );
(Y2min > Y1max) - второй прямоугольник выше (3, 4, 5).

Любого из этих подусловий достаточно, чтобы прямоугольники не пересекались и не лежали один внутри другого.

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

* Rect.gif (4.98 Кб - загружено 1621 раз.)
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 28-08-2006 13:15 » 

В случае долготы и широты надо учитывать, что "земля круглая" и аккуратно определить, что означает задание прямоугольника значениями крайними значениями долготы и широты.  Из-за того, что земля круглая, есть ДВА прямоугольника, задаваемых двумя парами (широта, долгота) - один "внутренний" (обозначенный на рисунке Альфа цифрой 0), а другой "внешний", который получается вырезанием из сферы "внутреннего" четырёхугольника.

По этой причине в геодезии любая фигура определяется как поверхность, расположенная по правую руку от контура, заданного последовательным перечислением всех вершин.  В каком порядке обходятся вершины прямоугольника в поставленной задаче?

* Internal.jpg (12.14 Кб - загружено 912 раз.)
* External.jpg (12.05 Кб - загружено 965 раз.)
« Последнее редактирование: 28-08-2006 13:18 от npak » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #7 : 28-08-2006 13:32 » 

 Не понял

не знаю, в такой же в какой возвращают данные Google Maps или Yahoo Maps
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 28-08-2006 16:53 » 

А где этот формат описан?
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #9 : 16-09-2006 19:41 » 

спасибо за помощь,

однако в самом начале я немного ступил Жаль

дело в том что широту и долготу нельзя рассматривать как прямоугольную систему координат

так как это вообще углы Улыбаюсь

причем в примере выше

minX, maxX могут принимать значения
0 до 180, после 180 идет -180 а потом опять 0

minY, maxY могут принимать значения
от 0 до 90, после 90 идет -90 а потом опять 0

то есть все замкнуто и идет по кругу
точки располагаются как показаны на рисунку Alf'a

это и есть в принципе формат

как можно адаптировать алгоритм который посоветовал Alf (за что отдельное спасибо) к таким системам координат?
« Последнее редактирование: 18-12-2007 21:44 от Алексей1153++ » Записан
Alf
Гость
« Ответ #10 : 16-09-2006 20:15 » 

Что касается долготы, тут должно быть довольно просто. При переходе через меридиан 180 градусов мы можем произвести преобразование координат таким образом, чтобы избежать отрицательных значений: продолжать отсчет в том же направлении - 190, 200 и так далее.

С широтой дело посложнее. Может оказаться, что все 4 точки лежат на одной широте, и тогда "прямоугольник" выродится на карте в линию, совпадающую с одной из параллелей.

Тут нужно посмотреть специфику задачи, может ли в ней встретиться такая ситуация. Например, если речь идет о карте сухопутной части России, то такие предосторожности излишни. А если велика вероятность того, что один из полюсов окажется внутри области, придется ее учитывать.
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #11 : 16-09-2006 20:30 » 

в линию ни при каком случае прямоугольник выродиться не сможет (просто это ошибка при вводе данных по условию)
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #12 : 17-09-2006 05:56 » 

При работе с замкнутыми пространствами каждые вырезанный "кусок" обозначает всегда две области. Одну из них условно считают внутренней, а другую - внешней. Вот в этом и проблема: какую область считать внутренней, а какую внешней.

Предлагаю меньшую по площади считать внутренней (искомый "прямоугольник"), а также не забыть случай равенства внешней и внутренней областей.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 25-09-2006 16:37 » new

Если внутрь фигуры попадает полюс, то она превращается в "восьмёрку" - меридианы, составляющие границы фигуры, пересекаются.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines