C++在网格图中表示相机覆盖区域的最有效方法

Question

我目前正在开展一个项目，其中机器人正在通过表示为 nxn 网格图(例如 100x100，但将来会更大)的环境) 我将其建模为 ints 的 2D-array。该区域由摄像机观察。机器人知道哪个摄像头覆盖哪个区域，并且能够在略微超出摄像头 FOV 范围的范围内远程停用摄像头。它必须想出一个计划，以在不被注意的情况下通过环境。

现在，我需要知道哪个区域被哪个相机捕获。为简单起见，我们假设所有相机都具有圆形 FOV。现在，如果例如camera 1 捕获某个区域，我考虑将 1 放在数组的那个区域。到目前为止，一切都很好。但是，如果有第二个(也许是第三个)摄像机的 FOV 重叠怎么办？我将如何在网格图中表示这种重叠？

到目前为止我的想法:

• 将网格中的摄像机 ID 相加 - 例如如果 camera 1 覆盖了某个 FOV，则用 1 填充它。如果 camera 2 的 FOV 重叠，则用 1+2=3 填充重叠区域。缺点:n 个相机的可能性数量是指数级的，并且很难追溯一个数字是如何计算的 - 例如，6 可能是 camera 5 与 camera 1 重叠，还有 camera 2 与 camera 4 重叠。
• 在网格中连接相机 ID - 对于 cam 1 和 cam 2 的重叠，将 12 放入网格中。对于 cam 1,2 和 3 的重叠，将 123 放入网格中。优点:仅整数运算，应该很快。缺点:只有尽可能多的相机整数范围有数字(int_max 32bit 是 4294967295，所以最多 10 个相机)

有什么帮助或想法吗？甚至解决此类问题的文献或算法？编程语言将是 C++。

Answer 1

您可能会在 int 中使用一位对于每个特定的相机。但是，如果处理单个位，unsigned int更可取:假设 32 位 int，1 << 31由于有符号整数溢出导致未定义的行为，因此您必须忍受少一位或对相机 ID 31 进行一些特殊处理(假设 ID 从零开始):

unsigned int field;

// setting the bit for camera ID n (zero based):
field |= 1U << n;

// clearing the bit for camera ID n (zero based):
field &= ~(1U << n);

// reading the bit:
bool isSet = (field & ~(1U << n)) != 0;

(当然，您会将其打包到适当的(内联？)函数中...)

这样，您可以管理CHAR_BIT * sizeof(unsigned int)相机。在大多数现代系统上，这将是 32 个摄像头——但这取决于编译器/架构!根据标准，unsigned int 保证能够保存从 0 到 65535 的值，因此为了便于携带，您只能依赖 16 位( long 这样可以保证 32 位，但可以更大，例如64 位 Linux 上的 64 位)。如果您想确保特定数量的可用位数，我建议使用 <cstdint> 中的数据类型 header ，e。 G。 uint32_t (为了确保文字 1U 具有适当的范围，您应该强制转换:static_cast<uint32_t>(1U) 或定义适当类型的常量)。

位处理会花费一些额外的操作，但这些应该可以忽略不计(除了一些非常罕见的、极端的性能场景；在超过 15 年的专业经验中只遇到过一次这样的场景...)。

只是一个旁注:您可能会发现位字段隐藏了您的位摆弄。好吧，当然，他们这样做了(但它仍然存在，只是编译器为你做了这些事情)。但是它们还有其他缺点(最重要的是:成员的顺序不能保证在不同的系统中是相同的，所以如果你将它们序列化到例如 TCP 或文件，你需要注意!)，我个人宁愿避免他们。仍然:

struct Field
{
    uint32_t  _0 : 1;
    uint32_t  _1 : 1;
    // ...
    uint32_t _31 : 1;
};