第12章：图与空间搜索

在大型建筑信息模型中，元素之间的关系往往比元素本身更重要。一堵墙连接着哪些楼板？疏散路径如何穿越楼层平面？怎样在海量构件中快速找到与某根管道发生碰撞的元素？这些问题的答案都指向同一类数据结构——图与空间索引。

Elements 在 Elements.Search 命名空间下提供了三类核心工具：

组件	类型	用途
`Network<T>`	图 / 网络	节点-边图结构，支持遍历、闭区域查找、可视化
`PointOctree<T>`	八叉树空间索引	动态八叉树，支持点的空间插入、范围查询、射线查询
`BinaryTree<T>`	二叉搜索树	有序空间分割，内部用于扫描线算法

此外还有一套辅助比较器（DirectionComparer、DistanceComparer、DoubleToleranceComparer）和扫描线算法基础设施（LineSweepEvent、LeftMostPointComparer）。

12.1 Network 网络图

12.1.1 设计思想

Network<T> 是一个泛型图结构，本身不存储空间位置——节点用整数索引表示，空间坐标单独维护在 List<Vector3> 中。这种”图-空间分离”的设计使同一个网络可以关联多种空间数据（例如建筑平面、结构分析、能耗模拟），而无需复制图的拓扑结构。

namespace Elements.Search
{
    public class Network<T>
    {
        // 类型参数 T 是与每条边关联的数据类型
        // 例如：double（边长/权重）、string（线路名称）、自定义类
    }
}

类型参数 T 是边数据的类型。例如：

Network<double> — 边带权重（用于最短路径计算）
Network<string> — 边带标签（用于标识道路名称、管道类型）
Network<Wall> — 边引用具体的墙体元素

12.1.2 创建网络与添加节点/边

Network 的节点全由 AddVertex() 创建，返回整数索引。边通过 AddEdgeOneWay（单向）和 AddEdgeBothWays（双向）添加。

using Elements.Search;
using Elements.Geometry;
using System.Collections.Generic;

// 创建一个边数据为 double（权重/距离）的网络
var network = new Network<double>();

// 添加 5 个节点，返回值是它们在网络中的索引
int n0 = network.AddVertex();  // 索引 0
int n1 = network.AddVertex();  // 索引 1
int n2 = network.AddVertex();  // 索引 2
int n3 = network.AddVertex();  // 索引 3
int n4 = network.AddVertex();  // 索引 4

// 添加双向边（无向图）
network.AddEdgeBothWays(n0, n1, 5.0);   // 边长 5
network.AddEdgeBothWays(n0, n2, 3.0);   // 边长 3
network.AddEdgeBothWays(n1, n2, 2.0);   // 边长 2
network.AddEdgeBothWays(n1, n3, 4.0);   // 边长 4
network.AddEdgeBothWays(n2, n3, 6.0);   // 边长 6
network.AddEdgeBothWays(n3, n4, 7.0);   // 边长 7

// 添加单向边（有向图）
network.AddEdgeOneWay(n0, n4, 10.0);    // n0 → n4

// 独立维护节点位置列表
var nodeLocations = new List<Vector3>
{
    new Vector3(0, 0, 0),    // n0
    new Vector3(10, 0, 0),   // n1
    new Vector3(5, 8, 0),    // n2
    new Vector3(15, 8, 0),   // n3
    new Vector3(20, 0, 0),   // n4
};

Console.WriteLine($"节点数: {network.NodeCount()}");  // 输出: 节点数: 5

12.1.3 查询节点与边

// 获取某个节点的所有邻接边
IEnumerable<(int neighbor, double data)> edges = network.EdgesAt(n1);
foreach (var (neighbor, weight) in edges)
{
    Console.WriteLine($"n1 -> n{neighbor}, 权重: {weight}");
}
// 输出:
// n1 -> n0, 权重: 5
// n1 -> n2, 权重: 2
// n1 -> n3, 权重: 4

// 获取叶子节点（度数为 0 的节点）
List<int> leaves = network.LeafNodes();

// 获取分支节点（度数为 1 或更多的节点）
List<int> branches = network.BranchNodes();

12.1.4 NetworkNode 与 NetworkEdge（内部实现）

虽然 Network 的用户接口只暴露索引，但其内部使用 NetworkNode 和 NetworkEdge 传递几何信息：

// Elements 内部实现（仅展示概念）
internal class NetworkNode
{
    public int Id { get; }
    public Vector3 Position { get; }
    public int CountOfVisits { get; }  // 遍历计数（用于检测环）

    public void MarkVisited() { CountOfVisits++; }
}

internal class NetworkEdge
{
    public NetworkNode Start { get; }      // 起始节点
    public NetworkNode End { get; }        // 终止节点
    public Vector3 Direction { get; }      // 单位方向向量
    public bool IsVisited { get; set; }    // 遍历标记
    public NetworkEdge Opposite { get; }   // 反向边引用
}

