# 空间哈希原理与应用

## 一、核心问题

在3D空间中进行几何查询时，最直接的方法是遍历所有几何体，但这会导致巨大的计算量。

**示例场景**：

- 10,000个查询点
- 10,000个三角形
- 暴力方法：1亿次相交测试

## 二、空间哈希基本原理

空间哈希是一种空间索引数据结构，通过将空间划分成规则网格，预先将几何体分类到对应的格子中，查询时只检查相关格子内的几何体。

### 2.1 核心思想

```
空间划分 → 几何体分类 → 快速查询
```

### 2.2 数据结构

```csharp
Dictionary<int, List<Geometry>> spatialHash;
// Key: 格子的哈希值
// Value: 该格子内的几何体列表
```

## 三、工作流程

### 3.1 构建阶段（Build Phase）

#### 步骤1：确定空间范围和格子大小

```csharp
BoundingBox bounds = CalculateBounds(allGeometry);
double cellSize = gridSize * 2; // 经验值
```

#### 步骤2：计算每个几何体覆盖的格子

```
三角形投影到2D平面：
      /\
     /  \      覆盖格子：[2,3,7,8]
    /____\
   
网格划分：
┌─┬─┬─┬─┬─┐
│0│1│2│3│4│
├─┼─┼─┼─┼─┤
│5│6│7│8│9│
└─┴─┴─┴─┴─┘
```

#### 步骤3：建立哈希映射

```csharp
foreach (var triangle in triangles)
{
    var coveredCells = GetCoveredCells(triangle);
    foreach (var cell in coveredCells)
    {
        int hash = cell.X * GRID_WIDTH + cell.Y;
        spatialHash[hash].Add(triangle);
    }
}
```

### 3.2 查询阶段（Query Phase）

#### 步骤1：计算查询点所在格子

```csharp
int gridX = (int)(queryPoint.X / cellSize);
int gridY = (int)(queryPoint.Y / cellSize);
int hash = gridX * GRID_WIDTH + gridY;
```

#### 步骤2：获取该格子的几何体

```csharp
var localGeometry = spatialHash[hash];
// 只返回少量相关几何体，而不是全部
```

#### 步骤3：执行精确测试

```csharp
foreach (var geometry in localGeometry)
{
    if (ExactIntersectionTest(queryPoint, geometry))
        return true;
}
```

## 四、性能分析

### 4.1 时间复杂度

| 操作 | 暴力方法 | 空间哈希 |
|-----|---------|---------|
| 构建 | O(1) | O(n×m) |
| 单次查询 | O(n) | O(1)平均 |
| k次查询 | O(k×n) | O(k) |

- n: 几何体数量
- m: 平均每个几何体覆盖的格子数
- k: 查询次数

### 4.2 空间复杂度

```
内存占用 = 格子数量 × 每格平均几何体数 × 引用大小
        ≈ O(n×m)
```

### 4.3 实际性能提升

```
示例：L型通道（5000个三角形）
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
暴力方法：
  每个查询点 × 5000个三角形 = 5000次测试

空间哈希（cellSize = 1.0m）：
  格子数量：~100个
  每格平均三角形：~50个
  每次查询：~50次测试

性能提升：100倍
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
```

## 五、参数选择

### 5.1 cellSize 选择

cellSize 是最关键的参数，影响性能和内存占用。

#### 太小的问题

- 格子数量多 → 内存占用大
- 几何体被分到多个格子 → 构建时间长
- 哈希表变大 → 缓存性能差

#### 太大的问题

- 每格包含太多几何体 → 筛选效果差
- 退化成暴力搜索

#### 最佳实践

```csharp
cellSize = averageGeometrySize * 2
// 或
cellSize = queryGridSize * 2
```

### 5.2 哈希函数选择

```csharp
// 简单哈希（推荐）
int hash = x * LARGE_PRIME + y;

// 莫顿码（Z-order）
int hash = MortonEncode(x, y); // 保持空间局部性

// 避免冲突
int hash = (x * 73856093) ^ (y * 19349663);
```

## 六、优化技巧

### 6.1 层次化空间哈希

