Алгоритм C ++ для фильтрации несоответствующих координатных данных

В настоящее время я работаю над хобби-проектом, в котором у меня есть несколько тысяч звезд в вымышленной вселенной 2D. Мне нужно визуализировать эти звезды на экране, но, очевидно, я не хочу работать со всеми из них — только с теми, которые видны в любой момент времени.

Для подтверждения концепции я написал алгоритм грубой силы, который бы смотрел на каждую звезду и проверял ее координаты на границах экрана игрока:

for (const std::shared_ptr<Star>& star : stars_) {
if (moved_)
star->MoveStar(starfield_offset_, level_);
position = star->position();
if (position.x >= bounds_[0] &&
position.x <= bounds_[1] &&
position.y >= bounds_[2] &&
position.y <= bounds_[3])
target.draw(*star);
}

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

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

Итак, я реализовал два новых контейнера — один для данных, отсортированных по координате х, а другой по координате у. Моя первоначальная мысль состояла в том, чтобы взять пересечение этих двух отсортированных наборов и нарисовать получившиеся звезды на экране (звезды, координаты x и y которых лежат в границах экрана):

struct SortedStars {
std::vector<std::shared_ptr<Star>>::iterator begin, end;
std::vector<std::shared_ptr<Star>> stars;
} stars_x_, stars_y_;

Затем я отсортировал эти контейнеры:

// comparison objects
static struct SortX {
bool operator() (const std::shared_ptr<Star>& first, const std::shared_ptr<Star>& second)
{ return (first->position().x < second->position().x); }
bool operator() (const std::shared_ptr<Star>& first, const float val)
{ return (first->position().x < val); }
bool operator() (const float val, const std::shared_ptr<Star>& second)
{ return (val < second->position().x); }
} sort_x;

static struct SortY {
bool operator() (const std::shared_ptr<Star>& first, const std::shared_ptr<Star>& second)
{ return (first->position().y < second->position().y); }
bool operator() (const std::shared_ptr<Star>& first, const float val)
{ return (first->position().y < val); }
bool operator() (const float val, const std::shared_ptr<Star>& second)
{ return (val < second->position().y); }
} sort_y;

void Starfield::Sort() {
// clone original data (shared pointers)
stars_x_.stars = stars_;
stars_y_.stars = stars_;
// sort as needed
std::sort(stars_x_.stars.begin(), stars_x_.stars.end(), sort_x);
std::sort(stars_y_.stars.begin(), stars_y_.stars.end(), sort_y);

// set iterators to the outermost visible stars (defined by screen bounds)
// these are updated every time the screen is moved
stars_x_.begin = std::lower_bound(stars_x_.stars.begin(), stars_x_.stars.end(), bounds_[0], sort_x);
stars_x_.end = std::upper_bound(stars_x_.stars.begin(), stars_x_.stars.end(), bounds_[1], sort_x);
stars_y_.begin = std::lower_bound(stars_y_.stars.begin(), stars_y_.stars.end(), bounds_[2], sort_y);
stars_y_.end = std::upper_bound(stars_y_.stars.begin(), stars_y_.stars.end(), bounds_[3], sort_y);

return;
}

К сожалению, я не могу придумать подходящую функцию сравнения для std :: set_intersection или метод, с помощью которого я мог бы вручную сравнивать координаты, используя мои итераторы.

Не могли бы вы, ребята, указать мне правильное направление? Отзывы о моей методологии или реализации очень приветствуются.

Спасибо за ваше время!