# cartographer/mapping/2d/probability_grid.h

## Overview

`ProbabilityGrid` is a 2D occupancy grid using log-odds representation. Each cell stores the log-odds of occupancy, allowing efficient Bayesian updates during range data insertion.

## Class: `cartographer::mapping::ProbabilityGrid`

### Inheritance

```
Grid2D (abstract)
└── ProbabilityGrid
```

### Grid2D Interface

```cpp
class Grid2D {
 public:
  virtual ~Grid2D() {}
  virtual const MapLimits& limits() const = 0;
  virtual float GetProbability(const Eigen::Array2i& cell_index) const = 0;
  virtual bool IsKnown(const Eigen::Array2i& cell_index) const = 0;
  virtual void SetProbability(const Eigen::Array2i& cell_index,
                              float probability) = 0;
};
```

### ProbabilityGrid Methods

#### Construction

```cpp
explicit ProbabilityGrid(const MapLimits& limits);
ProbabilityGrid(const proto::ProbabilityGrid2D& proto,
                const MapLimits& limits);
```

#### Grid Access

```cpp
const MapLimits& limits() const override;
float GetProbability(const Eigen::Array2i& cell_index) const override;
bool IsKnown(const Eigen::Array2i& cell_index) const override;
void SetProbability(const Eigen::Array2i& cell_index,
                    float probability) override;
```

#### Iteration

```cpp
void ApplyToCells(const std::function<void(const Eigen::Array2i&)>& function) const;
```

Calls function for every known cell.

#### Serialization

```cpp
proto::ProbabilityGrid2D ToProto() const;
void ToProto(proto::ProbabilityGrid2D* proto) const;
```

### Log-Odds Representation

Internally stores **log-odds** (logit) values:
```
log_odds = log(p / (1 - p))
```

Where `p` is the occupancy probability.

**Advantages:**
- Bayesian updates become addition: `log_odds_new = log_odds_prior + log_odds_measurement`
- No division or clamping during updates
- Efficient incremental updates

### Constants

```cpp
constexpr int16 kMaxCorrespondenceCost = 32767;
constexpr int16 kMinCorrespondenceCost = 0;
constexpr int16 kUnknownCorrespondenceCost = 32767;
```

Correspondence cost maps to probability:
- `0` → probability 1.0 (occupied)
- `32767` → probability 0.0 (free) or unknown

### Correspondence Cost

Used for scan matching cost computation:
```cpp
int GetCorrespondenceCost(const Eigen::Array2i& cell_index) const;
```

Returns cost in `[0, 32767]` where lower = more likely occupied.

### Conversion Functions

```cpp
static float ProbabilityToCorrespondenceCost(float probability);
static float CorrespondenceCostToProbability(int correspondence_cost);
```

### MapLimits

Defines the grid bounds and resolution:
```cpp
struct MapLimits {
  double resolution;           // Meters per cell
  Eigen::Vector2d max;         // Max x, y in grid frame
  Eigen::Array2i cell_limits;  // Number of cells (x, y)
  
  Eigen::Array2i GetCellIndex(const Eigen::Vector2f& point) const;
  Eigen::Vector2f GetCellCenter(const Eigen::Array2i& cell_index) const;
  bool Contains(const Eigen::Array2i& cell_index) const;
};
```

## ProbabilityGridRangeDataInserter2D

Located in `probability_grid_range_data_inserter_2d.h/.cc`.

### Insertion Algorithm

For each range data insertion:
1. **Hit cells** (returns) → Increase occupancy probability
2. **Miss cells** (free space along rays) → Decrease occupancy probability

```cpp
struct Options {
  bool insert_free_space = true;
  float hit_probability = 0.55;
  float miss_probability = 0.49;
};
```

**Update equations:**
- Hit: `log_odds += log(hit_prob / (1 - hit_prob))`
- Miss: `log_odds += log(miss_prob / (1 - miss_prob))`

With defaults: hit adds ~0.2, miss adds ~-0.04 (slight free space bias).

### Ray Casting

Uses Bresenham's algorithm to trace rays from origin to returns/misses.

## Usage

```cpp
// Create grid
MapLimits limits(0.05, Eigen::Vector2d(50, 50), Eigen::Array2i(1000, 1000));
ProbabilityGrid grid(limits);

// Insert range data
ProbabilityGridRangeDataInserter2D inserter(options);
inserter.Insert(range_data, &grid);

// Query probability
Eigen::Array2i cell = limits.GetCellIndex(Eigen::Vector2f(1.0, 2.0));
float prob = grid.GetProbability(cell);

// For scan matching: get correspondence cost
int cost = grid.GetCorrespondenceCost(cell);
```

## Configuration

From `trajectory_builder_2d.lua`:
```lua
range_data_inserter = {
  probability_grid_range_data_inserter = {
    insert_free_space = true,
    hit_probability = 0.55,
    miss_probability = 0.49,
  },
}
```

## See Also

- [TSDF](submap_2d.md) — Alternative 2D representation
- [Submap2D](submap_2d.md) — Submap using ProbabilityGrid