Алгоритм отбора геокоординат из массива (no database)

Дано: есть большой массив геокоординат точек и полилиний

Poi: array[0..1788500] of Double = (68.94989, 33.10013, 69.00689, 33.08681, ....);
Polyline: array[0..508300] of Double = (69.02257, 33.0729,69.02223, 33.0729,69.02223, 33.07318,69.02257, 33.07318,69.02257, 33.0729,0, ....);

Вопрос: необходимо максимально быстро отобрать точки массива входящий в BoundingBox (например: [68.0,32.0,70.0,34.0]) текущей области просмотра
Варианты реализации:
1. сейчас я делаю это перебором и сравнением вхождения координат в область, это медленно.
2. можно было бы воспользоваться тайловой системой координат используемой в OSM, Google, Yandex. Т.е. сгруппировать все координаты по x,y тайла. И проверять вхождение координат тайла в требуемый BoundingBox. Это работает быстрее, но мне нужно еще вращать карту, при таком подходе прямоугольный тайловый подход теряет свой смысл (наверное все замечали, что в основном в web картах нет вращения).

Текущие тесты проводятся в Delphi, но это не принципиально, интересует возможный алгоритм построения системы индексации, не знаю как это можно назвать.
Спасибо.

xMailer
1. сейчас я делаю это перебором и сравнением вхождения координат в область, это медленно.

Самое время почитать третий том Кнута.

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

не теряет, вращение это простое преобразование и можно делать обратное

вместо "проверять вхождение координат тайла в требуемый BoundingBox" по идее у вас должно проверяться хотя бы частичное пересечение тайла и требуемогого BoundingBox, а затем все равно проверяться попадание в него конкретной точки

с учетом поворота на произвольный угол просто нужно будет проверять пересечение с BoundingBox окружности, описанной вокруг тайла (или проще - попадание центра тайла в немного расширенный BoundingBox, где немного = сторона тайла, деленная на корень из двух)

вообще, для индексации точек на плоскости используют quad-tree, то есть иерархию квадратных тайлов

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

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

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

Парни, все объяснили, большое спасибо!!!

После quad-tree можно почитать про r-tree.