C ++ самый эффективный способ представления зоны покрытия камеры в gridmap - PullRequest
Новая
       8

C ++ самый эффективный способ представления зоны покрытия камеры в gridmap

0 голосов
/ 21 февраля 2019

В настоящее время я работаю над проектом, в котором робот движется по среде, представленной в виде nxn сетки (скажем, 100x100, но в будущем будет намного больше), которую я буду моделировать как 2D-array из ints.Район наблюдается камерами.Робот знает, какая камера покрывает какую область, и способен дистанционно деактивировать камеры из диапазона, который немного превышает диапазон обзора камеры.Он должен придумать план, чтобы пройти сквозь окружающую среду незамеченным.

Теперь мне нужно знать, какая область захватывается какой камерой.Давайте для простоты предположим, что все камеры имеют круглые поля зрения.Теперь, если, например, camera 1 захватывает определенную область, я собираюсь поместить 1 в эту область массива.Все идет нормально.Но что, если есть вторая (и, возможно, третья) камера, чьи поля зрения перекрываются?Как бы я представлял это перекрытие в карте сетки?

Пока мои мысли:

  • добавить идентификаторы камеры в сетку - например, если camera 1 покрывает определенный FOV, заполните его 1's.Если FOV camera 2 перекрывается, заполните область перекрытия 1+2=3.Недостаток: количество возможностей для n камер является экспоненциальным, и будет трудно проследить, как рассчитывалось число - например, 6 может быть camera 5 перекрывающимся camera 1, но также camera 2 перекрывающимся camera 4.
  • объединить идентификаторы камеры в сетке - для перекрытия cam 1 и cam 2, поместите 12 в сетку.Для перекрытия cam 1,2 and 3 поместите 123 в сетку.Преимущество: только целочисленная арифметика, должна быть быстрой.Недостаток: только столько камер, сколько возможно для целого диапазона, имеют цифры (int_max для 32bit равно 4294967295, поэтому максимум 10 камер)

Любая помощь или мысли?Даже литература или алгоритмы, которые решают этот тип проблемы?Язык программирования будет C ++.

1 Ответ

0 голосов
/ 22 февраля 2019

Вы можете использовать один бит внутри вашего int для каждой конкретной камеры.Однако, если иметь дело с одиночными битами, unsigned int предпочтительнее: если 32-битное целое число, 1 << 31 приводит к неопределенному поведению из-за целочисленного переполнения со знаком, так что вам придется жить с одним битом меньше или иметь некоторую специальную обработкудля идентификатора камеры 31 (при условии нулевого идентификатора): 

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 бита на 64-битной Linux).Если вы хотите обеспечить определенное количество доступных битов, я рекомендую использовать типы данных из заголовка <cstdint>, например, uint32_t (чтобы быть уверенным, что литерал 1U имеет соответствующий диапазон, следует привести: static_cast<uint32_t>(1U) или определитьконстанта соответствующего типа).

Обработка битов стоит несколько дополнительных операций, но они должны быть незначительными (за исключением некоторых очень редких, экстремальных сценариев производительности; встречаются такие только один единственныйопыт работы более 15 лет ...).

Еще одно замечание: вы можете обнаружить, что битовые поля скрывают биты от вас.Ну, конечно, они делают (но это все еще там, просто компилятор сделает все за вас).Но тогда у них есть и другие недостатки (самое важное: порядок членов не гарантируется, что они будут одинаковыми в разных системах, поэтому, если вы сериализуете их, например, в TCP или файлы, вы должны знать об этом!), Я лично предпочел бы избежатьих.Еще: 

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