我目前正在从事一个爱好项目，其中我在 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 坐标排序的数据。我最初的想法是取这两个排序集的交集并将生成的星星绘制到屏幕上（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 提供合适的比较函数，也无法使用迭代器手动比较坐标的方法。
你们能指出我正确的方向吗？非常欢迎对我的方法或实施提供反馈。
谢谢你的时间！