每个 NetworkEdge 都有对应的 Opposite 边，方向相反。这种设计使得无向图中的环检测和闭区域查找变得直接——一条边在两个方向上的遍历状态可以独立追踪。

12.1.5 VisitDirections：边访问方向

VisitDirections 是一个 [Flags] 枚举，被 LocalEdge 用于追踪一条边被遍历过的方向：

[Flags]
internal enum VisitDirections
{
    None = 0,
    Straight = 1,   // 从 Start 到 End 已遍历
    Opposite = 2    // 从 End 到 Start 已遍历
}

LocalEdge 是 Network 暴露给用户的一级边信息类型。它不存储位置，只记录两端节点索引和访问状态：

public class LocalEdge
{
    public int Start { get; }
    public int End { get; }

    // 标记从某节点方向已访问
    public void MarkAsVisited(int start);

    // 检查这条边是否在给定两个节点之间
    public bool IsBetweenVertices(int start, int end);

    // 检查是否已从某节点方向访问过
    public bool IsVisitedFromVertex(int vertexIndex);
}

12.1.6 NetworkCycleCoverage：环覆盖分析

NetworkCycleCoverage 是内部类，用于在网络中查找所有封闭区域。它的核心算法是”最大平面角遍历”——从一条边出发，每次选择平面角最大的邻接边前进，直至回到起点：

// 核心逻辑示意（From NetworkCycleCoverage）
// 从一条未访问边开始，沿最大平面角方向前进
var currEdge = startEdge;
do
{
    closedRegion.Add(currEdge);
    currEdge.IsVisited = true;
    currEdge = TraverseLargestPlaneAngle(currEdge);
} while (!currEdge.IsVisited && currEdge != startEdge);

调用方式是通过 Network.FindAllClosedRegions：

// 从 Network 的角度使用
List<List<int>> regions = network.FindAllClosedRegions(nodeLocations);

foreach (var region in regions)
{
    Console.WriteLine($"闭合区域: {string.Join(" -> ", region)}");
}

12.2 Network 的图算法

12.2.1 Traverse：通用图遍历框架

Network.Traverse 是 Elements 图遍历的核心方法。它接收一个遍历策略委托，使你可以实现任意遍历逻辑——最短路径、最大角度、自定义启发式等，而不需要修改 Network 本身。

public List<int> Traverse(
    int start,              // 起始节点索引
    Func<(int currentIndex, int previousIndex, IEnumerable<int> edgeIndices),
         List<Vector3>,     // allNodeLocations
         List<LocalEdge>,   // visitedEdges
         int> next,         // 遍历策略：返回下一个节点索引
    List<Vector3> allNodeLocations,
    List<LocalEdge> visitedEdges,
    out List<int> visited,  // 输出所有访问过的节点
    int prevIndex = -1
);

遍历策略委托的签名：

// 输入：当前节点、上一个节点、候选项列表
// 输出：下一个要前往的节点索引（-1 表示无路可走）
Func<(int currentIndex, int previousIndex, IEnumerable<int> edgeIndices),
     List<Vector3> allNodeLocations,
     List<LocalEdge> visitedEdges,
     int>

这个方法理解起来可能有些抽象，但它的精妙之处在于：所有的图算法（最短路径、连通分量、环检测）本质上只是”选择下一个节点的策略”不同。

12.2.2 内置遍历策略

Elements 内置了两种遍历策略：

TraverseSmallestPlaneAngle——选择”转角最小”的邻接边前进：

// 从当前节点出发，在未访问的邻接边中选择与入口边夹角最小的
// 这类似于"左手法则"——始终贴着最内侧走
public static int TraverseSmallestPlaneAngle(
    (int currentIndex, int previousIndex, IEnumerable<int> edgeIndices) traversalData,
    List<Vector3> allNodeLocations,
    List<LocalEdge> visitedEdges
);

TraverseLargestPlaneAngle——选择”转角最大”的邻接边前进：

// 类似于"右手法则"——始终贴着最外侧走
public static int TraverseLargestPlaneAngle(
    (int currentIndex, int previousIndex, IEnumerable<int> edgeIndices) traversalData,
    List<Vector3> allNodeLocations,
    List<LocalEdge> visitedEdges
);

两个策略互为镜像：SmallestPlaneAngle 沿”内圈”走，LargestPlaneAngle 沿”外圈”走。在封闭平面图中：

用 SmallestPlaneAngle 可以找到面（房间、面板）
用 LargestPlaneAngle 可以找到外轮廓

12.2.3 最短路径计算

Elements 没有内置 Dijkstra 实现，但借助 Traverse 框架，你可以轻松实现：

using Elements.Search;
using Elements.Geometry;
using System.Collections.Generic;
using System.Linq;

