многоугольники в заданной области

[little]

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

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

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

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

[RXL]

little,

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

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

[Finch]

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

[little]

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

т.е. сначала пройтись по списку отбирая по близкому X, Y, а затем еще раз по полученному результату? а будет ли выгода?

[little]

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

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

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

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

[zubr]

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

[Finch]

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

[Вахмурка]

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

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

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

[RXL]

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

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

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

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

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

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

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

[Алексей++]

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

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

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

[Вахмурка]

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

[Вахмурка]

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

[RXL]

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

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

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

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

[Алексей++]

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

[RXL]

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

[Алексей++]

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

[Finch]

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

[Алексей++]

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

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

[Finch]

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

[Алексей++]

понятно

[RXL]

Алексей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

[Вахмурка]

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

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

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

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