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

Question

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

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

到目前为止我的想法：

在网格中添加摄像机 ID - 例如如果 camera 1 覆盖了某个 FOV，则用 1's 填充它。如果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 and 3 的重叠，将 123 放入网格中。优点：仅整数运算，应该很快。缺点：只有尽可能多的相机，因为整数范围有数字（int_max 对于 32bit 是 4294967295，所以最多 10 个相机）

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

Answer 1

您可以在 int 中为每个特定的相机使用一位。但是，如果处理单个位，unsigned int 更可取：假设 32 位 int，1 << 31 由于有符号整数溢出导致未定义的行为，因此您必须忍受少一位或对相机 ID 31（假设 zero-based 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 个摄像头——但这取决于 compiler/architecture！根据标准，unsigned int 保证能够保存 0 到 65535 之间的值，因此为了便携，您只能依赖 16 位（long 这样可以保证 32 位，但可以更大，例如 64 位对 64 位 linux）。如果您想确保可用的特定位数，我建议使用 <cstdint> header 中的数据类型，例如。 G。 uint32_t（为了确保文字 1U 具有适当的范围，您应该强制转换：static_cast<uint32_t>(1U) 或定义适当类型的常量）。

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

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

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

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

C++ most efficient way to represent camera covered area in gridmap

c++

arrays

camera

2d