/// <summary>
/// 在 Network&lt;double&gt; 上使用 Dijkstra 算法计算最短路径。
/// 边数据 T = double 表示边长/权重。
/// </summary>
public static List<int> ShortestPath(
    Network<double> network,
    List<Vector3> nodeLocations,
    int start,
    int end)
{
    int n = network.NodeCount();
    var dist = new double[n];
    var prev = new int[n];
    var visited = new bool[n];

    for (int i = 0; i < n; i++)
    {
        dist[i] = double.MaxValue;
        prev[i] = -1;
    }
    dist[start] = 0;

    // 优先队列（用 SortedSet 模拟）
    var pq = new SortedSet<(double dist, int node)>();
    pq.Add((0, start));

    while (pq.Count > 0)
    {
        var (currentDist, u) = pq.Min;
        pq.Remove(pq.Min);

        if (u == end) break;
        if (visited[u]) continue;
        visited[u] = true;

        foreach (var (v, weight) in network.EdgesAt(u))
        {
            double alt = dist[u] + weight;
            if (alt < dist[v])
            {
                dist[v] = alt;
                prev[v] = u;
                pq.Add((alt, v));
            }
        }
    }

    // 回溯路径
    if (dist[end] == double.MaxValue) return new List<int>();

    var path = new List<int>();
    for (int at = end; at != -1; at = prev[at])
    {
        path.Add(at);
    }
    path.Reverse();
    return path;
}

// ---- 使用示例 ----
var net = new Network<double>();
int a = net.AddVertex(), b = net.AddVertex();
int c = net.AddVertex(), d = net.AddVertex();
int e = net.AddVertex();

net.AddEdgeBothWays(a, b, 7.0);
net.AddEdgeBothWays(a, c, 9.0);
net.AddEdgeBothWays(a, d, 14.0);
net.AddEdgeBothWays(b, c, 10.0);
net.AddEdgeBothWays(b, d, 15.0);
net.AddEdgeBothWays(c, d, 11.0);
net.AddEdgeBothWays(c, e, 2.0);
net.AddEdgeBothWays(d, e, 9.0);

var locs = new List<Vector3>
{
    new Vector3(0, 0, 0),   // a
    new Vector3(7, 0, 0),   // b
    new Vector3(0, 9, 0),   // c
    new Vector3(7, 9, 0),   // d
    new Vector3(2, 11, 0),  // e
};

var path = ShortestPath(net, locs, a, e);
Console.WriteLine($"最短路径: {string.Join(" -> ", path)}");
// 预期输出: 最短路径: 0 -> 2 -> 4  (A → C → E，总权重 11)

12.2.4 连通分量计算

利用深度优先搜索查找网络中的所有连通分量：

public static List<List<int>> ConnectedComponents(
    Network<double> network)
{
    int n = network.NodeCount();
    var visited = new bool[n];
    var components = new List<List<int>>();

    for (int i = 0; i < n; i++)
    {
        if (visited[i]) continue;

        var component = new List<int>();
        var stack = new Stack<int>();
        stack.Push(i);

        while (stack.Count > 0)
        {
            int node = stack.Pop();
            if (visited[node]) continue;
            visited[node] = true;
            component.Add(node);

            foreach (var (neighbor, _) in network.EdgesAt(node))
            {
                if (!visited[neighbor])
                    stack.Push(neighbor);
            }
        }

        components.Add(component);
    }

    return components;
}

12.2.5 FromSegmentableItems：线段交点到网络

Network.FromSegmentableItems 是 Elements 中一个强大但常被忽略的方法。它接收一组”可线段化”的对象（比如墙的中心线），自动计算所有交点，构建节点和边网络：

public static Network<T> FromSegmentableItems(
    IList<T> items,                         // 输入对象集合
    Func<T, Line> getSegment,               // 从对象提取线段
    out List<Vector3> allNodeLocations,     // 输出：所有节点位置
    out List<Vector3> allIntersectionLocations, // 输出：所有交点位置
    bool twoWayEdges = true                 // 是否创建双向边
);

这个方法内部使用了完整的扫描线算法（参见 12.5 节）——通过 LineSweepEvent、BinaryTree 和 LeftMostPointComparer 协同工作，时间复杂度为 O((n + k) log n)，其中 n 是线段数，k 是交点数。

使用示例——从一组墙创建房间网络：

using Elements;
using Elements.Geometry;
using Elements.Search;
using System.Collections.Generic;

// 创建一组墙（作为"可线段化"的对象）
var walls = new List<Wall>
{
    new Wall(new Line(new Vector3(0, 0, 0), new Vector3(10, 0, 0)),
             new Profile(Polygon.Rectangle(0.2, 3)), 3),
    new Wall(new Line(new Vector3(10, 0, 0), new Vector3(10, 8, 0)),
             new Profile(Polygon.Rectangle(0.2, 3)), 3),
    new Wall(new Line(new Vector3(10, 8, 0), new Vector3(0, 8, 0)),
             new Profile(Polygon.Rectangle(0.2, 3)), 3),
    new Wall(new Line(new Vector3(0, 8, 0), new Vector3(0, 0, 0)),
             new Profile(Polygon.Rectangle(0.2, 3)), 3),
    // 内墙
    new Wall(new Line(new Vector3(5, 0, 0), new Vector3(5, 8, 0)),
             new Profile(Polygon.Rectangle(0.2, 3)), 3),
};
var model = new Model();
model.AddElements(walls);

