# Delaunay 三角分割

Voronoi 與 Delaunay 三角分割是一體的兩面，在〈玩轉 p5.js〉中就談過兩者的關係。

``````import numpy as np
from scipy import spatial

def polygon(points):
return cq.Workplane().polyline(points).close()

n = 50
points = np.random.rand(n, 2)
delaunay  = spatial.Delaunay(points)

r = cq.Workplane()
for tri in delaunay.simplices:
``````

``````import numpy as np
from scipy import spatial

from random import randint
from scipy.spatial import ConvexHull
from cadquery import Vector, Edge, Wire, Solid, Shell, Face

def polyhedron(points, faces):
def _edges(vectors, face_indices):
leng_vertices = len(face_indices)
return (
Edge.makeLine(
vectors[face_indices[i]],
vectors[face_indices[(i + 1) % leng_vertices]]
)
for i in range(leng_vertices)
)

vectors = [Vector(*p) for p in points]

return Solid.makeSolid(
Shell.makeShell(
Face.makeFromWires(
Wire.assembleEdges(
_edges(vectors, face_indices)
)
)
for face_indices in faces
)
)

def hull3D(points):
hull = ConvexHull(points)
vertices = [points[i] for i in hull.vertices]
v_i_lookup = {v: i for i, v in enumerate(vertices)}
faces = [
[v_i_lookup[points[i]] for i in face]
for face in hull.simplices
]

return polyhedron(vertices, faces)

def random_color():
return (randint(0, 255), randint(0, 255), randint(0, 255))

# 3D Delaunay

n = 10
points = np.random.rand(n, 3)
delaunay = spatial.Delaunay(points)

r = cq.Workplane()
for tetrahedron in delaunay.simplices:
p = hull3D([tuple(p) for p in points[tetrahedron]])