优化矢量emplace_back

Question

我们必须找到圆中的所有点，并将其保持在一个矢量中，以便进行平面拟合。为此，我们编写了以下代码。圆周上的点数约为2960520。执行时，执行vec.emplace_back(t)大约需要300ms。有没有办法优化代码？

constexpr int radius = 971;
auto time_begin = chrono::high_resolution_clock::now();
int rSquare = radius * radius;
vector<Point_t> vec;
vec.reserve(2048 * 2048);
for (int i = 1024 - radius; i < 1024 + radius; ++i)
{
    int iSquare = (i - 1024) * (i - 1024);
    for (int j = 1024 - radius; j < 1024 + radius; ++j)
    {
        int y = j - 1024;
        if ((y * y + iSquare) <= rSquare)
        {
            Point_t t{ static_cast<double>(i),static_cast<double>(j) };
            vec.emplace_back(t);
        }
    }
}

auto time_end = chrono::high_resolution_clock::now();

结构声明

struct Point_t
{
    double dX;
    double dY;
};

Answer 1

我建议你重新考虑算法。您当前测试该区域中的所有点。相反，您可以只使用Pythagoras定理来计算每条线的起点和终点。如果你做得正确，你实际上只需要计算出这个圆的四分之一。

虽然这需要使用平方根，但我认为执行sqrt 'radius‘次数很可能比测试(2*radius)^2点快得多。

抱歉，没有代码。目前还不能访问C++编译器。