// 从墙的中心线构建网络（自动计算所有交点）
var wallNetwork = Network<Wall>.FromSegmentableItems(
    walls,
    wall => wall.GetCenterLine(),   // 提取中心线
    out var nodeLocations,
    out var intersectionLocations
);

Console.WriteLine($"网络节点数: {wallNetwork.NodeCount()}");
Console.WriteLine($"交点数: {intersectionLocations.Count}");

// 将网络可视化为 ModelCurve
var curves = wallNetwork.ToModelCurves(nodeLocations);
model.AddElements(curves);

12.2.6 网络可视化方法

Network 提供了三个可视化辅助方法，用于调试和展示：

// 1. 绘制为模型曲线（每条边一条线）
List<ModelCurve> curves = network.ToModelCurves(nodeLocations);
model.AddElements(curves);

// 2. 绘制为带箭头的有向线（显示方向）
ModelArrows arrows = network.ToModelArrows(nodeLocations, Colors.Red);
model.AddElement(arrows);

// 3. 绘制节点索引和邻接关系文本
List<ModelText> texts = network.ToModelText(nodeLocations, Colors.Blue);
model.AddElements(texts);

// 4. 将闭合区域绘制为面板
List<Panel> panels = network.ToBoundedAreaPanels(nodeLocations);
model.AddElements(panels);

12.3 Octree 八叉树空间索引

12.3.1 什么是八叉树

八叉树（Octree）是一种将三维空间递归划分为八个子空间（八分体）的树形数据结构。每个节点代表一个轴对齐的立方体，当节点内包含的对象超过容量时，节点分裂为八个子节点。

Elements 的 PointOctree<T> 是对 NetOctree 库的轻量包装，专为点状对象的空间索引设计。

          ┌─────┬─────┐
          │ NW  │ NE  │
          ├──┼──┼──┼──┤
          │ SW  │ SE  │
          └─────┴─────┘

    二维四叉树示意（八叉树的三维类比）

    根节点 (边长 = initialWorldSize)
    ├── 子节点 0 (边长 = size/2)
    │   ├── 子节点 0-0
    │   ├── ...
    ├── 子节点 1
    ├── ...
    ├── 子节点 7

12.3.2 创建 Octree

using Elements.Search;
using Elements.Geometry;

// PointOctree<T> 的 T 可以是任何类型
// 存储对象本身，位置在添加时单独提供
var octree = new PointOctree<string>(
    initialWorldSize: 100.0,              // 初始世界边长（米）
    initialWorldPos: new Vector3(50, 50, 0),  // 初始世界中心
    minNodeSize: 0.5                      // 最小节点边长
);

参数说明：

initialWorldSize：根节点的边长。八叉树永远不会收缩到比这更小。
initialWorldPos：根节点的中心位置。
minNodeSize：节点分裂的最小边长。如果新的子节点边长小于此值，节点不再分裂。

12.3.3 插入与删除

// 添加对象（对象 + 位置）
octree.Add("柱子-A", new Vector3(10, 20, 0));
octree.Add("柱子-B", new Vector3(30, 20, 0));
octree.Add("柱子-C", new Vector3(10, 50, 0));
octree.Add("管道-1", new Vector3(25, 35, 3));
octree.Add("管道-2", new Vector3(40, 45, 3));

Console.WriteLine($"当前对象数: {octree.Count}");   // 输出: 5

// 获取八叉树的总包围盒
BBox3 bounds = octree.MaxBounds;
Console.WriteLine($"覆盖范围: {bounds.Min} ~ {bounds.Max}");

// 删除对象（按引用删除）
octree.Remove("柱子-C");
Console.WriteLine($"删除后: {octree.Count}");       // 输出: 4

// 按位置精确删除（当对象可能在多处时使用）
octree.Remove("管道-1", new Vector3(25, 35, 3));

12.3.4 范围查询（GetNearby）

PointOctree 提供两种查询方式——按点查询和按射线查询：

按球体范围查询——返回距指定点 maxDistance 范围内的所有对象：

// 查询 (10, 30, 0) 周围 15 米内的所有对象
var nearby = octree.GetNearby(
    new Vector3(10, 30, 0),   // 查询中心
    15.0                       // 半径（米）
);

foreach (var obj in nearby)
{
    Console.WriteLine($"附近: {obj}");
}
// 输出: 柱子-A (距离原点约 10m)，附近 15m 内

按射线范围查询——返回与指定射线距离小于 maxDistance 的所有对象：

using Elements.Geometry;

// 从 (0, 20, 0) 向 +X 方向发出一条射线
var ray = new Ray(
    new Vector3(0, 20, 0),    // 射线起点
    Vector3.XAxis             // 射线方向
);

// 查询射线附近 2 米内的对象
var rayHits = octree.GetNearby(ray, 2.0);

foreach (var hit in rayHits)
{
    Console.WriteLine($"射线命中: {hit}");
}

