1use crate::prelude::*;
3use crate::proj::{self, BaseTriProjector};
4use crate::tri::{self, BaseRegion, BaseRegionType, TriSphere};
5use std::num::NonZero;
6
7#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
14pub struct HexSphere<Proj = proj::Default> {
15 kis: TriSphere<Proj>,
16}
17
18impl<Proj: Clone + BaseTriProjector> TriSphere<Proj> {
19 pub fn truncate(self) -> HexSphere<Proj> {
24 HexSphere {
25 kis: self.subdivide_edge(NonZero::new(3).unwrap()),
26 }
27 }
28}
29
30impl<Proj> HexSphere<Proj> {
31 pub fn from_kis(kis: TriSphere<Proj>) -> Option<Self> {
37 if (kis.b() + 2 * kis.c()) % 3 == 0 {
38 Some(Self { kis })
39 } else {
40 None
41 }
42 }
43
44 pub fn kis(self) -> TriSphere<Proj> {
50 self.kis
51 }
52
53 pub fn with_projector<NProj>(self, proj: NProj) -> HexSphere<NProj> {
58 HexSphere {
59 kis: self.kis.with_projector(proj),
60 }
61 }
62
63 const fn dual_num_divisions(&self) -> usize {
65 let b = self.kis.b() as usize;
66 let c = self.kis.c() as usize;
67 let dual_c = (b - c) / 3;
68 let dual_b = c + dual_c;
69 dual_b * (dual_b + dual_c) + dual_c * dual_c
70 }
71
72 fn num_faces_per_edge_region(&self) -> usize {
74 let b = self.kis.b() as usize;
75 let c = self.kis.c() as usize;
76 num_faces_on_edge(b, c + 1)
77 }
78
79 fn num_faces_per_interior_region(&self) -> usize {
81 let b = self.kis.b() as usize;
82 let c = self.kis.c() as usize;
83 let n = b - c;
84 if n == 0 {
85 (c % 3 == 0) as usize
86 } else {
87 num_faces_on_interior(c, n, n)
88 }
89 }
90
91 fn num_vertices_per_edge_region(&self) -> usize {
94 self.kis.num_vertices_per_edge_region() - self.num_faces_per_edge_region()
95 }
96
97 fn num_vertices_per_interior_region(&self) -> usize {
99 self.kis.num_vertices_per_interior_region() - self.num_faces_per_interior_region()
100 }
101}
102
103fn num_faces_on_edge(b: usize, d: usize) -> usize {
105 ((b - 1) * d + (b % 3) / 2) / 3
106}
107
108#[test]
109fn test_num_faces_on_edge() {
110 for b in 1..10 {
111 for d in 0..10 {
112 let mut count = 0;
113 for u in 1..b {
114 for v in 0..d {
115 if u % 3 == v % 3 {
116 count += 1;
117 }
118 }
119 }
120 assert_eq!(
121 num_faces_on_edge(b, d),
122 count,
123 "failed for b = {}, d = {}",
124 b,
125 d
126 );
127 }
128 }
129}
130
131fn num_faces_on_interior(k: usize, n: usize, d: usize) -> usize {
134 (d - 1) * (2 * n - d - 2) / 6 + ((k % 3 == 0) & (d % 3 != 1)) as usize
135}
136
137#[test]
138fn test_num_faces_on_interior() {
139 for k in 0..2 {
140 for n_3 in 1..10 {
141 let n = n_3 * 3;
142 for d in 1..n {
143 let mut count = 0;
144 for u in 1..n {
145 for v in 1..d {
146 if u + v < n && u % 3 == (v + k) % 3 {
147 count += 1;
148 }
149 }
150 }
151 assert_eq!(
152 num_faces_on_interior(k, n, d),
153 count,
154 "failed for k = {}, n = {}, d = {}",
155 k,
156 n,
157 d
158 );
159 }
160 }
161 }
162}
163
164impl<Proj: Eq + Clone + BaseTriProjector> crate::Sphere for HexSphere<Proj> {
165 type Face = Face<Proj>;
166 type Vertex = Vertex<Proj>;
167 type HalfEdge = HalfEdge<Proj>;
168
169 fn num_faces(&self) -> usize {
170 self.num_vertices() / 2 + 2
171 }
172
173 fn face(&self, index: usize) -> Face<Proj> {
174 self.faces().nth(index).expect("face index out of bounds")
176 }
177
178 fn faces(&self) -> impl Iterator<Item = Face<Proj>> {
179 FaceIter {
180 sphere: self.clone(),
181 region: self.kis.base().first_region(),
182 u: 0,
183 u_end: self.kis.b(),
184 v: 0,
185 }
186 }
187
188 fn face_at(&self, point: [f64; 3]) -> Face<Proj> {
189 Face::from_kis_unchecked(self.kis.face_at(point))
190 }
191
192 fn num_vertices(&self) -> usize {
193 self.dual_num_divisions() * self.kis.base().num_faces()
194 }
195
196 fn vertex(&self, _index: usize) -> Vertex<Proj> {
197 todo!()
198 }
199
200 fn vertices(&self) -> impl Iterator<Item = Vertex<Proj>> {
201 VertexIter {
202 sphere: self.clone(),
203 region: self.kis.base().first_region(),
204 u: 1,
205 u_end: self.kis.b(),
206 v: 0,
207 skip: false,
208 }
209 }
210}
211
212#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
214pub struct Face<Proj> {
215 center: tri::Vertex<Proj>,
216}
217
218impl<Proj: Eq + Clone + BaseTriProjector> Face<Proj> {
219 pub fn from_center(center: tri::Vertex<Proj>) -> Option<Self> {
234 if center.sphere.b() % 3 != center.sphere.c() % 3 {
235 return None;
236 }
237 if center.u % 3 != center.adjusted_v() % 3 {
238 return None;
239 }
240 Some(Self { center })
241 }
242
243 pub fn from_kis(kis: tri::Face<Proj>) -> Option<Self> {
258 if kis.sphere.b() % 3 != kis.sphere.c() % 3 {
259 return None;
260 }
261
262 Some(Self::from_kis_unchecked(kis))
263 }
264
265 fn from_center_unchecked(center: tri::Vertex<Proj>) -> Self {
267 debug_assert_eq!(
268 center.sphere.b() % 3,
269 center.sphere.c() % 3,
270 "Sphere b and c parameters must be congruent mod 3."
271 );
272 debug_assert_eq!(
273 center.u % 3,
274 center.adjusted_v() % 3,
275 "Vertex u and adjusted v must be congruent mod 3."
276 );
277 Self { center }
278 }
279
280 fn from_kis_unchecked(kis: tri::Face<Proj>) -> Self {
282 debug_assert_eq!(
283 kis.sphere.b() % 3,
284 kis.sphere.c() % 3,
285 "Kis b and c parameters must be congruent mod 3."
286 );
287
288 let adj_v = if !kis.region.ty().is_edge() {
289 kis.sphere.c()
290 } else {
291 0
292 };
293
294 let [u, v] = match ((kis.u_0 + 2 * (kis.v_0 + adj_v)) % 3, kis.boundary_along_v) {
295 (0, _) => [kis.u_0, kis.v_0],
296 (1, _) => [kis.u_0, kis.v_0 + 1],
297 (_, false) => [kis.u_0 + 1, kis.v_0],
298 (_, true) => [kis.u_0 - 1, kis.v_0 + 1],
299 };
300
301 Self::from_center_unchecked(tri::Vertex::new(kis.sphere, kis.region, u, v))
302 }
303
304 pub fn sphere(&self) -> HexSphere<Proj> {
306 HexSphere {
307 kis: self.center.sphere.clone(),
308 }
309 }
310
311 pub fn center(self) -> tri::Vertex<Proj> {
313 self.center
314 }
315
316 pub fn is_hex(&self) -> bool {
318 self.center.as_base().is_none()
319 }
320}
321
322impl<Proj: Eq + Clone + BaseTriProjector> crate::Face for Face<Proj> {
323 type Vertex = Vertex<Proj>;
324 type HalfEdge = HalfEdge<Proj>;
325
326 fn index(&self) -> usize {
327 let b = self.center.sphere.b() as usize;
328 let c = self.center.sphere.c() as usize;
329 if self.center.region.ty().is_edge() {
330 self.sphere().base_face_index(self.center.region)
331 + num_faces_on_edge(b, self.center.v as usize)
332 + (self.center.u as usize).div_ceil(3)
333 } else if c < b {
334 self.sphere().base_face_index(self.center.region)
335 + num_faces_on_interior(c, b - c, self.center.v as usize)
336 + (self.center.u as usize).div_ceil(3)
337 } else {
338 self.sphere().base_face_index(self.center.region) + 1
339 }
340 }
341
342 fn area(&self) -> f64 {
343 crate::util::poly_area(self.vertices().map(|v| v.pos()))
344 }
345
346 fn num_sides(&self) -> usize {
347 if let Some(base) = self.center.as_base() {
348 base.degree()
349 } else {
350 6
351 }
352 }
353
354 fn side(&self, index: usize) -> HalfEdge<Proj> {
355 HalfEdge {
356 kis: self.center.outgoing(index).next(),
357 }
358 }
359}
360
361#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
363pub struct Vertex<Proj> {
364 kis: tri::Vertex<Proj>,
365}
366
367impl<Proj> Vertex<Proj> {
368 fn new(kis: tri::Vertex<Proj>) -> Self {
370 debug_assert_ne!(kis.u % 3, kis.adjusted_v() % 3);
371 Self { kis }
372 }
373}
374
375impl<Proj> tri::Vertex<Proj> {
376 fn adjusted_v(&self) -> u32 {
382 let mut v = self.v;
383 if !self.region.ty().is_edge() {
384 v += self.sphere.c();
385 }
386 v
387 }
388}
389
390impl<Proj: Clone> Vertex<Proj> {
391 pub fn sphere(&self) -> HexSphere<Proj> {
393 HexSphere {
394 kis: self.kis.sphere.clone(),
395 }
396 }
397
398 pub fn kis(self) -> tri::Vertex<Proj> {
400 self.kis
401 }
402}
403
404impl<Proj: Eq + Clone + BaseTriProjector> crate::Vertex for Vertex<Proj> {
405 type Face = Face<Proj>;
406 type HalfEdge = HalfEdge<Proj>;
407
408 fn index(&self) -> usize {
409 let b = self.kis.sphere.b() as usize;
410 let c = self.kis.sphere.c() as usize;
411 if self.kis.region.ty().is_edge() {
412 self.sphere().base_vertex_index(self.kis.region) + self.kis.v as usize * (b - 1)
413 - num_faces_on_edge(b, self.kis.v as usize)
414 + (self.kis.u as usize * 2 - 1 - (self.kis.v % 3 == 1) as usize) / 3
415 } else if c < b {
416 let n = b - c;
417 self.sphere().base_vertex_index(self.kis.region)
418 + (self.kis.v as usize - 1) * (2 * n - self.kis.v as usize - 2) / 2
419 - num_faces_on_interior(c, n, self.kis.v as usize)
420 + (self.kis.u as usize * 2 - 1 - ((self.kis.v as usize + c) % 3 == 1) as usize) / 3
421 } else {
422 self.sphere().base_vertex_index(self.kis.region)
423 }
424 }
425
426 fn pos(&self) -> [f64; 3] {
427 self.kis.pos()
428 }
429
430 fn degree(&self) -> usize {
431 3
432 }
433
434 fn outgoing(&self, index: usize) -> HalfEdge<Proj> {
435 assert!(index < 3, "index out of bounds");
436 let phase = (self.kis.u + 2 * self.kis.adjusted_v()) % 3;
437 debug_assert_ne!(phase, 0);
438 HalfEdge {
439 kis: tri::HalfEdge::new(
440 self.kis.sphere.clone(),
441 self.kis.region,
442 self.kis.u,
443 self.kis.v,
444 tri::HalfEdgeDir::from_index(2 * index + phase as usize - 1),
445 ),
446 }
447 }
448}
449
450#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
452pub struct HalfEdge<Proj> {
453 kis: tri::HalfEdge<Proj>,
454}
455
456impl<Proj> HalfEdge<Proj> {
457 pub fn kis(self) -> tri::HalfEdge<Proj> {
459 self.kis
460 }
461}
462
463impl<Proj: Eq + Clone + BaseTriProjector> crate::HalfEdge for HalfEdge<Proj> {
464 type Face = Face<Proj>;
465 type Vertex = Vertex<Proj>;
466
467 fn side_index(&self) -> usize {
468 self.kis.prev().outgoing_index()
469 }
470
471 fn length(&self) -> f64 {
472 self.kis.length()
473 }
474
475 fn angle(&self) -> f64 {
476 let v_a = self.prev().start().pos();
477 let v_b = self.start().pos();
478 let v_c = self.next().start().pos();
479 crate::util::angle(v_a, v_b, v_c)
480 }
481
482 fn inside(&self) -> Face<Proj> {
483 Face {
484 center: self.kis.prev().start(),
485 }
486 }
487
488 fn start(&self) -> Vertex<Proj> {
489 Vertex {
490 kis: self.kis.start(),
491 }
492 }
493
494 fn twin(&self) -> Self {
495 Self {
496 kis: self.kis.twin(),
497 }
498 }
499
500 fn prev(&self) -> Self {
501 Self {
502 kis: self.kis.prev().twin().prev(),
503 }
504 }
505
506 fn next(&self) -> Self {
507 Self {
508 kis: self.kis.next().twin().next(),
509 }
510 }
511}
512
513impl<Proj> HexSphere<Proj> {
514 fn base_face_index(&self, region: BaseRegion) -> usize {
517 let face = region.owner();
518 let num_owned_vertices_before = face.num_owned_vertices_before()
519 + (face.owns_vertex_1() && region.ty() > BaseRegionType::EDGE_0) as usize;
520 let num_edge_regions_before =
521 face.num_owned_edges_before() + (region.ty() > BaseRegionType::EDGE_0) as usize;
522 let num_interior_regions_before =
523 face.index() + (region.ty() > BaseRegionType::INTERIOR) as usize;
524 num_owned_vertices_before
525 + num_edge_regions_before * self.num_faces_per_edge_region()
526 + num_interior_regions_before * self.num_faces_per_interior_region()
527 }
528
529 fn base_vertex_index(&self, region: BaseRegion) -> usize {
531 let face = region.owner();
532 let num_edge_regions_before =
533 face.num_owned_edges_before() + (region.ty() > BaseRegionType::EDGE_0) as usize;
534 let num_interior_regions_before =
535 face.index() + (region.ty() > BaseRegionType::INTERIOR) as usize;
536 num_edge_regions_before * self.num_vertices_per_edge_region()
537 + num_interior_regions_before * self.num_vertices_per_interior_region()
538 }
539}
540
541impl<Proj> HexSphere<Proj> {
542 fn faces_from(self, region: BaseRegion) -> FaceIter<Proj> {
544 let b = self.kis.b();
545 let c = self.kis.c();
546 if region.ty().is_edge() {
547 FaceIter {
548 sphere: self,
549 region,
550 u: 3,
551 u_end: b,
552 v: 0,
553 }
554 } else if c < b {
555 let n = b - c;
556 FaceIter {
557 sphere: self,
558 region,
559 u: 1 + c % 3,
560 u_end: n - 1,
561 v: 1,
562 }
563 } else {
564 FaceIter {
567 sphere: self,
568 region,
569 u: c % 3,
570 u_end: 1,
571 v: 0,
572 }
573 }
574 }
575}
576
577#[derive(Clone, Debug)]
579pub struct FaceIter<Proj> {
580 sphere: HexSphere<Proj>,
581 region: BaseRegion,
582 u: u32,
583 u_end: u32,
584 v: u32,
585}
586
587impl<Proj: Eq + Clone + BaseTriProjector> Iterator for FaceIter<Proj> {
588 type Item = Face<Proj>;
589 fn next(&mut self) -> Option<Face<Proj>> {
590 loop {
591 if self.u < self.u_end {
592 let res = Face::from_center_unchecked(tri::Vertex {
593 sphere: self.sphere.kis.clone(),
594 region: self.region,
595 u: self.u,
596 v: self.v,
597 });
598 self.u += 3;
599 return Some(res);
600 } else if self.region.ty().is_edge() {
601 if self.v < self.sphere.kis.c() {
602 self.v += 1;
603 self.u = 1 + (self.v + 2) % 3;
604 continue;
605 } else if self.u <= self.u_end
606 && self.region.ty() == BaseRegionType::EDGE_0
607 && self.region.owner().owns_vertex_1()
608 {
609 let res = Face::from_center_unchecked(tri::Vertex {
610 sphere: self.sphere.kis.clone(),
611 region: self.region,
612 u: self.u,
613 v: self.v,
614 });
615 self.u += 3;
616 return Some(res);
617 }
618 } else {
619 let n = self.sphere.kis.b() - self.sphere.kis.c();
620 if self.v + 1 < n {
621 self.v += 1;
622 self.u = 1 + (self.v + self.sphere.kis.c() + 2) % 3;
623 self.u_end = n - self.v;
624 continue;
625 }
626 }
627 if let Some(region) = self.sphere.kis.base().next_region(self.region) {
628 *self = self.sphere.clone().faces_from(region);
629 continue;
630 } else {
631 return None;
632 }
633 }
634 }
635}
636
637impl<Proj: Eq + Clone + BaseTriProjector> HexSphere<Proj> {
638 fn vertices_from(self, region: BaseRegion) -> VertexIter<Proj> {
640 let b = self.kis.b();
641 let c = self.kis.c();
642 if region.ty().is_edge() {
643 VertexIter {
644 sphere: self,
645 region,
646 u: 1,
647 u_end: b,
648 v: 0,
649 skip: false,
650 }
651 } else if c < b {
652 let n = b - c;
653 VertexIter {
654 sphere: self,
655 region,
656 u: 1 + (c % 3 == 0) as u32,
657 u_end: n.saturating_sub(1),
658 v: 1,
659 skip: c % 3 == 1,
660 }
661 } else {
662 VertexIter {
665 sphere: self,
666 region,
667 u: (c % 3 == 0) as u32,
668 u_end: 1,
669 v: 0,
670 skip: c % 3 == 2,
671 }
672 }
673 }
674}
675
676#[derive(Clone, Debug)]
678pub struct VertexIter<Proj> {
679 sphere: HexSphere<Proj>,
680 region: BaseRegion,
681 u: u32,
682 u_end: u32,
683 v: u32,
684 skip: bool,
685}
686
687impl<Proj: Eq + Clone + BaseTriProjector> Iterator for VertexIter<Proj> {
688 type Item = Vertex<Proj>;
689 fn next(&mut self) -> Option<Vertex<Proj>> {
690 loop {
691 if self.u < self.u_end {
692 let res = Vertex::new(tri::Vertex {
693 sphere: self.sphere.kis.clone(),
694 region: self.region,
695 u: self.u,
696 v: self.v,
697 });
698 self.u += 1;
699 self.u += self.skip as u32;
700 self.skip = !self.skip;
701 return Some(res);
702 } else if self.region.ty().is_edge() {
703 if self.v < self.sphere.kis.c() {
704 self.v += 1;
705 (self.u, self.skip) = match self.v % 3 {
706 0 => (1, false),
707 1 => (2, false),
708 _ => (1, true),
709 };
710 continue;
711 }
712 } else {
713 let n = self.sphere.kis.b() - self.sphere.kis.c();
714 if self.v + 1 < n {
715 self.v += 1;
716 self.u_end = n - self.v;
717 (self.u, self.skip) = match (self.v + self.sphere.kis.c()) % 3 {
718 0 => (1, false),
719 1 => (2, false),
720 _ => (1, true),
721 };
722 continue;
723 }
724 }
725 if let Some(region) = self.sphere.kis.base().next_region(self.region) {
726 *self = self.sphere.clone().vertices_from(region);
727 continue;
728 } else {
729 return None;
730 }
731 }
732 }
733}