OptionB的实现路径（用于写报告）

本文介绍了空间几何计算与四叉树索引的实现方法。主要内容包括：1）点与线、多边形距离计算，通过分解线段和射线法判断位置；2）Envelope类的空间关系判断，包含contain、intersect和unionEnvelope函数；3）四叉树构建与查询功能，包括区域查询和最近邻查询的实现策略；4）基于距离的空间关联算法。这些方法采用分层计算策略，先通过包围盒快速过滤，再进行精确几何计算，有效提高了空间

2301_80025611

929人浏览 · 2025-12-28 11:06:12

2301_80025611 · 2025-12-28 11:06:12 发布

一、Point到LineString和Polygon的欧式距离计算实现

1.Point到LineString的距离计算（在`Geometry.cpp`的`Point::distance(const LineString*)`中实现）

实现路径：

基本思路：将折线分解为多个线段，计算点到每个线段的最短距离，取最小值
点到线段距离算法：
- 首先计算点到折线第一个点的距离作为初始最小距离
- 对折线的每一条线段（点i到点i+1）：
  - 计算线段向量 (x2-x1, y2-y1)
  - 计算点到线段起点的向量 (x-x1, y-y1)
  - 判断投影点是否在线段上：
```
if((x - x2) * (x2 - x1) < (y2 - y1) * (y2 - y) && 
   (x-x1)*(x2-x1) + (y-y1)*(y2-y1) > 0)
```
    这里第一个条件检查叉积符号，第二个条件检查点积正负
  - 如果投影在线段上：使用垂线距离公式
```
dist = abs((x - x1) * (y2 - y1) + (y - y1) * (x2 - x1)) / 
       sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
```
  - 如果投影不在线段上：计算点到两个端点的距离，取较小值
```
dist = std::min(distance(&p1), distance(&p2));
```

1.Point到Polygon的距离计算（在`Geometry.cpp`的`Point::distance(const Polygon*)`中实现）

实现路径：

射线法判断点是否在多边形内：

for(int i = 0; i < n - 1; i++) {
    double x1 = line.getPointN(i).getX();
    double x2 = line.getPointN(i+1).getX();
    double y1 = line.getPointN(i).getY();
    double y2 = line.getPointN(i+1).getY();
    
    // 核心判断条件：射线与边相交
    if(((y1 > y) != (y2 > y)) and  // 点的y坐标在边的y坐标范围内
       (x < ((y - y1) * (x2 - x1) / (y2 - y1) + x1))) {  // 交点在点左侧
        is_odd = !is_odd;
    }
}
inPolygon = is_odd;  // 奇数次相交表示在内部

距离计算逻辑：
- 如果在多边形内：距离为0
- 如果在多边形外：调用Point::distance(const LineString*)计算点到多边形边界的距离

注意：你的代码中存在一个问题 - 点在多边形内时应该返回0，但你的实现中：

if (!inPolygon)
    mindist = this->distance(&line);

这会导致点在多边形内时mindist保持为初始值0，这是正确的。但应该在前面明确设置：

if (inPolygon) {
    return 0.0;
} else {
    return this->distance(&line);
}

二、Envelope类的contain、intersect和unionEnvelope函数实现

1. contain函数（包含关系判断）

实现路径：

bool Envelope::contain(const Envelope& envelope) const {
    // 判断当前包围盒是否完全包含另一个包围盒
    if(minX <= envelope.getMinX() && 
       maxX >= envelope.getMaxX() && 
       minY <= envelope.getMinY() && 
       maxY >= envelope.getMaxY()) {
        return true;
    }
    return false;
}

逻辑：当前包围盒的min小于等于目标包围盒的min，且max大于等于目标包围盒的max，表示完全包含。

2. intersect函数（相交判断）

实现路径：

bool Envelope::intersect(const Envelope& envelope) const {
    // 检查四种不相交的情况
    bool left = (minX > envelope.getMaxX());   // 当前在目标右侧
    bool right = (maxX < envelope.getMinX());  // 当前在目标左侧
    bool above = (maxY < envelope.getMinY());  // 当前在目标下方
    bool below = (minY > envelope.getMaxY());  // 当前在目标上方
    
    // 如果满足任何一种不相交情况，返回false
    if(left || right || above || below) return false;
    return true;
}

逻辑：使用分离轴定理，检查四个方向是否分离。

3. unionEnvelope函数（合并包围盒）

实现路径：

