Line data Source code
1 : """
2 : Iterate local neighborhood in mesh.
3 :
4 : - `M` mesh type
5 : - `Center` iterate around vertex (`VHnd`) or face (`FHnd`)
6 : - `Element` type of returned elements (`VHnd`, `FHnd`, `HHnd`)
7 : - `ItrOrient` is one of `Val(:ccw)` or `Val(:cw)`
8 : - `EltOrient` is one of `Val(:out)` or `Val(:in)`
9 : - `Length` is one of `Val(:unknown)`, `Val(n)`, `Val(:infinite)`
10 :
11 : See also [`star`](@ref), [`ring`](@ref), [`fan`](@ref), [`vertices`](@ref),
12 : [`halfedges`](@ref)
13 : """
14 : struct LocalIter{M, Center, Element, ItrOrient, EltOrient, Length}
15 : mesh::M
16 : center::Center
17 : h::HHnd
18 :
19 49202 : function LocalIter{M, C, E, Io, Eo, L}(
20 : mesh::M, center::C, ::Type{E}) where {M, C, Io, E, Eo, L}
21 49202 : new(mesh, center, halfedge(mesh, center))
22 : end
23 : end
24 :
25 137 : Base.eltype(::LocalIter{M, C, E}) where {M, C, E} = E
26 :
27 0 : Base.HasEltype(::LocalIter) = HasEltype()
28 :
29 138 : Base.IteratorSize(
30 : ::LocalIter{M, C, E, Io, Eo, Val{:unknown}}) where {M, C, E, Io, Eo} =
31 : Base.SizeUnknown()
32 :
33 0 : Base.IteratorSize(
34 : ::LocalIter{M, C, E, Io, Eo, Val{:infinite}}) where {M, C, E, Io, Eo} =
35 : Base.IsInfinite()
36 :
37 0 : Base.IteratorSize(
38 : ::LocalIter{M, C, E, Io, Eo, Val{N}}) where {M, C, E, Io, Eo, N<:Integer} =
39 : Base.HasLength()
40 :
41 0 : Base.length(
42 : ::LocalIter{M, C, E, Io, Eo, Val{N}}) where {M, C, E, Io, Eo, N} = N
43 :
44 :
45 508 : function
46 : Base.iterate(it::LocalIter{M, FHnd, E, Io, Eo, L}) where {M, E, Io, Eo, L}
47 508 : @massert it.h != NoH
48 508 : (_iterelt(E, it, it.h), it.h) :: Tuple{E, HHnd}
49 : end
50 :
51 36496 : function
52 : Base.iterate(it::LocalIter{M, VHnd, E, Io, Eo, L}) where {M, E, Io, Eo, L}
53 36496 : (it.h == NoH) && return nothing
54 36496 : (_iterelt(E, it, it.h), it.h) :: Tuple{E, HHnd}
55 : end
56 :
57 : # TODO: For eo == in -> change initialization (not implemented)
58 :
59 219973 : _iterelt(::Type{HHnd}, _it, h::HHnd) = h
60 :
61 526 : _iterelt(::Type{VHnd}, it::LocalIter{M}, h::HHnd) where {M} =
62 : destination(it.mesh, h) :: VHnd
63 :
64 0 : _iterelt(::Type{FHnd}, it::LocalIter{M}, h::HHnd) where {M} =
65 : face(it.mesh, h) :: FHnd
66 :
67 0 : _iterstop(_) = true
68 :
69 0 : _iterstop(::Val{:infinite}) = false
70 : # TODO: Check length / condition for Val{N}?
71 :
72 1678 : _iternext(::Type{FHnd}, orientation, mesh::Mesh, h::HHnd) =
73 : next(mesh, orientation, h)
74 :
75 291443 : _iternext(::Type{VHnd}, orientation, mesh::Mesh, h::HHnd) =
76 : nextinstar(mesh, orientation, h)
77 :
78 220435 : function Base.iterate(it::LocalIter{M, C, E, Io, Eo, L},
79 : h::HHnd) where {M, C, E, Io, Eo, L}
80 220435 : @massert h != NoH
81 220435 : hn = _iternext(C, Io(), it.mesh, h)
82 220435 : _iterstop(L()) && (hn == it.h) && return nothing
83 183495 : (_iterelt(E, it, hn), hn) :: Tuple{E, HHnd}
84 : end
85 :
86 : #-----------------------------------------------------------------------------
87 : # iterate around vertex
88 : #-----------------------------------------------------------------------------
89 :
90 : """
91 : for hn in cwstar(mesh, h::VHnd)
92 : ...
93 : end
94 :
95 : Iterate outgoing edges `h::hHnd` in 1-ring of `v` in clockwise order.
96 :
97 : See also [`star`](@ref), [`ccwstar`](@ref).
98 : """
99 36490 : cwstar(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} =
100 : LocalIter{Mesh{V, F, H, E}, VHnd, HHnd,
101 : Val{:cw}, Val{:out}, Val{:unknown}}(mesh, v, HHnd)
102 :
103 : """
104 : Synonym for [`cwstar`](@ref).
105 : """
106 36490 : star(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} = cwstar(mesh, v)
107 :
108 : """
109 : for h in ccwstar(mesh, v::VHnd)
110 : ...
111 : end
112 :
113 : Iterate outgoing edges `h::HHnd` in 1-ring of `v` in counter-clockwise
114 : order.
115 :
116 : See also [`star`](@ref), [`cwstar`](@ref).
117 : """
118 0 : ccwstar(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} =
119 : LocalIter{Mesh{V, F, H, E}, VHnd, HHnd,
120 : Val{:ccw}, Val{:out}, Val{:unknown}}(mesh, v, HHnd)
121 :
122 :
123 : #-----------------------------------------------------------------------------
124 :
125 : """
126 : for vn in cwring(mesh, v::VHnd)
127 : ...
128 : end
129 :
130 : Iterate vertex neighbors `vn::VHnd` in 1-ring of `v` in clockwise order.
131 :
132 : See also [`ring`](@ref), [`ccwring`](@ref).
133 : """
134 10 : cwring(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} =
135 : LocalIter{Mesh{V, F, H, E}, VHnd, VHnd,
136 : Val{:cw}, Val{:out}, Val{:unknown}}(mesh, v, VHnd)
137 :
138 : """
139 : Synonym for [`cwring`](@ref).
140 : """
141 10 : ring(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} = cwring(mesh, v)
142 :
143 : """
144 : for vn in ccwring(mesh, v::VHnd)
145 : ...
146 : end
147 :
148 : Iterator vertex neighbors `vn::VHnd` in 1-ring of `v` in
149 : counter-clockwise order.
150 :
151 : See also [`ring`](@ref), [`cwring`](@ref).
152 : """
153 0 : ccwring(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} =
154 : LocalIter{Mesh{V, F, H, E}, VHnd, VHnd,
155 : Val{:ccw}, Val{:out}, Val{:unknown}}(mesh, v, VHnd)
156 :
157 : #-----------------------------------------------------------------------------
158 :
159 : # Fix for fan: There may be (multiple!) boundary half-edges w/o face. In this
160 : # case advance to the next half-edge.
161 :
162 : # TODO: Check fan for nonmanifold vertex! Check remove(mesh, VHnd) !!!
163 :
164 12188 : function Base.iterate(it::LocalIter{M, VHnd, FHnd, Io,
165 : Val{:out}, Val{:unknown}}) where {M, Io}
166 12188 : (it.h == NoH) && return nothing
167 :
168 12177 : h = it.h
169 12177 : f = face(it.mesh, h)
170 :
171 12177 : if f == NoF
172 61 : h = _iternext(VHnd, Io(), it.mesh, h)
173 61 : f = face(it.mesh, h)
174 61 : @massert f != NoF
175 : end
176 :
177 12177 : (f, h) :: Tuple{FHnd, HHnd}
178 : end
179 :
180 72624 : function Base.iterate(it::LocalIter{M, VHnd, FHnd, Io,
181 : Val{:out}, Val{:unknown}},
182 : h::HHnd) where {M, Io}
183 72624 : @massert h != NoH
184 :
185 72624 : hn = _iternext(VHnd, Io(), it.mesh, h)
186 72624 : (hn == it.h) && return nothing
187 :
188 60509 : f = face(it.mesh, hn)
189 :
190 60509 : if f == NoF
191 1 : hn = _iternext(VHnd, Io(), it.mesh, hn)
192 1 : (hn == it.h) && return nothing
193 1 : f = face(it.mesh, hn)
194 1 : @massert f != NoF
195 : end
196 :
197 60509 : (f, hn) :: Tuple{FHnd, HHnd}
198 : end
199 :
200 : """
201 : for f in cwfan(mesh, v::VHnd)
202 :
203 : Iterate faces`f::FHnd` incident to vertex `v` in
204 : clockwise order.
205 :
206 : See also [`fan`](@ref), [`ccwfan`](@ref).
207 : """
208 12190 : cwfan(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} =
209 : LocalIter{Mesh{V, F, H, E}, VHnd, FHnd,
210 : Val{:cw}, Val{:out}, Val{:unknown}}(mesh, v, FHnd)
211 :
212 : """
213 : Synonym for [`cwfan`](@ref).
214 : """
215 12190 : fan(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} = cwfan(mesh, v)
216 :
217 : """
218 : for f in cwfan(mesh, v::VHnd)
219 : ...
220 : end
221 :
222 : Iterate faces`f::FHnd` incident to vertex `v` in counter-clockwise
223 : order.
224 :
225 : See also [`fan`](@ref), [`cwfan`](@ref).
226 : """
227 0 : ccwfan(mesh::Mesh{V, F, H, E}, v::VHnd) where {V, F, H, E} =
228 : LocalIter{Mesh{V, F, H, E}, VHnd, FHnd,
229 : Val{:ccw}, Val{:out}, Val{:unknown}}(mesh, v, FHnd)
230 :
231 : #-----------------------------------------------------------------------------
232 : # iterate in face
233 : #-----------------------------------------------------------------------------
234 :
235 : """
236 : for v in ccwvertices(mesh, f::FHnd)
237 : ...
238 : end
239 :
240 : Iterate vertices spanning face `f` in counter-clockwise order.
241 :
242 : See also [`cwvertices`](@ref)
243 : """
244 166 : ccwvertices(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E} =
245 : LocalIter{Mesh{V, F, H, E}, FHnd, VHnd,
246 : Val{:ccw}, Val{:out}, Val{:unknown}}(mesh, f, VHnd)
247 :
248 : """
249 : for v in vertices(mesh, f::FHnd)
250 : ...
251 : end
252 :
253 : Synonym for [`ccwvertices`](@ref)
254 : """
255 166 : vertices(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E} =
256 : ccwvertices(mesh, f)
257 :
258 : """
259 : for v in vertices(mesh, f::FHnd)
260 : ...
261 : end
262 :
263 : Iterate vertices spanning face `f` in clockwise order.
264 :
265 : See also [`cwvertices`](@ref)
266 : """
267 0 : cwvertices(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E} =
268 : LocalIter{Mesh{V, F, H, E}, FHnd, VHnd,
269 : Val{:cw}, Val{:out}, Val{:unknown}}(mesh, f, VHnd)
270 :
271 : #-----------------------------------------------------------------------------
272 :
273 : """
274 : for h in ccwhalfedges(mesh, f::FHnd)
275 : ...
276 : end
277 :
278 : Iterate half-edges spanning face `f` in counter-clockwise order.
279 :
280 : See also [`cwhalfedges`](@ref)
281 : """
282 346 : ccwhalfedges(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E} =
283 : LocalIter{Mesh{V, F, H, E}, FHnd, HHnd,
284 : Val{:ccw}, Val{:out}, Val{:unknown}}(mesh, f, HHnd)
285 :
286 : """
287 : for h in halfedges(mesh, f::FHnd)
288 : ...
289 : end
290 :
291 : Synonym for [`ccwhalfedges`](@ref)
292 : """
293 346 : halfedges(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E} =
294 : ccwhalfedges(mesh, f)
295 :
296 : """
297 : for h in halfedges(mesh, f::FHnd)
298 : ...
299 : end
300 :
301 : Iterate half-edges spanning face `f` in clockwise order.
302 :
303 : See also [`ccwhalfedges`](@ref)
304 : """
305 0 : cwhalfedges(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E} =
306 : LocalIter{Mesh{V, F, H, E}, FHnd, HHnd,
307 : Val{:cw}, Val{:out}, Val{:unknown}}(mesh, f, HHnd)
308 :
309 : #-----------------------------------------------------------------------------
310 :
311 : # TODO: cwv(mesh, center), ccwv, cwh, ccwh, cwf, ccwf
312 :
313 :
314 : # circulate around vertex or face using infinite range
315 :
316 0 : function circulate(mesh::Mesh{V, F, H, E}, v::VHnd,
317 : elt::Type{Hnd{T}} = HHnd,
318 : orientation = Val(:cw)) where {V, F, H, E, T}
319 0 : LocalIter{Mesh{V, F, H, E}, VHnd, HHnd,
320 : typeof(orientation), Val{:out}, Val{:infinite}}(mesh, v, elt)
321 : end
322 :
323 0 : function circulate(mesh::Mesh{V, F, H, E}, f::FHnd,
324 : elt::Type{Hnd{T}} = HHnd,
325 : orientation = Val(:ccw)) where {V, F, H, E, T}
326 0 : LocalIter{Mesh{V, F, H, E}, FHnd, HHnd,
327 : typeof(orientation), Val{:out}, Val{:infinite}}(mesh, f, elt)
328 : end
329 :
330 : """
331 : for h in circulate(mesh, v::VHnd[, elt=HHnd])
332 : ...
333 : end
334 :
335 : for h in circulate(mesh, f::FHnd[, elt=HHnd])
336 : ...
337 : end
338 :
339 : Iterate around vertex `v` or face `f` forever (i.e, user needs to
340 : explicitly `break` out of the loop). The iteration yields `elt`, which
341 : can be outgoing half-edges (`HHnd`), neighboring vertices (`VHnd`) or
342 : incident faces (`FHnd`).
343 : """ circulate
344 :
345 : # iterate face with fixed degree
346 :
347 : """
348 : for i in ccwvertices(Val(N), mesh, f::FHnd)
349 :
350 : Generate `N` vertices spanning face `f`. The face `f` **must** have
351 : degree `N` or the iteration is undefined!
352 :
353 : !!! warning
354 : This method is significantly slower than the special cases like
355 : [`triangle`](@ref). -- *It may be removed in a future version!*
356 : """
357 0 : ccwvertices(_degree::Val{N},
358 : mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E, N} =
359 : LocalIter{Mesh{V, F, H, E}, FHnd, VHnd,
360 : Val{:ccw}, Val{:out}, Val{N}}(mesh, f, VHnd)
361 :
362 : # NOTE: This is probably not worth the effort. Constructing a tuple
363 : # from ccwvertices(...) is fairly expensive. Costs for a Vector
364 : # are similar! Calls to triangle(...) or quad(...) with
365 : # unrolled loops are significantly more efficient!
366 :
367 : """
368 : v1, v1, v2 = triangle(mesh, f::FHnd)
369 :
370 : Get vertices (`VHnd`) spanning triangle `f` as an `NTuple{3, VHnd}` or
371 : `(NoV, NoV, NoV)` if face is not a triangle.
372 :
373 : See also [`quad`](@ref), [`vertices`](@ref)
374 : """
375 49027 : function triangle(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E}
376 49027 : h0 = halfedge(mesh, f)
377 :
378 49027 : h = h0
379 49027 : a = destination(mesh, h) :: VHnd
380 49027 : h = next(mesh, h)
381 49027 : b = destination(mesh, h) :: VHnd
382 49027 : h = next(mesh, h)
383 49027 : c = destination(mesh, h) :: VHnd
384 :
385 49027 : (next(mesh, h) != h0) && return (NoV, NoV, NoV)
386 :
387 49027 : a, b, c
388 : end
389 :
390 :
391 : """
392 : v1, v1, v2, hnext = first3(mesh, f::FHnd)
393 :
394 : Get the first 3 vertices (`VHnd`) of face `f` and the handle of the
395 : "next edge" such that
396 :
397 : - `hnext == NoH` **if** `f` is a triangle
398 : - `destination(hnext)` provides the next vertex in `f` **else**
399 :
400 : See also [`triangle`](@ref), [`quad`](@ref)
401 : """
402 161652 : function first3(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E}
403 161652 : h0 = halfedge(mesh, f)
404 :
405 161652 : h = h0
406 161652 : a = destination(mesh, h) :: VHnd
407 161652 : h = next(mesh, h)
408 161652 : b = destination(mesh, h) :: VHnd
409 161652 : h = next(mesh, h)
410 161652 : c = destination(mesh, h) :: VHnd
411 :
412 161652 : hnext = next(mesh, h)
413 161652 : (hnext == h0) && (hnext = NoH)
414 :
415 161652 : a, b, c, hnext
416 : end
417 :
418 424 : istriangle(mesh::Mesh, f::FHnd) = istriangle(mesh, halfedge(mesh, f))
419 :
420 442 : function istriangle(mesh::Mesh, h::HHnd)
421 442 : @massert isused(mesh, h)
422 442 : @massert face(mesh, h) != NoH
423 :
424 442 : next(mesh, next(mesh, h)) == prev(mesh, h)
425 : end
426 :
427 : """
428 : istriangle(mesh, f::FHnd)
429 : istriangle(mesh, h::HHnd)
430 :
431 : Determine whether `f` or `face(h)` is a triangle.
432 :
433 : !!! warning "Precondition"
434 : Requires `isused(mesh, f)`: `f` must be a face.
435 : """ istriangle
436 :
437 : """
438 : v1, v2, v3, v4 = quad(mesh, f::FHnd)
439 :
440 : Get vertices (`VHnd`) spanning quad `f` as an `NTuple{4, VHnd}` or
441 : `(NoV, NoV, NoV, NoV)` if face is not a quad.
442 :
443 : See also [`triangle`](@ref), [`vertices`](@ref)
444 : """
445 2 : function quad(mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E}
446 2 : h0 = halfedge(mesh, f)
447 :
448 2 : h = h0
449 2 : a = destination(mesh, h) :: VHnd
450 2 : h = next(mesh, h)
451 2 : b = destination(mesh, h) :: VHnd
452 2 : h = next(mesh, h)
453 2 : c = destination(mesh, h) :: VHnd
454 2 : h = next(mesh, h)
455 2 : d = destination(mesh, h) :: VHnd
456 :
457 2 : (next(mesh, h) != h0) && return (NoV, NoV, NoV, NoV)
458 :
459 0 : a, b, c, d
460 : end
461 :
462 207 : isquad(mesh::Mesh, f::FHnd) = isquad(mesh, halfedge(mesh, f))
463 :
464 207 : function isquad(mesh::Mesh, h::HHnd)
465 207 : @massert isused(mesh, h)
466 207 : @massert face(mesh, h) != NoH
467 :
468 207 : next(mesh, next(mesh, next(mesh, h))) == prev(mesh, h)
469 : end
470 :
471 : """
472 : isquad(mesh, f::FHnd)
473 : isquad(mesh, h::HHnd)
474 :
475 : Determine whether `f` or `face(h)` is a quad.
476 :
477 : !!! warning "Precondition"
478 : Requires `isused(mesh, f)`: `f` must be a face.
479 : """ isquad
480 :
481 : # NOTE: collect(vertices(...)) is not significantly slower?!
482 :
483 : """
484 : vs = VHnd[]
485 : vertices!(vs, mesh, f)
486 :
487 : Update `vs::Vector` in-place to store vertices spanning face `f`.
488 :
489 : !!! warning
490 : This method seems not to be significantly faster than
491 : `collect(vertices(mesh, f)`. -- *It may be removed in a future
492 : version!*
493 :
494 : """
495 0 : function vertices!(v::Vector{VHnd},
496 : mesh::Mesh{V, F, H, E}, f::FHnd) where {V, F, H, E}
497 0 : empty!(v)
498 0 : for vi in vertices(mesh, f)
499 0 : push!(v, vi)
500 0 : end
501 0 : v
502 : end
503 :
504 : # TODO: remove option HasLength ... Val{N} ???
505 :
506 : # DONE: center=VHnd cwh=cwstar=star, cwv=cwring,ring, cwf=cwfan=fan, ...
507 : # DONE: center=FHnd cwh=edges, cwv=vertices
508 : # DONE: cwcirculate (infinite)
509 : # TODO: vertices(Val(n),...), edges(Val(n), vertices3, vertices4, edges3, edges4
|