射线查询特别适合”鼠标拾取”场景——用户在屏幕上点击，发出一条射线，精确找到被选中的建筑构件。

12.3.5 碰撞检测实战

下面的示例展示如何用 PointOctree 加速大规模模型的碰撞检测。直接做 O(n²) 的碰撞检测在 n=10000 时几乎不可行（约 5000 万次比较），而利用八叉树可以降到接近 O(n log n)：

using Elements;
using Elements.Geometry;
using Elements.Search;
using System.Collections.Generic;
using System.Linq;

/// <summary>
/// 用 PointOctree 加速碰撞检测。
/// 场景：检测新放置的 5000 根柱子是否与已有柱子碰撞。
/// </summary>
public class CollisionDetector
{
    private readonly PointOctree<Column> _octree;

    public CollisionDetector(double worldSize, Vector3 worldCenter)
    {
        _octree = new PointOctree<Column>(worldSize, worldCenter, minNodeSize: 0.1);
    }

    /// <summary>
    /// 向索引中添加一个已有的柱子。
    /// </summary>
    public void RegisterColumn(Column column)
    {
        _octree.Add(column, column.Location);
    }

    /// <summary>
    /// 检查新柱子是否与已有柱子碰撞。
    /// 假设柱子的碰撞半径是 0.5 米（柱子本身截面 + 安全距离）。
    /// </summary>
    public bool HasCollision(Column newColumn, double collisionRadius = 0.5)
    {
        // 关键：只检查附近的柱子，而非全部
        var nearby = _octree.GetNearby(newColumn.Location, collisionRadius);

        foreach (var existing in nearby)
        {
            double dist = newColumn.Location.DistanceTo(existing.Location);
            if (dist < collisionRadius)
                return true;
        }

        return false;
    }

    /// <summary>
    /// 批量生成柱子，自动检测并跳过碰撞位置。
    /// </summary>
    public List<Column> GenerateColumnsWithoutCollision(
        List<Vector3> candidatePositions,
        double height = 3.0,
        double collisionRadius = 0.5)
    {
        var profile = new Profile(Polygon.Rectangle(0.3, 0.3));
        var placed = new List<Column>();

        foreach (var pos in candidatePositions)
        {
            var col = new Column(pos, height, profile);

            if (!HasCollision(col, collisionRadius))
            {
                placed.Add(col);
                RegisterColumn(col);
            }
        }

        return placed;
    }
}

// ---- 使用 ----
var detector = new CollisionDetector(
    worldSize: 200.0,
    worldCenter: new Vector3(100, 100, 0)
);

// 随机生成 10000 个候选位置
var random = new Random(42);
var candidates = Enumerable.Range(0, 10000)
    .Select(_ => new Vector3(
        random.NextDouble() * 200,
        random.NextDouble() * 200,
        0))
    .ToList();

var placed = detector.GenerateColumnsWithoutCollision(candidates);
Console.WriteLine($"成功放置: {placed.Count} 根柱子（无碰撞）");

12.3.6 Octree 性能特性

操作	复杂度	说明
插入	O(log n) ~ O(n)	平衡时接近对数，最坏退化到线性
范围查询	O(log n + k)	k 为返回结果数
删除	O(log n)	按对象引用或位置删除
空间开销	O(n)	每个对象占用一个节点引用的空间

注意事项：

动态性：Octree 自动增长和收缩，无最大深度限制。
点是唯一索引维度：PointOctree 仅按点的位置索引，不存储对象的形状或大小。碰撞检测需要在查询结果上自行计算距离。
浮点精度：PointOctree 内部将 double 转换为 float（NetOctree 的约定），极端大坐标值可能引入精度损失。

12.4 BinaryTree 二叉树

12.4.1 概述

BinaryTree<T> 是一个内部泛型二叉搜索树，主要用于扫描线算法中的空间排序。开发者通常不直接使用它，但理解其工作机制有助于深入掌握 FromSegmentableItems 的内部原理。

internal class BinaryTree<T>
{
    public BinaryTreeNode<T> Root { get; set; }

    // 核心操作
    public bool Add(T value);                            // 插入
    public BinaryTreeNode<T> Find(T value);              // 查找
    public void Remove(T value);                         // 删除
    public void FindPredecessorSuccessor(                // 查找前驱/后继
        T data,
        out BinaryTreeNode<T> predecessor,
        out BinaryTreeNode<T> successor);
    public int GetTreeDepth();                           // 获取深度
}

12.4.2 比较驱动（Comparer-Driven）设计

与标准二叉搜索树不同，BinaryTree<T> 不要求 T 实现 IComparable<T>。排序逻辑完全由构造时传入的 IComparer<T> 决定：

public BinaryTree(IComparer<T> comparer)
{
    _comparer = comparer;
}

这使同一类型 T 可以根据不同维度构建不同的树——例如：

按 Y 坐标排序（LeftMostPointComparer）
按距离排序（DistanceComparer）
按方向相似度排序（DirectionComparer）

