c++ - 高效的算法来获得圆心的圆心

Question

问题

我想获取围绕给定点的给定半径的圆内的所有像素，其中点只能具有整数坐标，即 Canvas 中的像素。



所以我想在给定(x, y)和r的情况下获取黄色区域中的所有点。

方法

我能想到的最有效的方法是在(x, y)周围遍历一个正方形，并检查每个点的欧几里得距离:

for (int px = x - r; px <= x + r; px++) {
  for (int py = y - r; py <= y + r; py++) {
    int dx = x - px, dy = y - py;

    if (dx * dx + dy * dy <= r * r) {
      // Point is part of the circle.
    }
  }
}

但是，这意味着该算法将检查不属于圆的一部分的 (r * 2)^2 * (4 - pi) / 4像素。 dx * dx + dy * dy <= r * r似乎很昂贵，几乎在当时被称为 1 / 4。

集成类似于 proposed here的东西可能会提高性能:

for (int px = x - r; px <= x + r; px++) {
  for (int py = y - r; py <= y + r; py++) {
    int dx = abs(x - px), dy = abs(y - py);

    if (dx + dy <= r || (!(dx > r || dy > r) && (dx * dx + dy * dy <= r * r))) {
      // Point is part of the circle.
    }
  }
}

但是，正如作者自己指出的那样，当大多数点都在圆内时(特别是由于 abs)，这可能不会更快，在这种情况下， pi / 4就是这种情况。

我找不到有关此问题的任何资源。我正在专门寻找C++中的解决方案，而不是 in SQL。

Answer 1

好了，这是我所 promise 的基准。

设置

我使用了google benchmark，任务是将圆的圆角内的所有点插入std::vector<point>。我对一组半径和一个恒定的中心进行基准测试:

radii = {10, 20, 50, 100, 200, 500, 1000}
center = {100, 500}

语言:C++ 17

编译器:msvc 19.24.28316 x64

平台:Windows 10

优化:O2(全面优化)

线程:单线程执行

测试每种算法的结果的正确性(与OPs算法的输出进行比较)。

到目前为止，已对以下算法进行了基准测试:

OP的算法enclosing_square。

My algorithm containing_square。

creativecreatorormaybenot's algorithm edge_walking。

Mandy007's algorithm binary_search。

结果

Run on (12 X 3400 MHz CPU s)
CPU Caches:
  L1 Data 32K (x6)
  L1 Instruction 32K (x6)
  L2 Unified 262K (x6)
  L3 Unified 15728K (x1)
-----------------------------------------------------------------------------
Benchmark                                   Time             CPU   Iterations
-----------------------------------------------------------------------------
binary_search/10/manual_time              804 ns         3692 ns       888722
binary_search/20/manual_time             2794 ns        16665 ns       229705
binary_search/50/manual_time            16562 ns       105676 ns        42583
binary_search/100/manual_time           66130 ns       478029 ns        10525
binary_search/200/manual_time          389964 ns      2261971 ns         1796
binary_search/500/manual_time         2286526 ns     15573432 ns          303
binary_search/1000/manual_time        9141874 ns     68384740 ns           77
edge_walking/10/manual_time               703 ns         5492 ns       998536
edge_walking/20/manual_time              2571 ns        49807 ns       263515
edge_walking/50/manual_time             15533 ns       408855 ns        45019
edge_walking/100/manual_time            64500 ns      1794889 ns        10899
edge_walking/200/manual_time           389960 ns      7970151 ns         1784
edge_walking/500/manual_time          2286964 ns     55194805 ns          308
edge_walking/1000/manual_time         9009054 ns    234575321 ns           78
containing_square/10/manual_time          629 ns         4942 ns      1109820
containing_square/20/manual_time         2485 ns        40827 ns       282058
containing_square/50/manual_time        15089 ns       361010 ns        46311
containing_square/100/manual_time       62825 ns      1565343 ns        10990
containing_square/200/manual_time      381614 ns      6788676 ns         1839
containing_square/500/manual_time     2276318 ns     45973558 ns          312
containing_square/1000/manual_time    8886649 ns    196004747 ns           79
enclosing_square/10/manual_time          1056 ns         4045 ns       660499
enclosing_square/20/manual_time          3389 ns        17307 ns       206739
enclosing_square/50/manual_time         18861 ns       106184 ns        37082
enclosing_square/100/manual_time        76254 ns       483317 ns         9246
enclosing_square/200/manual_time       421856 ns      2295571 ns         1654
enclosing_square/500/manual_time      2474404 ns     15625000 ns          284
enclosing_square/1000/manual_time     9728718 ns     68576389 ns           72

代码

完整的测试代码如下，您可以复制并粘贴并自己进行测试。 fill_circle.cpp包含不同算法的实现。

main.cpp

#include <string>
#include <unordered_map>
#include <chrono>

#include <benchmark/benchmark.h>

#include "fill_circle.hpp"

using namespace std::string_literals;

std::unordered_map<const char*, circle_fill_func> bench_tests =
{
    {"enclosing_square", enclosing_square},
    {"containing_square", containing_square},
    {"edge_walking", edge_walking},
    {"binary_search", binary_search},
};

std::vector<int> bench_radii = {10, 20, 50, 100, 200, 500, 1000};

void postprocess(std::vector<point>& points)
{
    std::sort(points.begin(), points.end());
    //points.erase(std::unique(points.begin(), points.end()), points.end());
}

