Spaces:
Sleeping
Sleeping
File size: 10,465 Bytes
c89947b | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 | """
Geometric realization from Rivin LP angles.
Construct Euclidean point positions from triangle angles using rigid construction.
"""
import numpy as np
from typing import List, Tuple, Dict, Set, Optional
import networkx as nx
def realize_from_angles_rigid(
triangles: List[Tuple[int, int, int]],
angles: np.ndarray, # Shape: (n_triangles, 3), in RADIANS
boundary_vertices: Optional[Set[int]] = None,
verbose: bool = False
) -> Dict:
"""
Rigidly construct point positions from triangle angles.
Algorithm:
1. Place v1 = 0, v2 = 1 (complex plane)
2. Find first triangle containing both v1 and v2
3. Place third vertex of that triangle using law of sines
4. Incrementally place remaining vertices using shared edges
Args:
triangles: List of (v0, v1, v2) tuples
angles: Array of shape (n_triangles, 3) with angles in radians
boundary_vertices: Optional set of boundary vertices
verbose: Print progress
Returns:
Dict with 'success', 'points', 'vertex_list', etc.
"""
# Get all vertices
all_vertices = set()
for tri in triangles:
all_vertices.update(tri)
vertex_list = sorted(all_vertices)
n_vertices = len(vertex_list)
if verbose:
print(f"Rigid construction from {len(triangles)} triangles, {n_vertices} vertices")
# Build triangle -> angles mapping
tri_to_angles = {}
for i, tri in enumerate(triangles):
tri_to_angles[tuple(sorted(tri))] = angles[i]
# Build vertex -> triangles mapping
vertex_to_tris = {v: [] for v in vertex_list}
for i, (v0, v1, v2) in enumerate(triangles):
vertex_to_tris[v0].append((i, v0, v1, v2))
vertex_to_tris[v1].append((i, v0, v1, v2))
vertex_to_tris[v2].append((i, v0, v1, v2))
# Use complex numbers for 2D positions
positions = {} # vertex -> complex position
# Step 1: Fix first two vertices
v1 = vertex_list[0]
v2 = vertex_list[1]
positions[v1] = 0.0 + 0.0j
positions[v2] = 1.0 + 0.0j
if verbose:
print(f" Fixed: v{v1} = 0, v{v2} = 1")
# Step 2: Find a triangle containing both v1 and v2
first_tri = None
first_tri_angles = None
for tri_id, (v0_t, v1_t, v2_t) in enumerate(triangles):
tri_verts = {v0_t, v1_t, v2_t}
if v1 in tri_verts and v2 in tri_verts:
# Found it!
first_tri = (v0_t, v1_t, v2_t)
first_tri_angles = angles[tri_id]
break
if first_tri is None:
return {
'success': False,
'message': 'Could not find triangle containing first two vertices',
'points': None,
'vertex_list': vertex_list,
}
# Step 3: Place third vertex of first triangle
v3 = [v for v in first_tri if v not in [v1, v2]][0]
# Get angles: we need to know which angle is at which vertex
# The triangle is (v0_t, v1_t, v2_t) with angles at positions 0, 1, 2
angle_at = {}
for i, v in enumerate(first_tri):
angle_at[v] = first_tri_angles[i]
alpha = angle_at[v1] # angle at v1
beta = angle_at[v2] # angle at v2
gamma = angle_at[v3] # angle at v3
if verbose:
print(f" First triangle: {first_tri}")
print(f" Angle at v{v1}: {np.degrees(alpha):.2f}°")
print(f" Angle at v{v2}: {np.degrees(beta):.2f}°")
print(f" Angle at v{v3}: {np.degrees(gamma):.2f}°")
# Edge opposite to v3 is v1-v2, which has length 1
# Using law of sines: |v1-v3| / sin(beta) = |v2-v3| / sin(alpha) = |v1-v2| / sin(gamma)
edge_v1_v2 = 1.0 # We fixed this
edge_v1_v3 = edge_v1_v2 * np.sin(beta) / np.sin(gamma)
edge_v2_v3 = edge_v1_v2 * np.sin(alpha) / np.sin(gamma)
# v3 is at distance edge_v1_v3 from v1 = 0
# and at distance edge_v2_v3 from v2 = 1
# Solve for position using circles
p1 = positions[v1] # = 0
p2 = positions[v2] # = 1
r1 = edge_v1_v3
r2 = edge_v2_v3
# Circle intersection: find p such that |p - p1| = r1 and |p - p2| = r2
# Two solutions (above/below the real axis)
d = abs(p2 - p1) # = 1
if r1 + r2 < d or r1 + d < r2 or r2 + d < r1:
return {
'success': False,
'message': f'Triangle inequality violated for first triangle',
'points': None,
'vertex_list': vertex_list,
}
# Using formula for circle intersection
a = (r1**2 - r2**2 + d**2) / (2 * d)
h_sq = r1**2 - a**2
if h_sq < 0:
h = 0
else:
h = np.sqrt(h_sq)
# Point along v1-v2 at distance a from v1
p_mid = p1 + a * (p2 - p1) / d
# Perpendicular direction (rotate by 90°)
perp = (p2 - p1) / d * 1j # Multiply by i to rotate 90°
# Two solutions
p3_option1 = p_mid + h * perp
p3_option2 = p_mid - h * perp
# Choose the one that gives positive orientation (counterclockwise)
# For triangle (v1, v2, v3), we want the signed area to be positive
def signed_area(p1, p2, p3):
return 0.5 * ((p2 - p1).real * (p3 - p1).imag - (p2 - p1).imag * (p3 - p1).real)
area1 = signed_area(p1, p2, p3_option1)
area2 = signed_area(p1, p2, p3_option2)
# Choose the option with positive area (or larger absolute area if both negative)
if area1 > 0 or (area1 == 0 and area2 < 0):
positions[v3] = p3_option1
else:
positions[v3] = p3_option2
if verbose:
print(f" Placed v{v3} at {positions[v3]}")
print(f" Distances: |v{v1}-v{v3}| = {abs(positions[v3] - positions[v1]):.6f} (target: {r1:.6f})")
print(f" |v{v2}-v{v3}| = {abs(positions[v3] - positions[v2]):.6f} (target: {r2:.6f})")
# Step 4: Incrementally place remaining vertices
placed = {v1, v2, v3}
remaining = set(vertex_list) - placed
max_iterations = 100
iteration = 0
while remaining and iteration < max_iterations:
iteration += 1
placed_any = False
for v in list(remaining):
# Find a triangle containing v and at least two already-placed vertices
for tri_id, (v0_t, v1_t, v2_t) in enumerate(triangles):
tri_verts = [v0_t, v1_t, v2_t]
if v not in tri_verts:
continue
# Get the other two vertices
others = [u for u in tri_verts if u != v]
if not all(u in placed for u in others):
continue
# We have a triangle with v and two placed vertices!
u1, u2 = others
# Get angles
angle_at = {}
for i, vt in enumerate(tri_verts):
angle_at[vt] = angles[tri_id][i]
alpha = angle_at[v]
beta = angle_at[u1]
gamma = angle_at[u2]
# Law of sines to get edge lengths
edge_u1_u2 = abs(positions[u2] - positions[u1])
edge_v_u1 = edge_u1_u2 * np.sin(gamma) / np.sin(alpha)
edge_v_u2 = edge_u1_u2 * np.sin(beta) / np.sin(alpha)
# Circle intersection
p1 = positions[u1]
p2 = positions[u2]
r1 = edge_v_u1
r2 = edge_v_u2
d = abs(p2 - p1)
# Check triangle inequality
if r1 + r2 < d - 1e-10 or r1 + d < r2 - 1e-10 or r2 + d < r1 - 1e-10:
continue # Skip this triangle, try another
a = (r1**2 - r2**2 + d**2) / (2 * d)
h_sq = r1**2 - a**2
if h_sq < -1e-10:
continue
elif h_sq < 0:
h = 0
else:
h = np.sqrt(h_sq)
p_mid = p1 + a * (p2 - p1) / d
perp = (p2 - p1) / d * 1j
p_option1 = p_mid + h * perp
p_option2 = p_mid - h * perp
# Choose the option that doesn't overlap with existing vertices
# and maintains positive orientation
min_dist_1 = min(abs(p_option1 - positions[u]) for u in placed)
min_dist_2 = min(abs(p_option2 - positions[u]) for u in placed)
# If one option is too close to an existing vertex, use the other
if min_dist_1 < 1e-6 and min_dist_2 >= 1e-6:
positions[v] = p_option2
elif min_dist_2 < 1e-6 and min_dist_1 >= 1e-6:
positions[v] = p_option1
else:
# Both are valid, choose based on positive signed area
# Check orientation with the triangle we're using
area1 = (p2 - p1).real * (p_option1 - p1).imag - (p2 - p1).imag * (p_option1 - p1).real
area2 = (p2 - p1).real * (p_option2 - p1).imag - (p2 - p1).imag * (p_option2 - p1).real
# Choose the one that gives positive orientation
if abs(area1) > abs(area2):
positions[v] = p_option1 if area1 > 0 else p_option2
else:
positions[v] = p_option2 if area2 > 0 else p_option1
placed.add(v)
remaining.remove(v)
placed_any = True
if verbose:
print(f" Placed v{v} at {positions[v]:.6f} using triangle {tri_verts}")
break
if v in placed:
break
if not placed_any:
if verbose:
print(f" Could not place any more vertices. {len(remaining)} remaining.")
break
if remaining:
return {
'success': False,
'message': f'Could not place all vertices ({len(remaining)} remaining)',
'points': None,
'vertex_list': vertex_list,
'placed': list(placed),
'remaining': list(remaining),
}
# Convert to numpy array
points_array = np.zeros((n_vertices, 2))
for i, v in enumerate(vertex_list):
pos = positions[v]
points_array[i, 0] = pos.real
points_array[i, 1] = pos.imag
if verbose:
print(f" ✓ Successfully placed all {n_vertices} vertices")
return {
'success': True,
'points': points_array,
'vertex_list': vertex_list,
'message': 'Rigid construction successful',
}
|