12.4.3 前驱/后继查找（FindPredecessorSuccessor）

这是 BinaryTree 在扫描线算法中最关键的方法。给定一个值 data，找出树中紧挨着它的”前一个”（predecessor）和”后一个”（successor）：

tree.FindPredecessorSuccessors(
    data,
    out List<BinaryTreeNode<T>> predecessors,
    out List<BinaryTreeNode<T>> successors
);

在扫描线算法中（参见 FromSegmentableItems），当扫描线遇到线段的左端点时，将该线段插入二叉树，并立即查找它的前驱和后继线段，以检测可能的交点。这使得交点检测从 O(n²) 降到了 O(n log n + k log n)。

12.4.4 与射线追踪的关系

虽然 BinaryTree 主要服务于扫描线算法，但二叉树在射线追踪中的原理是相同的——将场景按空间顺序组织，用二分查找快速排除不可能相交的物体。在 Elements 中，射线追踪本身更倾向于使用 PointOctree.GetNearby(Ray, ...)，而 BinaryTree 专注于有序的一维排序（如扫描线沿 Y 轴推进）。

12.5 LineSweepEvent 与扫描线算法

12.5.1 扫描线算法简介

扫描线算法（Plane Sweep / Line Sweep）是计算几何中的经典技术。它用一根假想的”扫描线”沿某一方向（通常是自上而下）移动，在遇到线段端点时触发事件，动态维护”活跃线段”集合，从而以接近线性的时间找出所有线段交点。

Elements 的 FromSegmentableItems 方法内部完整实现了该算法：

算法流程：
1. 收集所有线段的端点为"事件点"
2. 按 Y 坐标降序（从上到下）排列事件点
3. 创建空二叉树（按左端点 Y 坐标排序）
4. 遍历每个事件点：
   ├── 遇到左端点 → 线段插入二叉树 → 查找前驱/后继 → 检测交点
   └── 遇到右端点 → 查找前驱/后继 → 检测交点 → 线段从二叉树移除
5. 收集所有交点，构建 Network

12.5.2 LineSweepEvent

internal class LineSweepEvent<T>
{
    public Vector3 Point;    // 事件发生的坐标

    // 与该坐标关联的线段集合
    // 每条线段包含：(segmentId, isLeftMostPoint, data)
    public IEnumerable<(int segmentId, bool isLeftMostPoint, T data)> Segments;
}

一个事件点可能关联多条线段（例如，多面墙共用同一个角点），因此 Segments 是一个集合。

12.5.3 配套类型一览

类型	可见性	作用
`Network<T>`	public	图结构本体
`LocalEdge`	public	带访问状态的边描述
`PointOctree<T>`	public	八叉树空间索引
`DirectionComparer`	public	按方向”相似度”排序向量
`DistanceComparer`	public	按到参考点的距离排序
`DoubleToleranceComparer`	public	带容差的双精度比较
`BinaryTree<T>`	internal	二叉搜索树（扫描线核心）
`BinaryTreeNode<T>`	internal	二叉树节点
`LineSweepEvent<T>`	internal	扫描线事件
`LeftMostPointComparer<T>`	internal	按左端点 Y 坐标排序
`AdjacencyList<T>`	internal	邻接表（Network 底层存储）
`NetworkNode`	internal	带位置的网络节点
`NetworkEdge`	internal	带方向和对边的网络边
`NetworkCycleCoverage`	internal	环覆盖查找器
`VisitDirections`	internal	边访问方向枚举

12.5.4 扫描线算法的实际价值

在建筑建模中，”线段求交”是一个高频操作：

墙的中心线相交产生房间边界
管道布局需要检测管线交叉
轴网系统需要识别网格交叉点
楼板轮廓与开洞的布尔运算

所有这些场景背后都依赖扫描线算法。Elements 将它封装在 FromSegmentableItems 中，开发者无需手动实现交点检测逻辑。

12.6 实战示例

12.6.1 疏散路径图

下面的例子创建一个办公楼层的疏散路径图：以办公室、走廊、楼梯间为节点，以门和通道为边，计算从每个房间到最近楼梯间的最短路径。

using Elements;
using Elements.Geometry;
using Elements.Search;
using System.Collections.Generic;
using System.Linq;

// ---- 1. 定义楼层平面图 ----
// 节点：房间、走廊交叉点、楼梯间
var network = new Network<double>();
var positions = new List<Vector3>();

// 办公室节点
int office1 = AddNode(network, positions, new Vector3(2, 2, 0));   // 办公室 A
int office2 = AddNode(network, positions, new Vector3(12, 2, 0));  // 办公室 B
int office3 = AddNode(network, positions, new Vector3(2, 12, 0));  // 办公室 C
int office4 = AddNode(network, positions, new Vector3(12, 12, 0)); // 办公室 D

// 走廊节点
int hall1 = AddNode(network, positions, new Vector3(7, 3, 0));    // 走廊左中
int hall2 = AddNode(network, positions, new Vector3(7, 11, 0));   // 走廊右中
int hall3 = AddNode(network, positions, new Vector3(7, 7, 0));    // 走廊中心

