use petgraph::graph::EdgeIndex;
use petgraph::graph::NodeIndex;
use std::collections::HashMap;
use crate::geometry::*;
use crate::platonic_solids::make_icosahedron;
use crate::Polyhedron;
#[derive(Debug)]
struct GeodesicBuilder {
polyhedron: Polyhedron,
m: u64,
n: u64,
}
type EdgeReplacementMap = HashMap<EdgeIndex, NodeIndex>;
impl GeodesicBuilder {
pub fn subdivide(&mut self) {
debug_assert_eq!(
self.polyhedron.assert_consistency(),
Ok(()),
"Failed consistency before subdivide"
);
let mut faces_new = Vec::new();
let edge_replacement_map = self.create_vertices_for_edges();
let faces_old = self.polyhedron.faces.clone();
for face_old in &faces_old {
self.subdivide_face(&face_old, &edge_replacement_map, &mut faces_new)
}
for face_old in &faces_old {
self.remove_face_edges(&face_old)
}
self.polyhedron.faces = faces_new;
self.m *= 2;
debug_assert_eq!(
self.polyhedron.assert_consistency(),
Ok(()),
"Failed consistency after subdivide"
);
}
fn create_vertices_for_edges(&mut self) -> EdgeReplacementMap {
let mut edge_to_vertex: EdgeReplacementMap = HashMap::new();
let graph = &mut self.polyhedron.graph;
let mut edges: Vec<EdgeIndex> = Vec::new();
edges.extend(graph.edge_indices());
for edge in &edges {
let vertex_position = {
let (node_a, node_b) = graph.edge_endpoints(*edge).expect("Illegal edge access");
let wa = WeightedValue {
value: graph.node_weight(node_a).expect("Illegal vertex lookup"),
weight: 1.0,
};
let wb = WeightedValue {
value: graph.node_weight(node_b).expect("Illegal vertex lookup"),
weight: 1.0,
};
weighted_centroid(&[wa, wb])
};
let vertex = graph.add_node(vertex_position);
edge_to_vertex.insert(*edge, vertex);
}
edge_to_vertex
}
fn subdivide_face(
&mut self,
face: &Face,
edge_to_vertex: &EdgeReplacementMap,
new_faces: &mut Vec<Face>,
) {
{
let graph = &mut self.polyhedron.graph;
let v0 = face.nodes[0].ix;
let v1 = face.nodes[1].ix;
let v2 = face.nodes[2].ix;
let vertex_pairs = [(v0, v1), (v1, v2), (v2, v0)];
let mid_nodes = {
let get_mid_node = |(node_a, node_b): (NodeIndex, NodeIndex)| -> NodeIndex {
let edge = graph.find_edge(node_a, node_b);
let edge = edge.expect("Illegal node pair");
edge_to_vertex[&edge]
};
[
get_mid_node(vertex_pairs[0]),
get_mid_node(vertex_pairs[1]),
get_mid_node(vertex_pairs[2]),
]
};
for (i, (node_a, node_b)) in vertex_pairs.iter().enumerate() {
let node_mid = mid_nodes[i];
graph.update_edge(*node_a, node_mid, ());
graph.update_edge(*node_b, node_mid, ());
}
graph.update_edge(mid_nodes[0], mid_nodes[1], ());
graph.update_edge(mid_nodes[0], mid_nodes[2], ());
graph.update_edge(mid_nodes[1], mid_nodes[2], ());
new_faces.push(Face::new_triangle(&[
VertexHandle::new(mid_nodes[0]),
VertexHandle::new(mid_nodes[1]),
VertexHandle::new(mid_nodes[2]),
]));
new_faces.push(Face::new_triangle(&[
VertexHandle::new(v0),
VertexHandle::new(mid_nodes[0]),
VertexHandle::new(mid_nodes[2]),
]));
new_faces.push(Face::new_triangle(&[
VertexHandle::new(v1),
VertexHandle::new(mid_nodes[0]),
VertexHandle::new(mid_nodes[1]),
]));
new_faces.push(Face::new_triangle(&[
VertexHandle::new(v2),
VertexHandle::new(mid_nodes[1]),
VertexHandle::new(mid_nodes[2]),
]));
}
}
fn remove_face_edges(&mut self, face: &Face) {
let graph = &mut self.polyhedron.graph;
let v0 = face.nodes[0];
let v1 = face.nodes[1];
let v2 = face.nodes[2];
let vertex_pairs = [(v0, v1), (v1, v2), (v2, v0)];
for (node_a, node_b) in &vertex_pairs {
let edge = graph.find_edge(node_a.ix, node_b.ix);
if let Some(edge) = edge {
graph.remove_edge(edge);
}
}
}
fn to_goldberg(&self) -> Polyhedron {
debug_assert!(self.polyhedron.assert_consistency().is_ok());
let mut graph_new = VertexGraph::default();
let vertex_map: HashMap<&Face, NodeIndex> = {
let mut vertex_map = HashMap::new();
for face in &self.polyhedron.faces {
let node_pos = face.center(&self.polyhedron.graph);
let node = graph_new.add_node(node_pos);
vertex_map.insert(face, node);
}
vertex_map
};
for (_, (face_a, face_b)) in get_edge_face_map(&self.polyhedron) {
let node_a = vertex_map[face_a];
let node_b = vertex_map[face_b];
graph_new.add_edge(node_a, node_b, ());
}
let faces_new = {
let sort_vertices = |vertices: &mut Vec<NodeIndex>| {
for i in 0..vertices.len() {
let v1 = vertices[i];
for j in (i + 1)..vertices.len() {
let v2 = vertices[j];
if graph_new.find_edge(v1, v2).is_some() {
vertices.swap(j, i + 1);
break;
}
}
}
};
make_node_face_map(&self.polyhedron)
.iter()
.map(|(_, faces)| {
let mut vertices: Vec<NodeIndex> =
faces.iter().map(|f| vertex_map[f]).collect();
sort_vertices(&mut vertices);
let f = Face::from_node_index(&vertices);
{
let contains_edge = |(v1, v2): (VertexHandle, VertexHandle)| {
graph_new.find_edge_undirected(v1.ix, v2.ix).is_some()
};
debug_assert!(
f.edges().into_iter().all(contains_edge),
"Created face {:?} with edges that are not in graph {:?}",
f,
graph_new
);
};
f
})
.collect()
};
let result = Polyhedron {
graph: graph_new,
faces: faces_new,
};
debug_assert_eq!(
result.assert_consistency(),
Ok(()),
"Failed consistency after in goldberg conversion"
);
result
}
}
fn get_edge_face_map<'a>(polyhedron: &'a Polyhedron) -> HashMap<EdgeIndex, (&'a Face, &'a Face)> {
let mut map: HashMap<EdgeIndex, Vec<&Face>> = HashMap::new();
{
let mut insert_face = |key: EdgeIndex, value: &'a Face| {
let vec = map.entry(key).or_insert_with(Vec::new);
if !vec.contains(&value) {
vec.push(value);
}
};
for face in &polyhedron.faces {
for (node_a, node_b) in face.edges() {
let edge = polyhedron.graph.find_edge(node_a.ix, node_b.ix);
let edge = edge.expect("Illegal edge access.");
insert_face(edge, face)
}
}
}
map.iter()
.map(|(k, v)| {
assert_eq!(
v.len(),
2,
"Found edge with {} adjacent faces. Expected 2.",
v.len()
);
(*k, (v[0], v[1]))
})
.collect()
}
fn make_node_face_map<'a>(polyhedron: &'a Polyhedron) -> HashMap<NodeIndex, Vec<&'a Face>> {
let mut map: HashMap<NodeIndex, Vec<&Face>> = HashMap::new();
{
let mut insert = |key: NodeIndex, value: &'a Face| {
let vec = map.entry(key).or_insert_with(Vec::new);
vec.push(value);
};
for face in &polyhedron.faces {
for node in face.nodes() {
insert(node.ix, face);
}
}
}
map
}
pub fn build_icosahedral_geodesic(subdivisions: u64) -> Polyhedron {
let mut geo = GeodesicBuilder {
polyhedron: make_icosahedron(),
m: 1,
n: 0,
};
for _ in 0..subdivisions {
geo.subdivide();
}
geo.polyhedron
}
pub fn build_icosahedral_goldberg(subdivisions: u64) -> Polyhedron {
let mut geo = GeodesicBuilder {
polyhedron: make_icosahedron(),
m: 1,
n: 0,
};
for _ in 0..subdivisions {
geo.subdivide();
}
geo.to_goldberg()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::topology::Tiling;
use std::time::Instant;
fn check_subdivision(m: u64) {
let gg = build_icosahedral_geodesic(m);
let n = 0_u64;
let m = 2_u64.pow(m as u32);
let t = n * m + n * n + m * m;
let face_count = gg.faces.len() as u64;
if face_count != (t * 20) {
panic!("Number of faces is {} instead of {}.", face_count, 20 * t)
}
let edge_count = gg.graph.edge_count() as u64;
if edge_count != (t * 30) {
panic!("Number of edges is {} instead of {}.", edge_count, 30 * t)
}
let vertex_count = gg.graph.node_count() as u64;
if vertex_count != (t * 10 + 2) {
panic!(
"Number of vertices is {} instead of {}.",
vertex_count,
10 * t + 3
)
}
}
#[test]
fn test_subdivision() {
let start = Instant::now();
for n in 0..5 {
check_subdivision(n);
}
let end = Instant::now();
println!("{} seconds for whatever you did.", (end - start).as_secs());
}
#[test]
fn test_goldberg_polyhedron() {
for i in 0..5 {
let start = Instant::now();
let igp = build_icosahedral_goldberg(i);
let end = Instant::now();
println!(
"{} seconds for creating a {} subdivision Goldberg Polyhedron.",
(end - start).as_secs(),
i
);
let n = 0;
let m = 2_i32.pow(i as u32);
let t = (m * n + m * m + n * n) as usize;
println!("with {} nodes", igp.graph.node_count());
assert_eq!(igp.faces.len(), 10 * t + 2);
assert_eq!(igp.graph.node_count(), 20 * t);
assert_eq!(igp.graph.edge_count(), 30 * t);
}
}
#[test]
fn test_goldberg_edge_validity() {
for i in 0..5 {
let igp = build_icosahedral_goldberg(i);
for face in igp.faces.iter() {
for (v1, v2) in face.edges() {
assert_ne!(
None,
igp.graph.find_edge(v1.ix, v2.ix),
"Found edge in face ({:?}, {:?}) that is missing from graph {:?}",
v1,
v2,
igp.graph
)
}
}
}
}
#[test]
fn test_geodesic_consistency() {
for i in 0..5 {
println!("Checking subdivision {}.", i);
let ic = build_icosahedral_geodesic(i);
for face in ic.faces() {
for (v1, v2) in face.edges() {
assert_ne!(
ic.graph.find_edge_undirected(v1.ix, v2.ix),
None,
"Found invalid edge: ({:?}, {:?}) in face",
v1,
v2
);
}
}
}
}
#[test]
fn test_geodesic_map_consistency() {
for i in 0..5 {
let ic = build_icosahedral_geodesic(i);
let edge_face_map = get_edge_face_map(&ic);
let node_face_map = make_node_face_map(&ic);
for (edge, edge_faces) in edge_face_map {
let (v1, v2) = ic.graph.edge_endpoints(edge).unwrap();
let faces_v1 = &node_face_map[&v1];
assert!(faces_v1.contains(&edge_faces.0));
assert!(faces_v1.contains(&edge_faces.1));
let faces_v2 = &node_face_map[&v2];
assert!(faces_v2.contains(&edge_faces.0));
assert!(faces_v2.contains(&edge_faces.1));
}
}
}
#[test]
fn test_get_node_face_map() {
for i in 0..5 {
println!("Checking subdivision {}.", i);
let ic = build_icosahedral_geodesic(i);
let nfm = make_node_face_map(&ic);
for (node, faces) in nfm {
assert!(
faces.len() == 5 || faces.len() == 6,
"Expected there to be 5 or 6 adjacent faces adjacent to {:?}, but found {:?}",
node,
faces.len()
);
assert!(ic.graph.contains_node(node));
for face in &faces {
for (v1, v2) in face.edges() {
assert!(ic.graph.find_edge(v1.ix, v2.ix).is_some())
}
}
}
}
}
#[test]
fn test_goldberg_tiling() {
for i in 0..5 {
println!("Checking subdivision {}.", i);
let igp = build_icosahedral_goldberg(i);
for node in igp.iter() {
for (boundary, neighbour) in igp.adjacent(node) {
assert_ne!(
neighbour, None,
"Found unconnected edge: ({:?}, {:?})",
boundary, neighbour
);
}
}
}
}
#[test]
fn test_goldberg_polyhedron_node_degrees() {
for i in 0..5 {
let igp = build_icosahedral_goldberg(i);
let graph: VertexGraph = igp.into();
graph.node_indices().for_each(|n_ix| {
let nc = graph.neighbors(n_ix).count();
assert_eq!(nc, 3, "Found node with {} neighbors. Expected 3.", nc);
})
}
}
}