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