用于存储网格的数据结构(将具有负索引)

Question

我正在这所大学学习机器人，我必须在我自己的SLAM算法上实现。为此，我将使用ROS、Gazebo和C++。

我不知道我要用什么数据结构来存储地图(以及我要存储的是什么，但这是另一个故事)。

我想把地图表示为二维网格，机器人的起始位置是(0,0)。但我不知道我要绘制的世界上的机器人到底在哪里。它可以是在左上角，在世界的中部，或者在世界上任何其他的不起眼的地方。

网格的每个单元将是1x1米。我会用激光来知道障碍在哪里。使用当前机器人的位置，我将设置为1的所有细胞，代表一个障碍。例如，它的激光探测到在机器人前面2米处的障碍物，我将在(0,2)处设置为1。

使用一个向量，或者一个2D矩阵，这是一个问题，因为向量和矩阵的索引从0开始，机器人后面可能有更多的空间来映射。那个房间将在(-1，-3)处设置障碍物。

在这个数据结构上，我需要存储有障碍的细胞和我知道它们是免费的细胞。

我需要使用哪种数据结构？

更新：

存储地图的过程如下：

1. 机器人从(0,0)单元开始。它将发现障碍并将它们存储在地图中。
2. 机器人移动到(1,0)单元。再一次，在地图上发现和储存障碍。
3. 继续移动到自由细胞，并储存它所建立的障碍。

机器人会探测到前面和侧面的障碍物，但永远不会在后面。

当机器人检测到负电池上的障碍物(比如(0，-1) )时，我的问题就来了。如果我以前只把障碍存储在“阳性”细胞上，我就不知道如何存储这个障碍。所以，也许“抵消”，这不是一个解决方案(或者我错了)。

Answer 1

您可以使用创建的std::set类来使用position来表示网格布局。它包含一个x和y变量，因此可以直观地用于查找网格中的点。如果希望在网格中存储有关某个位置的信息，也可以使用std::map。

如果不想在外部提供比较操作符，请不要忘记满足C++命名的set/map (如比较 )的要求。

例:职位。

/* this class is used to store the position of things
 * it is made up by a horizontal and a vertical position.
 */
class position{
private:
    int32_t horizontalPosition;
    int32_t verticalPosition;
public:
    position::position(const int hPos = 0,const int vPos = 0) : horizontalPosition{hPos}, verticalPosition{vPos}{}
    position::position(position& inputPos) : position(inputPos.getHorPos(),inputPos.getVerPos()){}
    position::position(const position& inputPos) : position((inputPos).getHorPos(),(inputPos).getVerPos()){}

    //insertion operator, it enables the use of cout on this object: cout << position(0,0) << endl;
    friend std::ostream& operator<<(std::ostream& os, const position& dt){
        os << dt.getHorPos() << "," << dt.getVerPos();
        return os;
    }

    //greater than operator
    bool operator>(const position& rh) const noexcept{
        uint64_t ans1 = static_cast<uint64_t>(getVerPos()) | static_cast<uint64_t>(getHorPos())<<32;
        uint64_t ans2 = static_cast<uint64_t>(rh.getVerPos()) | static_cast<uint64_t>(rh.getHorPos())<<32;

        return(ans1 < ans2);
    }

    //lesser than operator
    bool operator<(const position& rh) const noexcept{
        uint64_t ans1 = static_cast<uint64_t>(getVerPos()) | static_cast<uint64_t>(getHorPos())<<32;
        uint64_t ans2 = static_cast<uint64_t>(rh.getVerPos()) | static_cast<uint64_t>(rh.getHorPos())<<32;

        return(ans1 > ans2);
    }

    //equal comparison operator
    bool operator==(const position& inputPos)const noexcept {
        return((getHorPos() == inputPos.getHorPos()) && (getVerPos() == inputPos.getVerPos()));
    }

    //not equal comparison operator
    bool operator!=(const position& inputPos)const noexcept {
        return((getHorPos() != inputPos.getHorPos()) || (getVerPos() != inputPos.getVerPos()));
    }

    void movNorth(void) noexcept{
        ++verticalPosition;
    }
    void movEast(void) noexcept{
        ++horizontalPosition;
    }
    void movSouth(void) noexcept{
        --verticalPosition;
    }
    void movWest(void) noexcept{
        --horizontalPosition;
    }

    position getNorthPosition(void)const noexcept{
        position aPosition(*this);
        aPosition.movNorth();
        return(aPosition);
    }
    position getEastPosition(void)const noexcept{
        position aPosition(*this);
        aPosition.movEast();
        return(aPosition);
    }
    position getSouthPosition(void)const noexcept{
        position aPosition(*this);
        aPosition.movSouth();
        return(aPosition);
    }
    position getWestPosition(void)const noexcept{
        position aPosition(*this);
        aPosition.movWest();
        return(aPosition);
    }

    int32_t getVerPos(void) const noexcept {
        return(verticalPosition);
    }
    int32_t getHorPos(void) const noexcept {
        return(horizontalPosition);
    }
};

std::set<position> gridNoData;
std::map<position, bool> gridWithData;

gridNoData.insert(point(1,1));
gridWithData.insert(point(1,1),true);

gridNoData.insert(point(0,0));
gridWithData.insert(point(0,0),true);

auto search = gridNoData.find(point(0,0));
if (search != gridNoData.end()) {
    std::cout << "0,0 exists" << '\n';
} else {
    std::cout << "0,0 doesn't exist\n";
}

auto search = gridWithData.find(point(0,0));
if (search != gridWithData.end()) {
    std::cout << "0,0 exists with value" << search->second  << '\n';
} else {
    std::cout << "0,0 doesn't exist\n";
}

我在类似的设置中使用了上面的类，我们使用了定义为：

std::map<position,directionalState> exploredMap;

如果我们在某个位置发现了墙壁。

通过使用这种基于std::map的方法，您不必通过数学来知道2D数组(或类似的结构)中必须有哪些偏移量。它也允许你自由移动，因为你不可能超出你在建筑中设定的预定界限。这种结构与二维阵列相比也更有空间效率，因为这种结构只节省了机器人所处的区域。这也是一种C++的做事方式:依赖STL，而不是使用C构造创建自己的2D地图。

Answer 2

在这里您可以编写一个class来帮助您：

class RoboArray 
{
     constexpr int width_ = ...
     constexpr int height_ = ...
     Cell grid_[width_ * 2][height_ * 2];
     ...
 public:
     ...
     Cell get(int x, int y) // can make this use [x][y] notation with a helper class
     {
           return grid_[x + width_][y + height];
     }
     ...
}

Answer 3

你有以下选择：

• 做个补偿。简单又肮脏。您的网格是100x100，但是存储-50，-50到50x50。
• 有多个偏移的网格。当您走出网格时，在它旁边分配一个新的，具有不同的偏移量。网格的列表或地图。
• 有稀疏的结构。一组或一幅坐标图。
• 有等级结构。你的整体，比如说50x50，网格是一个更高层次的网格中的一个单元。用一个链表或其他东西来实现它，所以当你移动时，你构建了一棵嵌套网格树。对于内存和计算时间非常有效，但实现起来要复杂得多。