NGF_on_Fractale / src /modules /geometry.py
antaris's picture
Upload 33 files
5543795 verified
Raw History Blame Contribute Delete
6.67 kB
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