// 楼梯间节点（安全出口）
int stair1 = AddNode(network, positions, new Vector3(7, 15, 0));  // 楼梯间 N
int stair2 = AddNode(network, positions, new Vector3(15, 7, 0));  // 楼梯间 E

// ---- 2. 添加边的连线（边权重 = 欧氏距离） ----
void Connect(Network<double> net, List<Vector3> locs, int a, int b)
{
    double dist = locs[a].DistanceTo(locs[b]);
    net.AddEdgeBothWays(a, b, dist);
}

// 办公室 → 走廊
Connect(network, positions, office1, hall1);
Connect(network, positions, office2, hall1);
Connect(network, positions, office3, hall2);
Connect(network, positions, office4, hall2);

// 走廊内部
Connect(network, positions, hall1, hall3);
Connect(network, positions, hall2, hall3);

// 走廊 → 楼梯间
Connect(network, positions, hall3, stair1);
Connect(network, positions, hall3, stair2);

// ---- 3. 计算每个办公室到最近楼梯间的最短路径 ----
var offices = new[] { office1, office2, office3, office4 };
var stairs = new[] { stair1, stair2 };
var officeNames = new[] { "办公室A", "办公室B", "办公室C", "办公室D" };
var stairNames = new[] { "楼梯间N", "楼梯间E" };

foreach (var officeIdx in offices)
{
    var bestPath = new List<int>();
    var bestDist = double.MaxValue;
    var bestStair = -1;

    foreach (var stairIdx in stairs)
    {
        var path = ShortestPath(network, positions, officeIdx, stairIdx);
        if (path.Count == 0) continue;

        double totalDist = 0;
        for (int i = 0; i < path.Count - 1; i++)
        {
            totalDist += positions[path[i]].DistanceTo(positions[path[i + 1]]);
        }

        if (totalDist < bestDist)
        {
            bestDist = totalDist;
            bestPath = path;
            bestStair = stairIdx;
        }
    }

    Console.WriteLine($"{officeNames[offices.ToList().IndexOf(officeIdx)]} → " +
        $"{stairNames[stairs.ToList().IndexOf(bestStair)]}: " +
        $"距离 {bestDist:F1}m, 路径: {string.Join(" → ", bestPath)}");
}
// 输出示例:
// 办公室A → 楼梯间N: 距离 10.2m, 路径: 0 → 4 → 6 → 8
// 办公室B → 楼梯间E: 距离 12.3m, 路径: 1 → 4 → 6 → 9
// ...

// ---- 辅助方法 ----
static int AddNode(Network<double> net, List<Vector3> locs, Vector3 pos)
{
    int idx = net.AddVertex();
    locs.Add(pos);
    return idx;
}

12.6.2 大规模碰撞检测（完整实例）

实战中更典型的场景：一个体育馆模型里，数千个 MEP 管道附件需要检测是否与结构梁碰撞。以下代码演示用 PointOctree 实现的高效管道-梁碰撞检测：

using Elements;
using Elements.Geometry;
using Elements.Search;
using System;
using System.Collections.Generic;
using System.Linq;

/// <summary>
/// MEP 管道与结构梁的碰撞检测器。
/// </summary>
public class MEPCollisionChecker
{
    private readonly PointOctree<Beam> _beamOctree;

    public MEPCollisionChecker(double worldSize, Vector3 worldCenter)
    {
        _beamOctree = new PointOctree<Beam>(
            worldSize, worldCenter, minNodeSize: 0.05);
    }

    /// <summary>
    /// 将所有梁注册到八叉树中。
    /// </summary>
    public void RegisterBeams(IEnumerable<Beam> beams)
    {
        foreach (var beam in beams)
        {
            // 用梁的中点作为八叉树中的位置
            var midPoint = beam.GetCenterLine().PointAt(0.5);
            _beamOctree.Add(beam, midPoint);
        }
    }

    /// <summary>
    /// 检查一段管道是否与任何梁碰撞。
    /// </summary>
    /// <param name="pipeLine">管道的中心线段</param>
    /// <param name="pipeDiameter">管道外径（米）</param>
    /// <param name="searchRadius">搜索半径（管道外径的一半 + 梁的半高 + 安全距离）</param>
    /// <returns>碰撞的梁的列表</returns>
    public List<Beam> FindPipeCollisions(
        Line pipeLine, double pipeDiameter, double searchRadius = 2.0)
    {
        var collisions = new List<Beam>();

        // 沿管道线段采样若干点进行查询（步长 = 管径）
        double length = pipeLine.Length();
        double step = Math.Max(pipeDiameter, 0.5);
        int samples = Math.Max(2, (int)(length / step) + 1);

        var checkedBeams = new HashSet<Guid>();

        for (int i = 0; i < samples; i++)
        {
            double t = (double)i / (samples - 1);
            var samplePoint = pipeLine.PointAt(t);

            var nearbyBeams = _beamOctree.GetNearby(samplePoint, searchRadius);

            foreach (var beam in nearbyBeams)
            {
                if (checkedBeams.Contains(beam.Id)) continue;
                checkedBeams.Add(beam.Id);

                // 精确检测：管道线段与梁的包围盒相交
                if (PipeIntersectsBeam(pipeLine, pipeDiameter, beam))
                {
                    collisions.Add(beam);
                }
            }
        }

        return collisions.Distinct().ToList();
    }

