šŗ Triangulation Foundations
šÆ What is Polygon Triangulation?
Polygon triangulation is the process of partitioning a polygon into a set of non-overlapping triangles using non-intersecting diagonals. It's fundamental to computational geometry.
Core Concepts
Triangulation: Partition into triangles. Number of triangles: n-2 for n vertices. Diagonals: n-3 non-intersecting diagonals. Any polygon can be triangulated.
class Polygon:
def __init__(self, vertices):
self.vertices = vertices # List of (x,y) points in order
def triangulate(self):
"""Triangulate polygon using ear clipping"""
triangles = []
remaining = list(range(len(self.vertices)))
while len(remaining) > 3:
ear = self.find_ear(remaining)
triangles.append(self.get_triangle(ear))
remaining.remove(ear)
triangles.append(self.get_triangle(remaining))
return trianglesš Polygon Basics
šÆ Types of Polygons
Simple polygons (non-self-intersecting), convex, concave, monotone, and general polygons.
Polygon Properties
Convex: All internal angles < 180Ā°. Concave: Has at least one reflex angle (> 180Ā°). Monotone: Intersection with vertical line is a segment.
def is_convex(polygon):
"""Check if polygon is convex"""
n = len(polygon)
for i in range(n):
p1 = polygon[i]
p2 = polygon[(i+1)%n]
p3 = polygon[(i+2)%n]
if cross_product(p1, p2, p3) < 0:
return False
return True
def cross_product(p1, p2, p3):
"""Compute cross product of vectors (p2-p1) and (p3-p2)"""
return (p2[0]-p1[0])*(p3[1]-p2[1]) - (p2[1]-p1[1])*(p3[0]-p2[0])āļø Ear Clipping Method
šÆ Simple and Classic
Ear clipping is the simplest triangulation algorithm. It finds an "ear" (convex vertex with no other vertices inside the triangle) and clips it off.
Algorithm Steps
Find ear: Locate convex vertex with empty triangle. Clip: Remove vertex, add diagonal. Repeat: Until 3 vertices remain.
def ear_clipping(polygon):
"""Ear clipping triangulation algorithm"""
vertices = polygon.copy()
triangles = []
n = len(vertices)
while len(vertices) > 3:
# Find an ear
for i in range(len(vertices)):
if is_ear(vertices, i):
# Add triangle
triangle = [vertices[i], vertices[(i+1)%len(vertices)], vertices[(i+2)%len(vertices)]]
triangles.append(triangle)
# Remove ear
vertices.pop((i+1)%len(vertices))
break
# Add final triangle
triangles.append(vertices)
return trianglesš Monotone Polygon Triangulation
šÆ Optimal for Monotone Polygons
Monotone polygon triangulation runs in O(n) time, making it optimal for special cases.
Monotone Decomposition
Decompose: Split polygon into monotone pieces. Triangulate: O(n) per monotone piece. Total: O(n log n) for general polygons.
def triangulate_monotone(polygon):
"""Triangulate a monotone polygon"""
# Assumes polygon is y-monotone
# Split into left and right chains
vertices = sorted(polygon, key=lambda p: p[1]) # Sort by y
triangles = []
stack = [vertices[0], vertices[1]]
for i in range(2, len(vertices)-1):
# Process vertices in order
# Add diagonals when possible
pass
return trianglesš® Delaunay Triangulation
šÆ Optimal Mesh Generation
Delaunay triangulation maximizes minimum angle in the mesh, avoiding skinny triangles. It's fundamental to mesh generation.
Delaunay Properties
Empty circumcircle: No point inside circumcircle of any triangle. Max min angle: Maximizes the minimum angle. Dual: Dual is Voronoi diagram.
def delaunay_triangulation(points):
"""Compute Delaunay triangulation using Bowyer-Watson"""
# Initialize super-triangle
super_triangle = find_super_triangle(points)
triangulation = [super_triangle]
for point in points:
# Find triangles with point in circumcircle
bad_triangles = []
for triangle in triangulation:
if point_in_circumcircle(point, triangle):
bad_triangles.append(triangle)
# Find boundary edges
boundary = find_boundary_edges(bad_triangles)
# Remove bad triangles
for triangle in bad_triangles:
triangulation.remove(triangle)
# Add new triangles
for edge in boundary:
triangulation.append([edge[0], edge[1], point])
return triangulationš§ Constrained Triangulation
šÆ Triangulation with Constraints
Constrained triangulation respects given edges (like polygon boundaries) that must be included in the triangulation.
Constrained Delaunay
Fixed edges: Prescribed edges in triangulation. CDT: Constrained Delaunay Triangulation. Applications: Terrain modeling, FEM meshing.
def constrained_triangulation(points, constraints):
"""Constrained Delaunay triangulation"""
# Start with regular Delaunay
triangulation = delaunay_triangulation(points)
# Enforce constraints
for constraint in constraints:
# Ensure edge exists in triangulation
if not edge_exists(triangulation, constraint):
# Flip edges to include constraint
flip_edges(triangulation, constraint)
return triangulationš Voronoi Diagrams
šÆ Dual of Delaunay
Voronoi diagrams partition the plane into regions closest to each point. They are the dual of Delaunay triangulation.
Voronoi Properties
Cells: Region of points closest to each site. Dual: Delaunay triangulation. Applications: Nearest neighbor, interpolation.
def voronoi_diagram(points):
"""Compute Voronoi diagram from Delaunay triangulation"""
delaunay = delaunay_triangulation(points)
voronoi = []
for triangle in delaunay:
# Circumcenter of triangle is Voronoi vertex
center = circumcenter(triangle)
voronoi.append(center)
return voronoiš Edge Flipping
šÆ Improving Triangulation Quality
Edge flipping replaces diagonal of a convex quadrilateral to improve quality (Delaunay property).
Flip Algorithm
Check: Test if edge should be flipped (Delaunay violation). Flip: Replace diagonal with other diagonal. Iterate: Until all edges are Delaunay.
def edge_flip(triangulation, edge):
"""Flip an edge in the triangulation"""
# Find quadrilateral containing the edge
quad = find_quadrilateral(triangulation, edge)
if quad is None:
return triangulation
# Check if flip improves quality
if should_flip(quad):
# Remove edge, add other diagonal
triangulation.remove(edge)
new_edge = [quad[1], quad[3]]
triangulation.append(new_edge)
return triangulationš Quality Mesh Generation
šÆ High-Quality Triangular Meshes
Quality meshes avoid skinny triangles, ensure good aspect ratios, and have controlled element sizes.
Quality Metrics
Aspect ratio: Longest/shortest edge. Min angle: Smallest angle in mesh. Size control: Local mesh density.
def quality_measure(triangle):
"""Compute quality of a triangle"""
# Aspect ratio: longest edge / shortest edge
edges = [
distance(triangle[0], triangle[1]),
distance(triangle[1], triangle[2]),
distance(triangle[2], triangle[0])
]
return max(edges) / min(edges)
def mesh_quality(mesh):
"""Compute overall mesh quality"""
qualities = [quality_measure(t) for t in mesh]
return min(qualities), max(qualities), np.mean(qualities)š Dual Graphs
šÆ Dual Graph Properties
The dual graph connects adjacent triangles in a triangulation. It's useful for mesh traversal and operations.
Dual Applications
Mesh traversal: Efficient navigation. Edge collapse: Simplification. Refinement: Adaptive subdivision.
def build_dual_graph(triangulation):
"""Build dual graph of triangulation"""
dual = {}
for i, tri in enumerate(triangulation):
dual[i] = []
for j, other in enumerate(triangulation):
if i != j:
# Check if triangles share an edge
if shares_edge(tri, other):
dual[i].append(j)
return dualš Point Location
šÆ Finding Triangles
Point location finds which triangle contains a given point. Essential for interpolation, querying, and analysis.
Methods
Walking: Walk through mesh to find triangle. Hierarchical: Use tree structures. Jump-and-walk: Random jump + walk.
def point_in_triangle(point, triangle):
"""Check if point is inside triangle"""
# Barycentric coordinate test
a, b, c = triangle
v0 = b - a
v1 = c - a
v2 = point - a
d00 = np.dot(v0, v0)
d01 = np.dot(v0, v1)
d11 = np.dot(v1, v1)
d20 = np.dot(v2, v0)
d21 = np.dot(v2, v1)
denom = d00 * d11 - d01 * d01
u = (d11 * d20 - d01 * d21) / denom
v = (d00 * d21 - d01 * d20) / denom
return u >= 0 and v >= 0 and u + v <= 1š Applications
šÆ Real-World Uses
Triangulation is used in computer graphics, finite element analysis, terrain modeling, robotics, and geographic information systems.
Application Domains
Graphics: 3D rendering, texture mapping. FEM: Structural analysis. GIS: Terrain representation. Robotics: Path planning.
class TerrainModel:
def __init__(self, points, triangles):
self.points = points
self.triangles = triangles
def interpolate(self, x, y):
"""Interpolate height at (x,y) using triangulation"""
# Find containing triangle
for triangle in self.triangles:
if point_in_triangle([x, y], triangle):
# Barycentric interpolation
return interpolate_barycentric(x, y, triangle)
return Noneā” Algorithms
šÆ Algorithmic Approaches
Various algorithms: Sweep-line, divide-and-conquer, incremental insertion, and randomized algorithms.
Algorithm Comparison
Divide-and-conquer: O(n log n). Incremental: O(nĀ²) worst-case, O(n log n) expected. Sweep-line: O(n log n).
def divide_and_conquer_triangulation(points):
"""Divide-and-conquer triangulation"""
if len(points) <= 3:
return [points]
# Divide points by x-coordinate
mid = len(points) // 2
left = points[:mid]
right = points[mid:]
# Recursively triangulate
left_tri = divide_and_conquer_triangulation(left)
right_tri = divide_and_conquer_triangulation(right)
# Merge triangulations
return merge_triangulations(left_tri, right_tri)š¬ Advanced Topics
šÆ Research Directions
3D triangulation, adaptive refinement, anisotropic meshing, and GPU-accelerated triangulation.
Current Research
3D tetrahedralization: Volume meshing. Anisotropic: Direction-dependent quality. GPU: Parallel triangulation.
def adaptive_refinement(mesh, error_metric):
"""Adaptive mesh refinement based on error"""
refined = []
for triangle in mesh:
if error_metric(triangle) > threshold:
# Subdivide triangle
refined.extend(subdivide_triangle(triangle))
else:
refined.append(triangle)
return refined