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

Есть:
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) - касаются (это можно).

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

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

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

Спасибо!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

> Сабж

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

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

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

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

> картман ©   (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 (дерево
> квадрантов...

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

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

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

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

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

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

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

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