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

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

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

« : 25-04-2008 15:00 » 

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

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

Как это лучше сделать? Мне что-то не очень нравится каждый раз перебирать и обсчитывать весь массив. Может, подскажете каккую-нибудь другую организацию этого массива для уменьшения вычислений?

ЗЫ: реализовывать буду на C#.
Записан
RXL
Технический
Администратор

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

WWW
« Ответ #1 : 25-04-2008 16:35 » 

little,

1. Расстояние вычисляется между чем и чем? Между центрами, вершинами, любой точкой на стороне?

2. Перебирать все равно придется. Вариант оптимизации: создать индекс - упорядоченные предварительно вычисленные значения, по которым поиск будет делатся быстрее (за счет меньших вычислений или за счет поисковых алгоритмов).
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #2 : 25-04-2008 19:00 » 

Можно значительно уменьшмить объем поиска. Сначало выбрать все фигуры, которые близки по оси ֶX, затем по оси Y. Отсеять все фигуры, которые не вошли в два списка. Затем уже допроверять оставшиеся фигуры.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
little
Помогающий

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

« Ответ #3 : 29-04-2008 08:34 » 

Можно значительно уменьшмить объем поиска. Сначало выбрать все фигуры, которые близки по оси ֶX, затем по оси Y. Отсеять все фигуры, которые не вошли в два списка. Затем уже допроверять оставшиеся фигуры.
т.е. сначала пройтись по списку отбирая по близкому X, Y, а затем еще раз по полученному результату? а будет ли выгода?
Записан
little
Помогающий

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

« Ответ #4 : 29-04-2008 08:36 » 

1. Расстояние вычисляется между чем и чем? Между центрами, вершинами, любой точкой на стороне?

2. Перебирать все равно придется. Вариант оптимизации: создать индекс - упорядоченные предварительно вычисленные значения, по которым поиск будет делатся быстрее (за счет меньших вычислений или за счет поисковых алгоритмов).
1. По большому счету, без раницы. пусть будет между левыми верхними вершинами.

2. Вот насчет оптимизации хотелось бы что-нить более подробное услышать
Записан
zubr
Гость
« Ответ #5 : 29-04-2008 09:37 » 

little, стоит посмотреть для твоей задачи в сторону API функции IntersectRect. Достаточно будет проверять только пересечение регионов, да и работает она достаточно быстро.
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #6 : 29-04-2008 18:02 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #7 : 30-04-2008 02:35 » 

Может, подскажете каккую-нибудь другую организацию этого массива для уменьшения вычислений?

ЗЫ: реализовывать буду на C#.

Что бы упорядочить массиф нужно будет провести вычисления. Ток что выгоды от этого не будет. Тут единственный способ оптимизациии это использовать "короткие" логические операции при определении того является ли прямоугольник ближайшим.
Записан

Программа – это мысли спрессованные в код.
RXL
Технический
Администратор

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

WWW
« Ответ #8 : 30-04-2008 04:01 » 

1. По большому счету, без раницы. пусть будет между левыми верхними вершинами.

А значит - оперируем просто точками.

2. Вот насчет оптимизации хотелось бы что-нить более подробное услышать

Оптимизацию надо выбирать под специфику. К сожалению, в условии про нее не сказано...

Если делать универсально, то лучше как сказал Finch - сперва отсеч все ненужное. Например, отсечь все точки, не входящие в квадрат, с центром в контрольной точке и радиусом вписанной окружности, равным радиусу поиска. Иначе говоря, координаты вершин квадрата будут равны (X ± R, Y ± R). Потом тупо перебором с вычислением суммы квадратов разницы координат ((x - X)2 + (y - Y))2 - сравнивать с величиной R2. Это чтобы не вычислять корень.

Что бы упорядочить массив нужно будет провести вычисления. Ток что выгоды от этого не будет. Тут единственный способ оптимизациии это использовать "короткие" логические операции при определении того является ли прямоугольник ближайшим.

Если перемещаются не все точки, то будет.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 30-04-2008 14:44 » 

