Как быстрее получить множество точек, входящих в прямоугольник?

Question

[Губернатор]

Делаю игру, псевдо-agar.io. jsfiddle.net/Strukov/cr0m6q57

Есть множество точек (map.eats) - это еда игрока, их может быть большое множество, и чем их больше, тем сильней лагает. (Для примера на 66 строке поставьте 100 000).
Все дело в том, что по таймеру происходит движение и отрисовка карты с множеством точек. Для каждой точки вызывается функция отрисовки, хоть скрытые точки фактически не рисуются, время на итерацию теряется.

Хочу изменить алгоритм, так что бы в цикл отрисовки попадали только видимые точки.

Есть предложения для реализации?

Думал сделать так:
- Отсортировать массив по X так:

map.eats.sort( (a,b)=>{if(a.x < b.x) return -1; if(a.x > b.x) return 1; return 0;} );

- Добавить коллекцию ссылок на те же точки, и отсортировать их по Y

for(let eat of map.eats)
{
	map.eatsReverse.push(eat);
}
map.eatsReverse.reverse( (a,b)=>{if(a.x > b.x) return -1; if(a.x < b.x) return 1; return 0;} );

- Получить область видимости
- Бинарным поиском, найти точки входящие в видимость по Х
- Убрать не видимые по Y
- Рисовать

Пока что запнулся на бинарном поиске.

Comments

[RAX7]

https://www.youtube.com/watch?v=OJxEcs0w_kE

Answer 1

[freeExec]

Готовые реализации на JS
https://blog.mapbox.com/a-dive-into-spatial-search...

Answer 2

[Wataru]

Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

R-дерево (по той же ссылке) дает гарантию по времени выполнения и знимает сравнительно мало памяти, но его долго пересчитывать, если точки двигаются или добавляются/удаляются.

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

Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

Эта структрура данных найдет все точки в прямоугольнике за O(k + log(MaxW) * log N), где k - количество точек в прямоугольнике, MaxW - высота пространства, N - общее количество точек. При этом каждая точка будет хранится ровно log(MaxW) раз, т.е. по памяти эта структура данных не такая и прожорливая - O(n log(MaxW)).

Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.