Как найти все HTML элементы, попадающие в область другого элемента?

Question

[Андрей]

Нужно сделать штуку для выделения элементов на странице (по типу той, как мы выделяем файлы или папки в операционной системе).

Тупое решение я реализовал: рисуем див, чтобы показать область выделения, получаем массив необходимых элементов, при каждом mousemove проверяем, пересекается ли каждый взятый элемент с блоком выделения.

Разумеется, уже на десятке блоков начинаются лаги и стек забивается, даже несмотря на то, что слушатель mousemove затроттлен до 100мс (если сделать дольше, то всё равно будет ощущаться, как лаг).

Как оптимизировать данный алгоритм?

Comments

[Ankhena]

https://developer.mozilla.org/ru/docs/Web/API/Inte...

[Андрей]

Ankhena, при чем тут IntersectionObserver?

Answer 1

[dollar]

Можно разбить на два этапа:
1) Сначала подготавливаем массив элементов, - а именно считаем прямоугольную область каждого элемента. Теперь у нас массив прямоугольников. Исходя из того, что области меняться не будут, делаем кое-какие дополнительные вычисления для оптимизации этапа №2.
2) При каждом выделении мышкой, решаем геометрическую задачу по поиску пересечений прямоугольников, которая уже не имеет прямого отношения к HTML, DOM и т.д.

Навскидку могу предложить такое решение:

Режем экран в виде невидимой сетки. Размеры ячеек вы выбираете сами. Пусть это будет сетка 10х10 ячеек. Для каждого элемента заранее считаем, в какие ячейки он попадает. То есть каждая ячейка - это массив ссылок на элементы, которые в неё попадают.

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

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

И, наконец, когда юзер выделяет слишком большую область, которая ложится на 9х10 ячеек, то уже выгоднее искать те прямоугольники, которые могут не попасть в результат, то есть которые в ячейках 2х10. А все оставшиеся непроверенные автоматически попадают в результат.

Это был пример простой оптимизации, далёкой от совершенства.

Comments

[tempick]

Вообще, проще сделать список файлов в виде колонки (просто список) и записать нижнюю левую координату каждого элемента. А после выделения уже брать нижнюю координату выделения и бинарным поиском определять, какие элементы войдут. Но это только для формата списка. Если же обязательно в виде ячеек все надо, то там да, сложнее.

[Андрей]

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

[dollar]

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

[Андрей]

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

Проверку на пересечение написал методом тыка (в геометрии я жуткий нуб, но код выглядит не так, чтобы страшно):

const is_initial_selection_block = (
                (selection_initial_point.y > block.top + scrollY && selection_initial_point.y < block.bottom + scrollY) &&
                (selection_initial_point.x > block.left + scrollX && selection_initial_point.x < block.right + scrollX)
            )

            if (is_initial_selection_block) {
                if (top < block.top + scrollY || bottom > block.bottom + scrollY|| left < block.left + scrollX || right > block.right + scrollX) {
                    is_intersecting = true
                }
            }

            else {
                if (top < block.bottom + scrollY && bottom > block.top + scrollY) {
                    if (left < block.right + scrollX && right > block.left + scrollX) {
                        is_intersecting = true
                    }
                }
            }

Здесь, кстати, дополнительная проверка помимо простого пересечения: если выделение началось внутри определенного блока, то считать выделенным его нужно только в том случае, если одна из границ области выделения выходит за границы этого блока.

Прикладываю этот код на случай, если есть возможность сделать проверку проще)

[tempick]

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