from __future__ import annotations from dataclasses import dataclass from typing import Dict, List, Sequence, Set, Tuple import networkx as nx import numpy as np Array = np.ndarray @dataclass class Cell: address: Tuple[int, ...] vertex_positions: List[Array] level: int vertex_ids: Tuple[int, ...] | None = None def _deduplicate_and_build_graph( leaf_cells: Sequence[Cell], dim: int, ) -> Tuple[nx.Graph, Dict[int, Array], Set[int]]: """ Aus den Leaf-Zellen einen Graphen mit eindeutigen Knoten, Positionen und Randmarkierung bauen. """ pos_to_id: Dict[Tuple[float, ...], int] = {} positions: Dict[int, Array] = {} next_id = 0 G = nx.Graph() for cell in leaf_cells: vid_list: List[int] = [] for p in cell.vertex_positions: key = tuple(np.round(p.astype(float), 8)) if key not in pos_to_id: nid = next_id next_id += 1 pos_to_id[key] = nid positions[nid] = p.astype(float) G.add_node(nid) else: nid = pos_to_id[key] vid_list.append(nid) cell.vertex_ids = tuple(vid_list) if len(vid_list) == 3: edges = [ (vid_list[0], vid_list[1]), (vid_list[1], vid_list[2]), (vid_list[2], vid_list[0]), ] elif len(vid_list) == 4: e = vid_list edges = [ (e[0], e[1]), (e[0], e[2]), (e[0], e[3]), (e[1], e[2]), (e[1], e[3]), (e[2], e[3]), ] else: raise ValueError("Cell muss 3- oder 4-Ecken haben.") for u, v in edges: if G.has_edge(u, v): continue G.add_edge(u, v, weight=1.0) boundary_nodes: Set[int] = set() if dim == 2: # Basis-Dreieck (SG) A = np.array([0.0, 0.0, 0.0]) B = np.array([1.0, 0.0, 0.0]) C = np.array([0.5, np.sqrt(3) / 2.0, 0.0]) AB = B - A BC = C - B CA = A - C def on_segment(P: Array, P0: Array, P1: Array, vec: Array) -> bool: cross = np.cross(vec, P - P0) # In der x-y-Ebene reicht z-Komponente if abs(cross[2]) > 1e-6: return False dot0 = np.dot(P - P0, P1 - P0) dot1 = np.dot(P - P1, P0 - P1) return dot0 >= -1e-6 and dot1 >= -1e-6 for nid, p in positions.items(): if ( on_segment(p, A, B, AB) or on_segment(p, B, C, BC) or on_segment(p, C, A, CA) ): boundary_nodes.add(nid) elif dim == 3: # Basis-Tetraeder (ST) A = np.array([0.0, 0.0, 0.0]) B = np.array([1.0, 0.0, 0.0]) C = np.array([0.5, np.sqrt(3) / 2.0, 0.0]) D = np.array([0.5, np.sqrt(3) / 6.0, np.sqrt(6) / 3.0]) faces = [ (A, B, C), (A, B, D), (A, C, D), (B, C, D), ] normals = [] for P0, P1, P2 in faces: n = np.cross(P1 - P0, P2 - P0) normals.append((P0, n)) for nid, p in positions.items(): for P0, n in normals: dist = float(np.dot(n, p - P0)) if abs(dist) < 1e-6: boundary_nodes.add(nid) break else: raise ValueError("dim muss 2 oder 3 sein.") for nid in G.nodes: G.nodes[nid]["pos"] = positions[nid] G.nodes[nid]["is_boundary"] = nid in boundary_nodes return G, positions, boundary_nodes def generate_sg(level: int): """ Erzeuge einen Sierpinski-Gasket-Approximanten (2D, in 3D eingebettet mit z=0). Rückgabe: (Graph, Positionen, Randknoten, Leaf-Zellen) """ if level < 0: raise ValueError("level muss >= 0 sein.") A = np.array([0.0, 0.0, 0.0]) B = np.array([1.0, 0.0, 0.0]) C = np.array([0.5, np.sqrt(3) / 2.0, 0.0]) root = Cell(address=(), vertex_positions=[A, B, C], level=0) leaf_cells: List[Cell] = [root] all_cells: List[Cell] = [root] for _ in range(level): new_leaf: List[Cell] = [] for cell in leaf_cells: p0, p1, p2 = cell.vertex_positions addr = cell.address m01 = 0.5 * (p0 + p1) m12 = 0.5 * (p1 + p2) m20 = 0.5 * (p2 + p0) c0 = Cell(address=addr + (0,), vertex_positions=[p0, m01, m20], level=cell.level + 1) c1 = Cell(address=addr + (1,), vertex_positions=[m01, p1, m12], level=cell.level + 1) c2 = Cell(address=addr + (2,), vertex_positions=[m20, m12, p2], level=cell.level + 1) new_leaf.extend([c0, c1, c2]) all_cells.extend([c0, c1, c2]) leaf_cells = new_leaf G, positions, boundary_nodes = _deduplicate_and_build_graph(leaf_cells, dim=2) return G, positions, boundary_nodes, leaf_cells def generate_st(level: int): """ Erzeuge einen Sierpinski-Tetraeder-Approximanten (3D). Rückgabe: (Graph, Positionen, Randknoten, Leaf-Zellen) """ if level < 0: raise ValueError("level muss >= 0 sein.") A = np.array([0.0, 0.0, 0.0]) B = np.array([1.0, 0.0, 0.0]) C = np.array([0.5, np.sqrt(3) / 2.0, 0.0]) D = np.array([0.5, np.sqrt(3) / 6.0, np.sqrt(6) / 3.0]) root = Cell(address=(), vertex_positions=[A, B, C, D], level=0) leaf_cells: List[Cell] = [root] all_cells: List[Cell] = [root] for _ in range(level): new_leaf: List[Cell] = [] for cell in leaf_cells: p0, p1, p2, p3 = cell.vertex_positions addr = cell.address m01 = 0.5 * (p0 + p1) m02 = 0.5 * (p0 + p2) m03 = 0.5 * (p0 + p3) m12 = 0.5 * (p1 + p2) m13 = 0.5 * (p1 + p3) m23 = 0.5 * (p2 + p3) t0 = Cell(address=addr + (0,), vertex_positions=[p0, m01, m02, m03], level=cell.level + 1) t1 = Cell(address=addr + (1,), vertex_positions=[m01, p1, m12, m13], level=cell.level + 1) t2 = Cell(address=addr + (2,), vertex_positions=[m02, m12, p2, m23], level=cell.level + 1) t3 = Cell(address=addr + (3,), vertex_positions=[m03, m13, m23, p3], level=cell.level + 1) new_leaf.extend([t0, t1, t2, t3]) all_cells.extend([t0, t1, t2, t3]) leaf_cells = new_leaf G, positions, boundary_nodes = _deduplicate_and_build_graph(leaf_cells, dim=3) return G, positions, boundary_nodes, leaf_cells