((x - X)2 + (y - Y))2 - сравнивать с величиной R2.

только общего квадрата в левой части не нужно Улыбаюсь

(x - X)2 + (y - Y)2 - сравнивать с величиной R2.
« Последнее редактирование: 30-04-2008 15:14 от Алексей1153++ » Записан

Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #10 : 30-04-2008 15:58 » 

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

Программа – это мысли спрессованные в код.
Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #11 : 30-04-2008 16:40 » 

...Да дело даже не в этом. В общем виде задача сводится к выборке элементов массива значения аргументов которых соотвествуют определённому условию ( в данном случае эти аргументы координаты одной из вершин прамоугольника и значение высоты и ширины, а условие это прохождение хотя бы одной из сторон прямоугольника в зоне поиска ) . Зачем как - то сортировать элементы в массиве ( операция не быстрая ) если можно оптимезировать вычисление этого уловия?
« Последнее редактирование: 30-04-2008 18:11 от Вахмурка » Записан

Программа – это мысли спрессованные в код.
RXL
Технический
Администратор

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

WWW
« Ответ #12 : 04-05-2008 19:11 » 

Алексей1153++, промахнулся - все ж тегами приходится оборачивать и не заметил.

Вахмурка, зато, сравнение координат обойдется дешевле по времени, чем вычисление суммы квадратов векторов с последующим сравнением.

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

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

« Последнее редактирование: 04-05-2008 19:14 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #13 : 04-05-2008 19:16 » 

RXL, а можно сделать тег, скажем [math][/math] , внутри которого можно будет писать x^2  , а показываться будет как x2 , а и вещи , вроде "[i]"  не будут тегом считаться ?
Можно не только степень, ещё что то сделать
Записан

RXL
Технический
Администратор

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

WWW
« Ответ #14 : 04-05-2008 19:20 » 

Леш, такой язык есть - TeX, но это будет сложновато для народа, а рисовать новый тег ради квадрата не стоит (остальные частые матсимволы будет сложно изобразить средствами HTML).
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #15 : 04-05-2008 19:23 » 

а так пущай маленькими картинками показывается ) В таблице
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #16 : 04-05-2008 19:36 » 

Алексей1153++, В какой таблице? Ты же сам отключаеш все картинки при просмотре. Представь как будет выглядеть пост с такими картинками у тебя.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #17 : 04-05-2008 19:40 » 

Finch, ну так это элементарно Улыбаюсь
во первых, я дома ничего не отключаю,
во вторых , если показать картинку кликом,то все одинаковые картинки станут видны (скачаются или из кеша)
в третьих, можно показывать формулу в виде текста, а ниже - "картинную"

если сложно, я же не настаиваю, просто мысля такая была )
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #18 : 04-05-2008 19:43 » 

Это нагрузка на сервер, так как картинка должна динамически формироваться на сервере. И у нас не математический форум, надобность в этом минимальна.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #19 : 04-05-2008 19:46 » 

понятно
Записан

RXL
Технический
Администратор

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

WWW
« Ответ #20 : 04-05-2008 19:49 » 

Алексей1153++, http://meta.wikimedia.org/wiki/%D0%9F%D0%BE%D0%BC%D0%BE%D1%89%D1%8C:%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B
Записан

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

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #21 : 05-05-2008 02:40 » 

Алексей1153++, промахнулся - все ж тегами приходится оборачивать и не заметил.

Вахмурка, зато, сравнение координат обойдется дешевле по времени, чем вычисление суммы квадратов векторов с последующим сравнением.

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

RXL, но ведь всё это можно как я говорил выполнить в одном уcловии. Если по координатам прямоугольник не подходит, тогда его в сторону иначе вычисляем суммы квадратов векторов. Я уже говорил про "короткие" логические операции, типа :лог_выражение_1 && лог_выражние_2. Тут если условие 1 не истина, то значение условия 2 уже не будет вычислятся так как оно на результат не влияет. Вот и оптимизация.( организовать подобное можно так же используя операторы ветвления )
Записан

Программа – это мысли спрессованные в код.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines