1
我目前正在研究一个爱好项目，其中我有一个2D虚构宇宙中的几千颗恒星。我需要将这些星星渲染到屏幕上，但显然我不希望对所有这些星星进行操作 - 只有那些在任何给定时间都可见的星星。C++算法来过滤不相关的坐标数据
对于概念证明，我写了一个蛮力算法会看每一颗星星是和测试其坐标对播放器的屏幕的界限：
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想出一个适当的比较函数，或者我可以用我的迭代器手动比较坐标的方法。
你们可以指点我正确的方向吗？我的方法或实施反馈非常受欢迎。
谢谢你的时间！
你应该查找[k-d trees]（http://en.wikipedia.org/wiki/K-d_tree）。 – user1118321
良好的通话！我正在根据接受的答案的建议来看看Quadtrees。 – SamuelMS