```csharp
class HierarchicalSpatialHash
{
    SpatialHash coarseLevel; // 10m × 10m
    SpatialHash fineLevel;   // 1m × 1m
    
    List<Geometry> Query(Point p)
    {
        // 先查询粗粒度
        var candidates = coarseLevel.Query(p);
        // 再查询细粒度
        return fineLevel.Query(p, candidates);
    }
}
```

### 6.2 动态更新

```csharp
// 移除旧位置
spatialHash[oldHash].Remove(geometry);
// 添加到新位置
spatialHash[newHash].Add(geometry);
```

### 6.3 并行构建

```csharp
Parallel.ForEach(triangles, triangle =>
{
    var cells = GetCoveredCells(triangle);
    lock (spatialHash)
    {
        foreach (var cell in cells)
            spatialHash[cell].Add(triangle);
    }
});
```

## 七、适用场景

### 7.1 适合空间哈希的场景

✅ **均匀分布**的几何体
✅ **大量查询**的场景
✅ **2D/2.5D**空间查询
✅ **静态或缓慢变化**的几何体
✅ **局部性查询**（查询点附近）

### 7.2 不适合的场景

❌ 极度不均匀分布（考虑四叉树）
❌ 动态场景频繁更新（考虑松散四叉树）
❌ 稀疏数据（考虑KD树）
❌ 需要最近邻查询（考虑R树）

## 八、与其他数据结构对比

| 数据结构 | 构建时间 | 查询时间 | 内存占用 | 适用场景 |
|---------|---------|---------|---------|---------|
| **空间哈希** | O(n) | O(1) | 中等 | 均匀分布 |
| 四叉树/八叉树 | O(nlogn) | O(logn) | 较大 | 不均匀分布 |
| KD树 | O(nlogn) | O(logn) | 较小 | 最近邻查询 |
| BVH | O(nlogn) | O(logn) | 中等 | 光线追踪 |
| R树 | O(nlogn) | O(logn) | 较大 | 范围查询 |

## 九、实现示例

### 9.1 完整的空间哈希类

```csharp
public class SpatialHash<T> where T : IHasBounds
{
    private Dictionary<int, List<T>> hash;
    private double cellSize;
    private int gridWidth;
    
    public SpatialHash(double cellSize, int gridWidth = 10000)
    {
        this.cellSize = cellSize;
        this.gridWidth = gridWidth;
        hash = new Dictionary<int, List<T>>();
    }
    
    public void Add(T item)
    {
        var bounds = item.GetBounds();
        var minCell = WorldToGrid(bounds.Min);
        var maxCell = WorldToGrid(bounds.Max);
        
        for (int x = minCell.X; x <= maxCell.X; x++)
        {
            for (int y = minCell.Y; y <= maxCell.Y; y++)
            {
                int key = GetHash(x, y);
                if (!hash.ContainsKey(key))
                    hash[key] = new List<T>();
                hash[key].Add(item);
            }
        }
    }
    
    public List<T> Query(Point2D point)
    {
        var grid = WorldToGrid(point);
        int key = GetHash(grid.X, grid.Y);
        return hash.ContainsKey(key) ? hash[key] : new List<T>();
    }
    
    private Point2I WorldToGrid(Point2D world)
    {
        return new Point2I(
            (int)(world.X / cellSize),
            (int)(world.Y / cellSize)
        );
    }
    
    private int GetHash(int x, int y)
    {
        return x * gridWidth + y;
    }
}
```

### 9.2 使用示例

```csharp
// 构建
var spatialHash = new SpatialHash<Triangle3D>(1.0);
foreach (var triangle in triangles)
{
    spatialHash.Add(triangle);
}

// 查询
var point = new Point2D(10.5, 20.3);
var localTriangles = spatialHash.Query(point);
// 只返回相关的几个三角形，而不是全部

// 精确测试
foreach (var triangle in localTriangles)
{
    if (RayTriangleIntersect(point, triangle))
    {
        // 找到相交
        break;
    }
}
```

## 十、总结

空间哈希是一种简单高效的空间索引结构，特别适合：

- 均匀分布的数据
- 大量的点查询
- 2D/2.5D场景

通过合理的参数选择和优化，可以将查询性能提升100-1000倍，是路径规划等场景的理想选择。