1
ZBAA SID TEPID G212 VYK STAR ZSPD

1
-- 航路表的核心字段
2
CREATE TABLE tbl_enroute_airways (
3
    route_identifier TEXT,    -- 航路名称，如 "G212"
4
    seqno INTEGER,            -- 顺序号，1,2,3...
5
    waypoint_identifier TEXT, -- 航点标识，如 "TEPID"
6
    waypoint_latitude REAL,
7
    waypoint_longitude REAL,
8
    -- ... 其他字段
9
);

1
#[derive(Debug, Clone, Hash, Eq, PartialEq)]
2
struct NodeKey {
3
    identifier: String,
4
    latitude: i32,  // 存储为整数，避免浮点精度问题
5
    longitude: i32,
6
}
7

8
impl NodeKey {
9
    fn from_coord(identifier: &str, coord: &Coordinate) -> Self {
10
        // 保留4位小数精度，转换成整数
11
        let lat = (coord.latitude * 10000.0).round() as i32;
12
        let lon = (coord.longitude * 10000.0).round() as i32;
13
        Self {
14
            identifier: identifier.to_string(),
15
            latitude: lat,
16
            longitude: lon,
17
        }
18
    }
19
}

1
struct Edge {
2
    to_idx: usize,           // 目标节点索引
3
    airway: String,          // 航路名称，如 "G212"
4
    distance_nm: f64,        // 这段航路的长度（海里）
5
    direction: Direction,    // 方向限制（单向/双向）
6
}

1
pub fn build_graph(&self) -> Result<AirwayGraph> {
2
    let mut graph = AirwayGraph::new();
3

4
    // 1. 加载所有航路边（连续航点对）
5
    let edges = self.load_all_airway_edges()?;
6

7
    for (airway, from_id, from_coord, to_id, to_coord, direction) in edges {
8
        // 2. 为航点创建或获取节点索引
9
        let from_idx = graph.get_or_create_node(&from_id, from_coord);
10
        let to_idx = graph.get_or_create_node(&to_id, to_coord);
11

12
        // 3. 计算大圆距离
13
        let distance = haversine_distance_nm(&from_coord, &to_coord);
14

15
        // 4. 根据方向限制添加边
16
        match direction.as_str() {
17
            "BOTH" => {
18
                graph.add_edge(from_idx, to_idx, &airway, distance);
19
                graph.add_edge(to_idx, from_idx, &airway, distance);
20
            }
21
            "FORWARD" => {
22
                graph.add_edge(from_idx, to_idx, &airway, distance);
23
            }
24
            "BACKWARD" => {
25
                graph.add_edge(to_idx, from_idx, &airway, distance);
26
            }
27
            _ => {} // 忽略无效方向
28
        }
29
    }
30

31
    Ok(graph)
32
}

1
fn dijkstra(
2
    &self,
3
    graph: &AirwayGraph,
4
    start_idx: usize,
5
    end_idx: usize,
6
) -> Option<(Vec<PathEntry>, f64)> {
7
    let mut dist = vec![f64::INFINITY; graph.nodes.len()];
8
    let mut prev = vec![None; graph.nodes.len()];
9
    let mut prev_airway = vec![None; graph.nodes.len()];
10

11
    dist[start_idx] = 0.0;
12

13
    // 使用BinaryHeap作为优先队列
14
    let mut heap = BinaryHeap::new();
15
    heap.push(State {
16
        cost: 0.0,
17
        node: start_idx,
18
    });
19

20
    while let Some(State { cost, node }) = heap.pop() {
21
        if node == end_idx {
22
            // 重建路径
23
            return Some(self.reconstruct_path(&prev, &prev_airway, end_idx));
24
        }
25

26
        if cost > dist[node] {
27
            continue;
28
        }
29

30
        for edge in &graph.adjacency[node] {
31
            let next = State {
32
                cost: cost + edge.distance_nm,
33
                node: edge.to_idx,
34
            };
35

36
            if next.cost < dist[edge.to_idx] {
37
                dist[edge.to_idx] = next.cost;
38
                prev[edge.to_idx] = Some(node);
39
                prev_airway[edge.to_idx] = Some(edge.airway.clone());
40
                heap.push(next);
41
            }
42
        }
43
    }
44

45
    None
46
}

1
impl Ord for State {
2
    fn cmp(&self, other: &Self) -> Ordering {
3
        other.cost.partial_cmp(&self.cost).unwrap_or(Ordering::Equal)
4
    }
5
}

1
fn bidirectional_dijkstra(&self, start: usize, end: usize) -> Option<Path> {
2
    let mut forward_dist = vec![f64::INFINITY; self.node_count];
3
    let mut backward_dist = vec![f64::INFINITY; self.node_count];
4
    let mut forward_heap = BinaryHeap::new();
5
    let mut backward_heap = BinaryHeap::new();
6

7
    forward_dist[start] = 0.0;
8
    backward_dist[end] = 0.0;
9

10
    forward_heap.push(State { cost: 0.0, node: start });
11
    backward_heap.push(State { cost: 0.0, node: end });
12

13
    let mut best_path_cost = f64::INFINITY;
14
    let mut meeting_node = None;
15

16
    while let (Some(f), Some(b)) = (forward_heap.peek(), backward_heap.peek()) {
17
        // 如果两个搜索的最优值之和已经超过已知最优路径，可以提前终止
18
        if f.cost + b.cost >= best_path_cost {
19
            break;
20
        }
21

22
        // 正向搜索一步
23
        if let Some(State { cost, node }) = forward_heap.pop() {
24
            if cost <= forward_dist[node] {
25
                for edge in &self.forward_adj[node] {
26
                    let new_cost = cost + edge.distance;
27
                    if new_cost < forward_dist[edge.to] {
28
                        forward_dist[edge.to] = new_cost;
29
                        forward_heap.push(State { cost: new_cost, node: edge.to });
30

31
                        // 检查是否与反向搜索相遇
32
                        if backward_dist[edge.to] < f64::INFINITY {
33
                            let total = new_cost + backward_dist[edge.to];
34
                            if total < best_path_cost {
35
                                best_path_cost = total;
36
                                meeting_node = Some(edge.to);
37
                            }
38
                        }
39
                    }
40
                }
41
            }
42
        }
43

44
        // 类似的反向搜索...
45
    }
46

47
    // 重建路径...
48
}

1
fn filter_graph_by_flight_level(&self, graph: &AirwayGraph, level: FlightLevel) -> FilteredGraph {
2
    let filtered_adj: Vec<Vec<Edge>> = graph.adjacency
3
        .iter()
4
        .map(|edges| {
5
            edges.iter()
6
                .filter(|e| match level {
7
                    FlightLevel::High => e.route_type == RouteType::High || e.route_type == RouteType::RNAV,
8
                    FlightLevel::Low => e.route_type == RouteType::Low,
9
                    _ => true,
10
                })
11
                .cloned()
12
                .collect()
13
        })
14
        .collect();
15

16
    FilteredGraph {
17
        adjacency: filtered_adj,
18
        nodes: graph.nodes.clone(),
19
    }
20
}

1
fn contract_graph(&self, graph: &AirwayGraph) -> ContractedGraph {
2
    let mut contracted = graph.clone();
3

4
    loop {
5
        let mut contracted_any = false;
6
        let nodes_to_remove: Vec<usize> = contracted.nodes
7
            .iter()
8
            .enumerate()
9
            .filter(|(idx, _)| {
10
                let degree = contracted.adjacency[*idx].len();
11
                degree == 2 // 度数为2的节点可以收缩
12
            })
13
            .map(|(idx, _)| idx)
14
            .collect();
15

16
        for idx in nodes_to_remove {
17
            if contracted.adjacency[idx].len() == 2 {
18
                let edge1 = &contracted.adjacency[idx][0];
19
                let edge2 = &contracted.adjacency[idx][1];
20

21
                // 创建一条新的边，跳过中间节点
22
                let new_distance = edge1.distance_nm + edge2.distance_nm;
23
                let new_airway = if edge1.airway == edge2.airway {
24
                    edge1.airway.clone() // 同一条航路
25
                } else {
26
                    format!("{}/{}", edge1.airway, edge2.airway) // 不同航路
27
                };
28

29
                contracted.add_edge(edge1.to_idx, edge2.to_idx, &new_airway, new_distance);
30
                contracted.remove_node(idx);
31
                contracted_any = true;
32
            }
33
        }
34

35
        if !contracted_any {
36
            break;
37
        }
38
    }
39

40
    contracted
41
}

1
pub fn haversine_distance_nm(coord1: &Coordinate, coord2: &Coordinate) -> f64 {
2
    const EARTH_RADIUS_NM: f64 = 3440.065; // 地球半径（海里）
3

4
    let lat1 = coord1.latitude.to_radians();
5
    let lat2 = coord2.latitude.to_radians();
6
    let dlat = (coord2.latitude - coord1.latitude).to_radians();
7
    let dlon = (coord2.longitude - coord1.longitude).to_radians();
8

9
    let a = (dlat / 2.0).sin().powi(2)
10
          + lat1.cos() * lat2.cos() * (dlon / 2.0).sin().powi(2);
11
    let c = 2.0 * a.sqrt().atan2((1.0 - a).sqrt());
12

13
    EARTH_RADIUS_NM * c
14
}

1
#[derive(Clone)]
2
struct CachedCoord {
3
    coord: Coordinate,
4
    lat_rad: f64,
5
    sin_lat: f64,
6
    cos_lat: f64,
7
}
8

9
impl CachedCoord {
10
    fn from_coord(coord: Coordinate) -> Self {
11
        let lat_rad = coord.latitude.to_radians();
12
        Self {
13
            coord,
14
            lat_rad,
15
            sin_lat: lat_rad.sin(),
16
            cos_lat: lat_rad.cos(),
17
        }
18
    }
19

20
    fn distance_to(&self, other: &CachedCoord) -> f64 {
21
        let dlat = (other.coord.latitude - self.coord.latitude).to_radians();
22
        let dlon = (other.coord.longitude - self.coord.longitude).to_radians();
23

24
        let a = (dlat / 2.0).sin().powi(2)
25
              + self.cos_lat * other.cos_lat * (dlon / 2.0).sin().powi(2);
26
        let c = 2.0 * a.sqrt().atan2((1.0 - a).sqrt());
27

28
        EARTH_RADIUS_NM * c
29
    }
30
}

1
pub fn fast_distance_nm(coord1: &Coordinate, coord2: &Coordinate) -> f64 {
2
    let dlat = (coord2.latitude - coord1.latitude) * 60.0; // 纬度差（海里）
3
    let dlon = (coord2.longitude - coord1.longitude) * 60.0
4
               * coord1.latitude.to_radians().cos(); // 经度差（海里）
5

6
    (dlat.powi(2) + dlon.powi(2)).sqrt()
7
}

1
use rstar::{RTree, RTreeObject, AABB};
2

3
#[derive(Debug, Clone)]
4
struct SpatialWaypoint {
5
    waypoint: Waypoint,
6
}
7

8
impl RTreeObject for SpatialWaypoint {
9
    type Envelope = AABB<[f64; 2]>;
10

11
    fn envelope(&self) -> Self::Envelope {
12
        let point = [
13
            self.waypoint.coordinate.longitude,
14
            self.waypoint.coordinate.latitude,
15
        ];
16
        AABB::from_point(point)
17
    }
18
}
19

20
pub struct SpatialIndex {
21
    rtree: RTree<SpatialWaypoint>,
22
}

1
pub fn find_nearest(&self, coord: &Coordinate) -> Option<Waypoint> {
2
    let mut radius = 10.0; // 起始半径10海里
3
    let max_radius = 500.0; // 最大500海里
4

5
    while radius <= max_radius {
6
        let candidates = self.find_within_radius(coord, radius);
7
        if !candidates.is_empty() {
8
            return candidates
9
                .into_iter()
10
                .min_by(|a, b| {
11
                    let dist_a = haversine_distance_nm(coord, &a.coordinate);
12
                    let dist_b = haversine_distance_nm(coord, &b.coordinate);
13
                    dist_a.partial_cmp(&dist_b).unwrap()
14
                });
15
        }
16
        radius *= 2.0; // 指数增长，快速扩大范围
17
    }
18

19
    None
20
}