Конференция "Прочее" » Определение пересечения заданного прямоуг. с набором прямоуг.
 
  • Тимохов Дима © (01.11.18 23:27) [0]
    Коллеги, знаю тут есть знатоки алгоритмов. Может, поможете?

    Есть:
    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]
  • Тимохов Дима © (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 для скорости можно работать как со строкой
 
Конференция "Прочее" » Определение пересечения заданного прямоуг. с набором прямоуг.
Есть новые Нет новых   [94805   +143][b:0.001][p:0.002]