squid_n_core/region_gen/
mod.rs

1//! 主架構が囲む閉領域（床領域・壁領域の境界）の検出。
2//!
3//! 床領域は「大梁で囲まれた領域ごとに 1 つ」、壁領域は「柱と梁が囲む鉛直構面内の
4//! 閉領域ごとに 1 つ」と定める。本モジュールは、その閉領域を主架構のトポロジーから
5//! 求める半辺（有向辺）面走査エンジン（[`scan_faces`]）を共有し、床（[`floor`]）と
6//! 壁（[`wall`]）がそれぞれ「対象部材の絞り込み」と「2 次元への射影」を用意して
7//! 同じ走査に載せる。
8//!
9//! 設計の経緯は `dev_docs/handoff/床領域・壁領域の再設計_申し送り.md` を参照。
10//!
11//! # 面走査エンジン（[`scan_faces`]）
12//!
13//! 1. **半辺**（有向辺）の一覧を作る。同じ節点対に複数の部材があっても、最初の 1 本だけを採る
14//!    （重複部材は面を増やさない）。
15//! 2. 各節点まわりの接続先を、`proj`（節点 → 局所 2D 座標）が返す座標の方位角の昇順に並べる。
16//! 3. 半辺 `u→v` の次を「`v` のまわりで `v→u` の 1 つ手前（時計回りに次）」とすると、
17//!    内部を左に見て一周する閉路が得られる（定型の面走査）。
18//! 4. 得られた閉路すべてを、符号付き面積つきで返す。**どれが外周面かの判別は呼び出し側が行う。**
19//!    床は「符号付き面積が負」で判別できる（グローバル XY・+Z を上とする固定の向きで
20//!    常に判定できるため）。壁は局所座標 `(s, z)` の水平方向 `s` が構面ごとに任意に決まり、
21//!    床と同じ絶対符号の規則を機械的に流用できるとは限らないため、[`wall`] が自身で
22//!    判別方法を持つ（[`wall`] のモジュールドキュメント参照）。
23//!
24//! `proj` が `None` を返す節点（節点が引けない陳腐化した参照）を含む閉路は捨てる。
25
26use crate::ids::{ElemId, NodeId};
27use std::collections::HashMap;
28
29pub mod floor;
30pub mod wall;
31
32pub use floor::{
33    crossing_beams, generate_region_boundaries, scan_region_boundaries, RegionBoundary,
34    RegionBoundaryScan,
35};
36pub use wall::{
37    generate_wall_region_boundaries, scan_wall_region_boundaries, WallRegionBoundary,
38    WallRegionBoundaryScan,
39};
40
41/// 面走査の入力となる 1 本の部材（無向の辺。半辺は本モジュールが内部で作る）。
42pub(crate) struct Edge {
43    pub a: NodeId,
44    pub b: NodeId,
45    pub elem: ElemId,
46}
47
48/// 面走査で見つかった 1 つの閉路。
49pub(crate) struct Face {
50    pub boundary: Vec<NodeId>,
51    pub edges: Vec<ElemId>,
52    /// `proj` が返す 2D 座標系での符号付き面積（シューレース公式）。
53    /// 外周面の判別は呼び出し側が行う（モジュールドキュメント参照）。
54    pub signed_area: f64,
55}
56
57/// 半辺（有向辺）をたどる面走査エンジン。モジュールドキュメント参照。
58///
59/// 戻り値は `(検出した閉路の一覧, 閉じなかった走査の数)`。後者は各半辺の後続が
60/// 一意に定まる不変条件の番人であり、0 でなければ呼び出し側のグラフ構築に誤りがある。
61/// 閉路の順序は開始半辺の安定順（`(NodeId, NodeId)` の辞書順）。
62pub(crate) fn scan_faces<P>(edges: &[Edge], proj: P) -> (Vec<Face>, usize)
63where
64    P: Fn(NodeId) -> Option<[f64; 2]>,
65{
66    // 半辺（有向辺）の一覧。同じ節点対に複数の部材があっても、最初の 1 本だけを採る
67    // （重複部材は面を増やさない）。
68    let mut half: HashMap<(NodeId, NodeId), ElemId> = HashMap::new();
69    for e in edges {
70        if e.a == e.b {
71            continue;
72        }
73        half.entry((e.a, e.b)).or_insert(e.elem);
74        half.entry((e.b, e.a)).or_insert(e.elem);
75    }
76
77    // 各節点まわりの接続先を方位角の昇順に並べる。
78    let mut around: HashMap<NodeId, Vec<NodeId>> = HashMap::new();
79    for &(from, to) in half.keys() {
80        around.entry(from).or_default().push(to);
81    }
82    for (from, list) in around.iter_mut() {
83        let Some(origin) = proj(*from) else {
84            continue;
85        };
86        list.sort_by(|x, y| angle_at(&proj, origin, *x).total_cmp(&angle_at(&proj, origin, *y)));
87        list.dedup();
88    }
89
90    let mut visited: HashMap<(NodeId, NodeId), bool> = HashMap::new();
91    let mut faces = Vec::new();
92    let mut unclosed = 0;
93    let mut starts: Vec<(NodeId, NodeId)> = half.keys().copied().collect();
94    // 走査順を安定させる（HashMap の反復順に依存しない）。
95    starts.sort_by_key(|(a, b)| (a.0, b.0));
96
97    for start in starts {
98        if visited.contains_key(&start) {
99            continue;
100        }
101        let mut boundary = Vec::new();
102        let mut face_edges = Vec::new();
103        let mut cur = start;
104        let mut closed = false;
105        // 閉路をたどる。半辺の総数を超えたら異常として打ち切る（無限ループ防止）。
106        for _ in 0..=half.len() {
107            if visited.insert(cur, true).is_some() {
108                break;
109            }
110            boundary.push(cur.0);
111            face_edges.push(half[&cur]);
112            let Some(next) = next_half_edge(&around, cur) else {
113                break;
114            };
115            cur = next;
116            if cur == start {
117                closed = true;
118                break;
119            }
120        }
121        if !closed {
122            // 各半辺の後続は一意なので、ここへ来るのはグラフの構築に誤りがある場合だけ。
123            unclosed += 1;
124            continue;
125        }
126        if boundary.len() < 3 {
127            continue;
128        }
129        let pts: Vec<[f64; 2]> = boundary.iter().filter_map(|&n| proj(n)).collect();
130        if pts.len() != boundary.len() {
131            continue;
132        }
133        faces.push(Face {
134            signed_area: crate::geom::polygon::signed_area(&pts),
135            boundary,
136            edges: face_edges,
137        });
138    }
139
140    (faces, unclosed)
141}
142
143/// `origin` から節点 `to` を `proj` で見た方位角（-π..π）。射影できない場合は端に寄せる。
144fn angle_at<P>(proj: &P, origin: [f64; 2], to: NodeId) -> f64
145where
146    P: Fn(NodeId) -> Option<[f64; 2]>,
147{
148    match proj(to) {
149        Some(c) => (c[1] - origin[1]).atan2(c[0] - origin[0]),
150        None => f64::MAX,
151    }
152}
153
154/// 半辺 `u→v` の次の半辺。`v` のまわりで `v→u` の 1 つ手前（時計回りに次）を選ぶと、
155/// 内部を左に見て一周する閉路になる。
156fn next_half_edge(
157    around: &HashMap<NodeId, Vec<NodeId>>,
158    (u, v): (NodeId, NodeId),
159) -> Option<(NodeId, NodeId)> {
160    let list = around.get(&v)?;
161    let pos = list.iter().position(|&w| w == u)?;
162    let prev = if pos == 0 { list.len() - 1 } else { pos - 1 };
163    Some((v, list[prev]))
164}
squid_n_core/region_gen/mod.rs

squid_n_core/region_gen/
mod.rs
