Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник |
Коллекция курьезных вопросов из форумов
KOL и MCK |
KOL и MCK - Компактные программы на Delphi
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »

Определение пересечения заданного прямоуг. с набором прямоуг.


Тимохов Дима ©   (01.11.18 23:27

Коллеги, знаю тут есть знатоки алгоритмов. Может, поможете?

Есть:
1. Список записей TMyRect вида (Col1, Row1) - (Col2, Row2) - углы прямоугольника.
2. Есть новый TMyRect.
3. Нужно определить, пересекается ли новый TMyRect с существующими TMyRect.

Общее понятие пересечения очевидно.
Приведу пограничные случаи:
а. Сторонами пересекаться нельзя. (1,1)-(2,2) и (2,1)-(5,5) - пересекаются стороной.
б. Иметь общие углы тоже нельзя. (1,1)-(2,2) и (2,2)-(3,3) - пересекаются углом.
в. Касаться можно. (1,1)-(2,2) и (3,1)-(4,2) - касаются (это можно).

Конечно, понятно, как это сделать перебором. Нужен быстрый алгоритм!

В случае лексикографии понятно, что надо держать список упорядоченным и методом деления пополам находить - есть ли такой объект. Тут я не соображу - как эти прямоугольники упорядочить лексикографически.

Должен же быть какой-то общеизвестный алгоритм.

Спасибо!


картман ©   (02.11.18 11:01[1]


> Общее понятие пересечения очевидно.

судя по приведенным координатам, тебе нужен зазор не менее 1


картман ©   (02.11.18 11:06[2]

https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B0


Тимохов Дима ©   (02.11.18 15:01[3]


> картман ©   (02.11.18 11:01) [1]
>
> > Общее понятие пересечения очевидно.
>
> судя по приведенным координатам, тебе нужен зазор не менее
> 1

Почему? Это не TRect. (1,1)-(2,2) это квадрат 2 на 2.

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

ЗЫ Не для себя стараюсь. Мне не очень нужно. Хочу предложить один хороший сторонний компонент усовершенствовать.


Читатель ©   (02.11.18 15:14[4]

Метод перебора дает просадки в скорости или просто из перфекционизма вопрос возник? Так много прямоугольников?
Можно цикл по проверке оптимизировать, например, как вариант.


картман ©   (02.11.18 15:40[5]


> Почему? Это не TRect. (1,1)-(2,2) это квадрат 2 на 2.

это же координаты левого верхнего и правого нижнего углов?


картман ©   (02.11.18 15:44[6]


> это же координаты левого верхнего и правого нижнего углов?

или координата и размеры?


картман ©   (02.11.18 16:02[7]

Четыре бинарных дерева.
Ветка слева - элементы меньше корня, справа - больше. В узлах/листьях отсортированные(хоть по номерам добавления) списки соответствующих прямоугольников.

В первом дереве - меньшая координата по х, во втором - большая.
В 3 и 4 - храним у.

Поступил прямоугольник(х1,у1,х2,у2 - это координаты углов). Прошли по первому дереву, выбрали список прямоугольников, с большей или равной координатой х1. Прошли по второму - получили список с координатами меньше или равно х2. Нашли пересечение. Та же хрень с 3-м и 4-м деревьями.

Надеюсь, в дельфи есть сбалансированное дерево?))


Читатель ©   (02.11.18 16:10[8]

Только вопрос, если это компонента, где деревья хранить? По логике должен быть контейнер где прямоугольники хранятся. Вот в нем и объявить деревья. Или писать "сторонний класс -контейнер" для поиска, например TRectIntersectFind, в который будут добавляться прямоугольники (ссылки). По процедуре Work(например) формироваться деревья и возвращать результат как список пересеченных с нашим прямоугольником объектов. Второй вариант без вмешивания в исходный код компонента.


Юрий Зотов ©   (02.11.18 17:16[9]

> Сабж

Если координаты экранные, то IntersectRect.
Если НЕэкранные, то сначала привести к экранным.


L_G ©   (03.11.18 04:52[10]

если засунуть существующие прямоугольники в quad-tree (дерево квадрантов), каждый узел к-рого содержит список попадающих в него прямоугольников и 4 ссылки на списки прямоугольников, целиком попадающих в 1 из 4 его подквадрантов (исключенных из его собственного списка) и найти имеющийся узел дерева, подходящий для нового прямоугольника - достаточно будет проверить только прямоугольники из этого узла и его подузлов

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


L_G ©   (03.11.18 04:59[11]

* достаточно будет проверить только прямоугольники из этого узла, его подузлов и еще его родительских узлов


Тимохов Дима ©   (03.11.18 13:18[12]


> картман ©   (02.11.18 15:40) [5]
> > Почему? Это не TRect. (1,1)-(2,2) это квадрат 2 на 2.
> это же координаты левого верхнего и правого нижнего углов?

Плохой пример привел я. Не подумал.
Это координаты, а не размеры.


> Читатель ©   (02.11.18 15:14) [4]
> Метод перебора дает просадки в скорости или просто из перфекционизма
> вопрос возник? Так много прямоугольников?
> Можно цикл по проверке оптимизировать, например, как вариант.

Есть реальная просадка.
Это компонент XLSReadWriteII - для прямого эскорта в формат xlsx.
Есть просадка при большом кол-ве объединенных ячеек.
Видимо, компонент проверяет, что объединения не пересекаются.
У меня есть своя либа - для экспорта в BIFF8 (xls). Но 65тыс строк стало мало. Вот, решил взять чужой компонент для экспорта в современный формат Excel.
У меня было все просто - заполнение сверху вниз, слева направо (т.е. возвращаться нельзя). Похожая проблема в моей либе решена с учетом этого ограничения. XLSReadWriteII позволяет делать произвольный доступ к ячейкам. Поэтому, видимо, оптимальный алгоритм там будет сложнее, чем у меня.

---------

> картман ©   (02.11.18 16:02) [7]
> Четыре бинарных дерева...
> Надеюсь, в дельфи есть сбалансированное дерево?))

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


> L_G ©   (03.11.18 04:52) [10]
> если засунуть существующие прямоугольники в quad-tree (дерево
> квадрантов...

Спасибо. Покопаю тему.


Читатель ©   (06.11.18 07:21[13]


> Это компонент XLSReadWriteII - для прямого эскорта в формат
> xlsx.
> Есть просадка при большом кол-ве объединенных ячеек.
> Видимо, компонент проверяет, что объединения не пересекаются.
>

Елки, это просадки не из-за алгоритма! А из-за экселя.. Тормоз еще тот. Не там копаете.. Создать эффективный экспорт в эксель по скорости та еще задача и деревья для прямоугольников не спасут. Помню делал оптимизацию, так получилось из 2-х часов в 10 минут оптимизировалось. Оптимизировать нужно под эксел, а это значит нужно понимать что надо минимизировать переключение между внешней программой и экселем и по максимуму использовать его внутренние функции, особо предпочитая групповые изменения. Быть может для этого нужно будет писать полностью свой компонент. ИМХО


Читатель ©   (06.11.18 07:25[14]


> Елки, это просадки не из-за алгоритма! А из-за экселя..

Ой, я не прав. Смотрю компоненту, она без ОЛЕ..


L_G ©   (06.11.18 23:22[15]

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


Тимохов Дима ©   (07.11.18 21:58[16]

Добрался до исходников XLSReadWriteII (купиль на кровные!).
Сложно там все с этими объединениями. Думал за денек справлюсь левой ногой. Не фига, думать шибко надо.
Пусть будет как есть пока. Все равно не актуально - в моих примерах массовых объединений нет.
Спасибо всем! И извините за беспокойство)


картман ©   (09.11.18 15:01[17]

С xlsx для скорости можно работать как со строкой


версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо