1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
//! Removal edits on a [`SpacePlate`]: spur and edge deletion plus the orphan
//! sweep that cleans up after them. Split out of `mod.rs` for the module-size
//! ratchet; the construction, split/merge/dissolve edits and queries stay there.
use super::walk::FaceWalk;
use super::{EditError, Face, FaceId, FacePatch, HalfEdgeId, SpacePlate, VertexId, EPS_COLL};
use super::geom2d::perp_distance;
impl SpacePlate {
/// Live degree of a vertex (its number of live outgoing half-edges).
pub(super) fn vertex_degree(&self, v: VertexId) -> usize {
let vi = v.0 as usize;
if vi >= self.vertices.len() || !self.vertices[vi].alive {
return 0;
}
self.outgoing_half_edges(v).count()
}
/// Remove the undirected edge of a **degree-1 spur tip** — a dangling wall
/// poking into a face — splicing the face cycle closed and tombstoning the
/// tip. `spur_he` may be either half-edge of the spur. Internal; driven by
/// `prune_orphans` / `remove_edge`. Area-neutral: the tip's out-and-back
/// boundary contributes cancelling shoelace terms, so no face area changes.
pub(super) fn remove_spur_edge(&mut self, spur_he: HalfEdgeId) -> Result<(), EditError> {
let hi = spur_he.0 as usize;
if hi >= self.half_edges.len() || !self.half_edges[hi].alive {
return Err(EditError::StaleHandle);
}
let t = self.half_edges[hi].twin;
// Orient so `s = T→J` (origin is the degree-1 tip) and `s_t = J→T`.
let (s, s_t) = if self.vertex_degree(self.half_edges[hi].origin) == 1 {
(spur_he, t)
} else if self.vertex_degree(self.half_edges[t.0 as usize].origin) == 1 {
(t, spur_he)
} else {
return Err(EditError::VertexNotDissolvable); // neither end is a tip
};
let tip = self.half_edges[s.0 as usize].origin;
let j = self.half_edges[s_t.0 as usize].origin;
let f = self.half_edges[s.0 as usize].face;
// A genuine tip is a peninsula: both half-edges share one face and the
// rotation at the tip is the out-and-back pattern. Else it's corrupt.
if self.half_edges[s_t.0 as usize].face != f
|| self.half_edges[s_t.0 as usize].next != s
|| self.half_edges[s.0 as usize].prev != s_t
{
return Err(EditError::StaleHandle);
}
let a = self.half_edges[s_t.0 as usize].prev; // ends at J
let b = self.half_edges[s.0 as usize].next; // starts at J
if a == s {
// Lone stick: J is degree-1 too, so this 2-cycle bounds nothing.
// Tombstone it whatever face it is tagged with (refusing left
// `prune_orphans` a tip it could never remove) and let the face
// re-anchor on whatever else it still bounds, or die with it.
self.half_edges[s.0 as usize].alive = false;
self.half_edges[s_t.0 as usize].alive = false;
self.vertices[tip.0 as usize].outgoing = None;
self.vertices[tip.0 as usize].alive = false;
self.vertices[j.0 as usize].outgoing = None;
self.vertices[j.0 as usize].alive = false;
self.reanchor_face_if_dead(f);
return Ok(());
}
// Splice the spur out of F's cycle: A → B directly.
self.half_edges[a.0 as usize].next = b;
self.half_edges[b.0 as usize].prev = a;
self.half_edges[s.0 as usize].alive = false;
self.half_edges[s_t.0 as usize].alive = false;
self.vertices[tip.0 as usize].outgoing = None;
self.vertices[tip.0 as usize].alive = false;
self.repair_vertex_outgoing(j, s_t);
if matches!(self.faces[f.0 as usize].half_edge, Some(h) if h == s || h == s_t) {
self.faces[f.0 as usize].half_edge = Some(a);
}
Ok(())
}
/// Remove all orphaned cruft the wall arrangement leaves behind: dangling
/// spur walls (degree-1 chains), isolated vertices, and redundant collinear
/// degree-2 nodes. Idempotent, and never changes a room's area (spurs bound
/// no room; collinear dissolve only straightens a node already on its chord).
/// Returns how many topology elements were pruned.
pub fn prune_orphans(&mut self) -> usize {
let mut removed = 0usize;
// Phase A — spur sweep to a fixpoint (chews whole chains). A tip that
// `remove_spur_edge` refuses stays degree-1, so "no tips left" alone is
// not an exit: a sweep that removes nothing must break, as Phase C does.
loop {
let mut progress = false;
let tips: Vec<VertexId> = (0..self.vertices.len())
.map(|i| VertexId(i as u32))
.filter(|&v| self.vertex_degree(v) == 1)
.collect();
for tip in tips {
if self.vertex_degree(tip) != 1 {
continue; // a sibling removal already changed it
}
let s = self.outgoing_half_edges(tip).next();
if let Some(s) = s {
if self.remove_spur_edge(s).is_ok() {
removed += 1;
progress = true;
}
}
}
if !progress {
break;
}
}
// Phase B — drop leftover degree-0 (isolated) vertices.
for i in 0..self.vertices.len() {
let v = VertexId(i as u32);
if self.vertices[i].alive && self.vertex_degree(v) == 0 {
self.vertices[i].alive = false;
self.vertices[i].outgoing = None;
removed += 1;
}
}
// Phase C — dissolve redundant collinear degree-2 nodes (fixpoint).
loop {
let mut progress = false;
let cands: Vec<VertexId> = (0..self.vertices.len())
.map(|i| VertexId(i as u32))
.filter(|&v| self.vertex_degree(v) == 2)
.collect();
for v in cands {
if self.vertex_degree(v) != 2 {
continue;
}
let outs: Vec<HalfEdgeId> = self.outgoing_half_edges(v).collect();
let p = self.vertices[v.0 as usize].pos;
let x = self.vertices[self.dest(outs[0]).0 as usize].pos;
let y = self.vertices[self.dest(outs[1]).0 as usize].pos;
if perp_distance(p, x, y) >= EPS_COLL {
continue; // a genuine corner — keep it
}
if self.dissolve_vertex(v).is_ok() {
removed += 1;
progress = true;
}
}
if !progress {
break;
}
}
removed
}
/// Remove the wall `edge`, choosing the right semantics from its two
/// incident faces, and auto-clean the orphans it leaves:
/// - room ↔ room → union the two rooms (`merge_faces`);
/// - bridge (same face both sides) → delete it, give the cycle it cut off
/// its own face (`split_bridge_cycles`), then `prune_orphans`;
/// - outer ↔ outer → delete it + `prune_orphans`;
/// - room ↔ outer (a real enclosing wall) → `BordersExterior` (don't open a room).
pub fn remove_edge(&mut self, edge: HalfEdgeId) -> Result<Vec<FacePatch>, EditError> {
let hi = edge.0 as usize;
if hi >= self.half_edges.len() || !self.half_edges[hi].alive {
return Err(EditError::StaleHandle);
}
let t = self.half_edges[hi].twin;
let f_keep = self.half_edges[hi].face;
let f_drop = self.half_edges[t.0 as usize].face;
let keep_outer = self.faces[f_keep.0 as usize].is_outer;
let drop_outer = self.faces[f_drop.0 as usize].is_outer;
if f_keep != f_drop && !keep_outer && !drop_outer {
return self.merge_faces(edge); // two real rooms → union
}
if f_keep != f_drop && keep_outer != drop_outer {
return Err(EditError::BordersExterior); // would open a room
}
// Bridge (f_keep == f_drop) or outer ↔ outer → delete + clean.
let hn = self.half_edges[hi].next;
let hp = self.half_edges[hi].prev;
let tn = self.half_edges[t.0 as usize].next;
let tp = self.half_edges[t.0 as usize].prev;
let oh = self.half_edges[hi].origin;
let ot = self.half_edges[t.0 as usize].origin;
self.half_edges[hp.0 as usize].next = tn;
self.half_edges[tn.0 as usize].prev = hp;
self.half_edges[tp.0 as usize].next = hn;
self.half_edges[hn.0 as usize].prev = tp;
if f_drop != f_keep {
// outer ↔ outer: fold f_drop's loop into f_keep.
self.faces[f_keep.0 as usize].half_edge = Some(hp);
let merged: Vec<HalfEdgeId> = self.face_half_edges(f_keep).collect();
for he in merged {
self.half_edges[he.0 as usize].face = f_keep;
}
self.faces[f_drop.0 as usize].alive = false;
self.faces[f_drop.0 as usize].half_edge = None;
}
self.half_edges[hi].alive = false;
self.half_edges[t.0 as usize].alive = false;
self.repair_vertex_outgoing(oh, edge);
self.repair_vertex_outgoing(ot, t);
// The face's anchor may have been one of the removed half-edges (esp. a
// bridge / spur in the outer face) — re-point it at a survivor.
self.reanchor_face_if_dead(f_keep);
if f_drop == f_keep {
self.split_bridge_cycles(f_keep, hn, tn);
}
self.prune_orphans();
let mut out = Vec::new();
if self.faces[f_keep.0 as usize].alive && !self.faces[f_keep.0 as usize].is_outer {
out.push(self.face_patch(f_keep));
}
Ok(out)
}
/// After a bridge splice in `remove_edge`, the face's one cycle
/// `h, hn, …, tp, t, tn, …, hp` has become two: `hn…tp` and `tn…hp`, both
/// still tagged `f`. A `Face` anchors one cycle, so the walk from `f`'s
/// anchor reached only one of them and the other was a fragment nothing
/// could reach or re-home. Give the second cycle its own face, classified
/// by signed area exactly as `from_arrangement` does (a cut-off stick or
/// island winds CW or flat → outer); `f` stays on the larger-area cycle so
/// a room keeps its id when something is cut off it. A spur tip needs
/// nothing: its "second cycle" is the dead pair itself.
fn split_bridge_cycles(&mut self, f: FaceId, hn: HalfEdgeId, tn: HalfEdgeId) {
if !self.half_edges[hn.0 as usize].alive || !self.half_edges[tn.0 as usize].alive {
return;
}
let walk = |start: HalfEdgeId| FaceWalk { plate: self, start: Some(start), cur: None };
let cycle_h: Vec<HalfEdgeId> = walk(hn).collect();
if cycle_h.contains(&tn) {
return; // still one cycle
}
let cycle_t: Vec<HalfEdgeId> = walk(tn).collect();
let (area_h, area_t) = (self.signed_area_of_cycle(&cycle_h), self.signed_area_of_cycle(&cycle_t));
let (keep, split, split_area) =
if area_h >= area_t { (cycle_h, cycle_t, area_t) } else { (cycle_t, cycle_h, area_h) };
let parent = self.faces[f.0 as usize].clone();
let is_outer = split_area <= 0.0;
let new_face = FaceId(self.faces.len() as u32);
self.faces.push(Face {
half_edge: split.first().copied(),
is_outer,
is_room: !is_outer && parent.is_room,
alive: true,
..parent
});
for he in split {
self.half_edges[he.0 as usize].face = new_face;
}
self.faces[f.0 as usize].half_edge = keep.first().copied();
}
}