std::vector<point> prepare(int radius)
{
    std::vector<point> vec;
    vec.reserve(10ull * radius * radius);
    return vec;
}

void bm_run(benchmark::State& state, circle_fill_func target, int radius)
{
    using namespace std::chrono;
    constexpr point center = {100, 500};

    auto expected_points = prepare(radius);
    enclosing_square(center, radius, expected_points);
    postprocess(expected_points);

    for (auto _ : state)
    {
        auto points = prepare(radius);

        auto start = high_resolution_clock::now();
        target(center, radius, points);
        auto stop = high_resolution_clock::now();

        postprocess(points);
        if (expected_points != points)
        {
            auto text = "Computation result incorrect. Expected size: " + std::to_string(expected_points.size()) + ". Actual size: " + std::to_string(points.size()) + ".";
            state.SkipWithError(text.c_str());
            break;
        }

        state.SetIterationTime(duration<double>(stop - start).count());
    }
}

int main(int argc, char** argv)
{
    for (auto [name, target] : bench_tests)
        for (int radius : bench_radii)
            benchmark::RegisterBenchmark(name, bm_run, target, radius)->Arg(radius)->UseManualTime();

    benchmark::Initialize(&argc, argv);
    if (benchmark::ReportUnrecognizedArguments(argc, argv))
        return 1;
    benchmark::RunSpecifiedBenchmarks();
}

fill_circle.hpp

#pragma once

#include <vector>

struct point
{
    int x = 0;
    int y = 0;
};

constexpr bool operator<(point const& lhs, point const& rhs) noexcept
{
    return lhs.x != rhs.x
               ? lhs.x < rhs.x
               : lhs.y < rhs.y;
}

constexpr bool operator==(point const& lhs, point const& rhs) noexcept
{
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

using circle_fill_func = void(*)(point const& center, int radius, std::vector<point>& points);

void enclosing_square(point const& center, int radius, std::vector<point>& points);
void containing_square(point const& center, int radius, std::vector<point>& points);
void edge_walking(point const& center, int radius, std::vector<point>& points);
void binary_search(point const& center, int radius, std::vector<point>& points);

fill_circle.cpp

#include "fill_circle.hpp"

constexpr double sqrt2 = 1.41421356237309504880168;
constexpr double pi = 3.141592653589793238462643;

void enclosing_square(point const& center, int radius, std::vector<point>& points)
{
    int sqr_rad = radius * radius;

    for (int px = center.x - radius; px <= center.x + radius; px++)
    {
        for (int py = center.y - radius; py <= center.y + radius; py++)
        {
            int dx = center.x - px, dy = center.y - py;
            if (dx * dx + dy * dy <= sqr_rad)
                points.push_back({px, py});
        }
    }
}

void containing_square(point const& center, int radius, std::vector<point>& points)
{
    int sqr_rad = radius * radius;
    int half_side_len = radius / sqrt2;
    int sq_x_end = center.x + half_side_len;
    int sq_y_end = center.y + half_side_len;

    // handle inner square
    for (int x = center.x - half_side_len; x <= sq_x_end; x++)
        for (int y = center.y - half_side_len; y <= sq_y_end; y++)
            points.push_back({x, y});

    // probe the rest
    int x = 0;
    for (int y = radius; y > half_side_len; y--)
    {
        int x_line1 = center.x - y;
        int x_line2 = center.x + y;
        int y_line1 = center.y - y;
        int y_line2 = center.y + y;

        while (x * x + y * y <= sqr_rad)
            x++;

        for (int i = 1 - x; i < x; i++)
        {
            points.push_back({x_line1, center.y + i});
            points.push_back({x_line2, center.y + i});
            points.push_back({center.x + i, y_line1});
            points.push_back({center.x + i, y_line2});
        }
    }
}

void edge_walking(point const& center, int radius, std::vector<point>& points)
{
    int sqr_rad = radius * radius;
    int mdx = radius;

    for (int dy = 0; dy <= radius; dy++)
    {
        for (int dx = mdx; dx >= 0; dx--)
        {
            if (dx * dx + dy * dy > sqr_rad)
                continue;

            for (int px = center.x - dx; px <= center.x + dx; px++)
            {
                for (int py = center.y - dy; py <= center.y + dy; py += 2 * dy)
                {
                    points.push_back({px, py});
                    if (dy == 0)
                        break;
                }
            }

            mdx = dx;
            break;
        }
    }
}

void binary_search(point const& center, int radius, std::vector<point>& points)
{
    constexpr auto search = []( const int &radius, const int &squad_radius, int dx, const int &y)
    {
        int l = y, r = y + radius, distance;

        while (l < r)
        {
            int m = l + (r - l) / 2;
            distance = dx * dx + (y - m) * (y - m);
            if (distance > squad_radius)
                r = m - 1;
            else if (distance < squad_radius)
                l = m + 1;
            else
                r = m;
        }

        if (dx * dx + (y - l) * (y - l) > squad_radius)
            --l;

        return l;
    };

    int squad_radius = radius * radius;    
    for (int px = center.x - radius; px <= center.x + radius; ++px)
    {
        int upper_limit = search(radius, squad_radius, px - center.x, center.y);
        for (int py = 2*center.y - upper_limit; py <= upper_limit; ++py)
        {
            points.push_back({px, py});
        }
    }
}