Envelope Envelope::unionEnvelope(const Envelope& envelope) const {
    // 取两个包围盒在各个维度上的最小值和最大值
    double x_min = std::min(minX, envelope.getMinX());
    double x_max = std::max(maxX, envelope.getMaxX());
    double y_min = std::min(minY, envelope.getMinY());
    double y_max = std::max(maxY, envelope.getMaxY());
    
    return Envelope(x_min, x_max, y_min, y_max);
}

逻辑：创建新的包围盒，其范围是两个原始包围盒在各个维度上的并集。

关键特点总结：

空间索引加速：这些几何计算函数在四叉树/R树中被大量调用：
- intersect()用于快速过滤不相交的节点
- contain()用于判断点是否在节点内
- unionEnvelope()用于构建父节点的包围盒
分层计算策略：
- 先通过包围盒进行快速过滤（Filter）
- 再执行精确的几何计算（Refinement）
代码优化点：
- 使用高效的算法（如射线法、分离轴定理）
- 避免不必要的计算（如点在多边形内时直接返回0）
- 利用向量运算简化几何计算

三、四叉树的构建与查询功能的实现

1. 实现 `constructQuadTree` 和 `split` 函数

实现位置：
- QuadTree::constructTree（已实现）
- QuadNode::split（已实现）
实现逻辑：
- 在 constructTree 中，先计算所有特征的总包围盒，创建根节点，将所有特征加入根节点。
- 调用 split 函数：
  - 如果节点特征数 > capacity，且为叶子节点，则创建四个子节点（SW、SE、NE、NW）。
  - 将特征根据包围盒重叠关系分配到子节点中。
  - 清空当前节点特征，使其成为内部节点。
  - 递归分裂子节点。
- 如果节点已经是内部节点，则递归分裂子节点。

核心代码段：

if (features.size() <= capacity) return;
if (!isLeafNode()) {
    for (int i = 0; i < 4; ++i) {
        if (children[i] != nullptr) children[i]->split(capacity);
    }
    return;
}
// 分裂叶子节点

2. 实现 `rangeQuery` 函数（区域查询）

实现位置：
- QuadNode::rangeQuery（已实现）
- QuadTree::rangeQuery（已实现）
实现逻辑：
- 首先判断节点包围盒与查询区域是否相交，不相交则剪枝。
- 如果是叶子节点，遍历特征，检查包围盒是否与查询区域相交（filter）。
- 如果是内部节点，递归查询子节点。
- 注意：特征可能出现在多个叶子节点中，返回结果可能包含重复项（通常需要去重）。

核心代码段：

if (!bbox.intersect(rect)) return;
if (isLeafNode()) {
    for (const auto& feat : features) {
        if (feat.getEnvelope().intersect(rect)) {
            result.push_back(feat);
        }
    }
} else {
    for (int i = 0; i < 4; ++i) {
        if (children[i] != nullptr) children[i]->rangeQuery(rect, result);
    }
}

3. 实现 `NNQuery` 和 `pointInLeafNode` 函数（最邻近查询）

实现位置：
- QuadNode::pointInLeafNode（已实现）
- QuadTree::NNQuery（已实现）
实现逻辑：
- pointInLeafNode：递归找到包含查询点的叶子节点。
- NNQuery：
  - 找到叶子节点。
  - 计算查询点到叶子节点中特征包围盒的最大距离的最小值 minDist。
  - 构造查询区域 [x ± minDist, y ± minDist]，调用 rangeQuery 获取候选集。
  - 在候选集中精确计算点到几何体的距离，找到最近特征（在测试代码中实现）。

核心代码段：

QuadNode* leaf = root->pointInLeafNode(x, y);
if (leaf && leaf->getFeatureNum() > 0) {
    for (size_t i = 0; i < leaf->getFeatureNum(); ++i) {
        double d = leaf->getFeature(i).maxDistance2Envelope(x, y);
        if (d < minDist) minDist = d;
    }
}
Envelope searchBox(x - minDist, x + minDist, y - minDist, y + minDist);
rangeQuery(searchBox, features);

4. 基于距离的空间关联（Spatial Join）

实现位置：
- QuadTree::spatialJoin（已实现）
实现逻辑：
- 外循环遍历集合 A（如道路）。
- 对每个特征 A，构造扩展包围盒 [minX - d, maxX + d, minY - d, maxY + d]。
- 在四叉树 B 上进行 rangeQuery 获取候选集。
- 精确计算几何体间距离（调用 Geometry::distance），筛选出距离 ≤ d 的对。

核心代码段：

Envelope searchRect(...);
treeB->rangeQuery(searchRect, candidates);
for (const auto& featB : candidates) {
    double dist = geomA->distance(geomB);
    if (dist <= distance) results.push_back({featA, featB});
}