使用std :: list :: iterator變量跟蹤循環訪問列表中的最近點。當您到達列表的末尾時,它將包含最近的點並可用於擦除該項目。
void erase_closest_point(const list<Point>& pointList, const Point& point)
{
if (!pointList.empty())
{
list<Point>::iterator closestPoint = pointList.begin();
float closestDistance = sqrt(pow(point.x - closestPoint->x, 2) +
pow(point.y - closestPoint->y, 2));
// for each point in the list
for (list<Point>::iterator it = closestPoint + 1;
it != pointList.end(); ++it)
{
const float distance = sqrt(pow(point.x - it->x, 2) +
pow(point.y - it->y, 2));
// is the point closer than the previous best?
if (distance < closestDistance)
{
// replace it as the new best
closestPoint = it;
closestDistance = distance
}
}
pointList.erase(closestPoint);
}
}
在給定點的半徑內建立一個點列表是類似的。請注意,通過引用將空半徑列表傳遞給函數。通過引用將列表添加到列表將消除在按值返回向量時複製所有點的需要。
void find_points_within_radius(vector<Point>& radiusListOutput,
const list<Point>& pointList,
const Point& center, float radius)
{
// for each point in the list
for (list<Point>::iterator it = pointList.begin();
it != pointList.end(); ++it)
{
const float distance = sqrt(pow(center.x - it->x, 2) +
pow(center.y - it->y, 2));
// if the distance from the point is within the radius
if (distance > radius)
{
// add the point to the new list
radiusListOutput.push_back(*it);
}
}
}
再次使用副本,如果:
struct RadiusChecker {
RadiusChecker(const Point& center, float radius)
: center_(center), radius_(radius) {}
bool operator()(const Point& p)
{
const float distance = sqrt(pow(center_.x - p.x, 2) +
pow(center_.y - p.y, 2));
return distance < radius_;
}
private:
const Point& center_;
float radius_;
};
void find_points_within_radius(vector<Point>& radiusListOutput,
const list<Point>& pointList,
const Point& center, float radius)
{
radiusListOutput.reserve(pointList.size());
remove_copy_if(pointList.begin(), pointList.end(),
radiusListOutput.begin(),
RadiusChecker(center, radius));
}
注意,開方可以,如果你需要額外的性能,因爲幅度的平方的作品一樣好這些比較中移除。另外,如果您真的想要提高性能,則需要考慮允許場景分區的數據結構,如quadtree。第一個問題與collision detection密切相關,並且存在大量關於該主題的有價值的信息。
@Nathan Fellman,我不在學校。我正在努力學習C++,並決定編寫一個繪圖程序。所以,我猜想自己的作業。 – KingNestor 2009-02-11 21:26:51