    private bool PipeIntersectsBeam(Line pipeLine, double pipeDiameter, Beam beam)
    {
        // 简化：用梁包围盒进行 AABB 检测
        var beamBbox = beam.Bounds;
        var pipeBbox = new BBox3(
            new Vector3(
                Math.Min(pipeLine.Start.X, pipeLine.End.X) - pipeDiameter / 2,
                Math.Min(pipeLine.Start.Y, pipeLine.End.Y) - pipeDiameter / 2,
                Math.Min(pipeLine.Start.Z, pipeLine.End.Z) - pipeDiameter / 2
            ),
            new Vector3(
                Math.Max(pipeLine.Start.X, pipeLine.End.X) + pipeDiameter / 2,
                Math.Max(pipeLine.Start.Y, pipeLine.End.Y) + pipeDiameter / 2,
                Math.Max(pipeLine.Start.Z, pipeLine.End.Z) + pipeDiameter / 2
            )
        );
        return pipeBbox.Intersects(beamBbox);
    }
}

// ---- 使用 ----
var checker = new MEPCollisionChecker(
    worldSize: 500.0,
    worldCenter: new Vector3(250, 250, 15));

// 加载所有梁（假设从模型获取）
var allBeams = model.AllElementsOfType<Beam>();
checker.RegisterBeams(allBeams);

// 检查一根 100 米的主管道的碰撞
var mainPipe = new Line(
    new Vector3(0, 50, 10),
    new Vector3(200, 50, 10)
);

var collisions = checker.FindPipeCollisions(mainPipe, pipeDiameter: 0.3);

if (collisions.Any())
{
    Console.WriteLine($"检测到 {collisions.Count} 处碰撞!");
    // 标记碰撞梁为红色
    foreach (var beam in collisions)
    {
        beam.Material = new Material("碰撞警告", Colors.Red);
    }
}
else
{
    Console.WriteLine("未检测到碰撞。");
}

12.6.3 用 Network 分析房间拓扑

建筑平面图中的房间常由墙的中心线围合而成。FromSegmentableItems 可以从墙线直接生成 Network，然后通过 FindAllClosedRegions 和 ToBoundedAreaPanels 提取房间轮廓：

using Elements;
using Elements.Geometry;
using Elements.Search;
using System.Collections.Generic;

// 用墙的中心线构建 Network
var walls = model.AllElementsOfType<Wall>();
var network = Network<Wall>.FromSegmentableItems(
    walls,
    wall => wall.GetCenterLine(),
    out var nodeLocations,
    out var intersectionLocations
);

Console.WriteLine($"从 {walls.Count} 面墙中提取了 {network.NodeCount()} 个节点");

// 查找所有闭合区域（房间）
var closedRegions = network.FindAllClosedRegions(nodeLocations);
Console.WriteLine($"找到 {closedRegions.Count} 个闭合区域");

// 将闭合区域转换为面板（可视化显示）
var panels = network.ToBoundedAreaPanels(nodeLocations);
model.AddElements(panels);

// 将网络边转换为模型曲线（显示网络结构）
var curves = network.ToModelCurves(nodeLocations);
model.AddElements(curves);

小结

本章覆盖了 Elements Search 命名空间的核心组件：

Network：图结构是建筑拓扑分析的基础。它不存储空间坐标，而是用整数索引引用外部位置列表——同一图可服务于多种空间分析。Traverse 方法提供的策略委托模式，使最短路径、最大角度遍历、环查找等算法都可以用统一的框架实现。
PointOctree：八叉树将 O(n²) 的碰撞检测降到接近 O(n log n)。对于数万构件的大模型，这是性能的分水岭。虽然仅按点索引（不存形状），但配合应用层的精确几何检测（AABB、射线交），可以实现高效而精确的空间查询。
BinaryTree 与扫描线：FromSegmentableItems 方法内部封装了完整的扫描线算法——LineSweepEvent 驱动事件、BinaryTree 管理活跃线段、LeftMostPointComparer 控制排序。开发者调用一个方法即可从一组线段自动生成网络拓扑。
辅助比较器：DirectionComparer、DistanceComparer 和 DoubleToleranceComparer 解决了几何计算中的常见需求——方向排序、距离排序和容差比较。

在实际项目中，Network 用于疏散分析、管线拓扑、房间关系建模；PointOctree 用于碰撞检测、空间查询、点云管理；而 FromSegmentableItems 则架起了”几何线段”与”图”之间的自动化桥梁。