1 (define-module (dungeon-master geom voronoi)
2 #:use-module (ice-9 receive)
3 #:use-module (srfi srfi-1)
4 #:use-module (srfi srfi-9)
5 #:use-module (dungeon-master geom point)
6 #:use-module (dungeon-master geom triangle)
7 #:use-module (dungeon-master geom bowyer-watson)
8 #:export (make-voronoi-mesh
10 voronoi-mesh-triangles
16 "https://github.com/watabou/TownGeneratorOS/blob/master/Source/com/watabou/geom/Voronoi.hx"
18 ;;; Voronoi mesh region
20 (define-record-type <voronoi-region>
21 (make-voronoi-region seed vertices)
23 (seed voronoi-region-seed)
24 (vertices voronoi-region-vertices))
29 (define-record-type <voronoi-mesh>
30 (make-raw-voronoi-mesh triangles points frame regions)
32 (triangles voronoi-mesh-triangles)
33 (points voronoi-mesh-points)
34 (frame voronoi-mesh-frame)
35 (regions voronoi-mesh-regions))
37 (define* (make-voronoi-mesh vertices #:optional (relax-steps 3))
38 ; Delaunay triangulation
39 (receive (triangles points frame)
40 (bowyer-watson vertices)
41 (make-raw-voronoi-mesh
45 (make-regions points triangles))))
47 (define* (voronoi-mesh-relax voronoi #:optional (to-relax '()))
50 (define* (make-regions points triangles #:optional (regions '()))
54 (let* ((p (car points))
56 (lambda (tr) (member p (triangle-points tr)))
58 (region (make-voronoi-region p vertices)))
59 (make-regions (cdr points)
61 (alist-cons p region regions))))))