1 ;;; Dungeon Master --- Adventure generator for GNU Guile
2 ;;; Copyright © 2019 Javier Sancho <jsf@jsancho.org>
4 ;;; Dungeon Master is free software; you can redistribute it and/or modify it
5 ;;; under the terms of the GNU General Public License as published by
6 ;;; the Free Software Foundation; either version 3 of the License, or
7 ;;; (at your option) any later version.
9 ;;; Dungeon Master is distributed in the hope that it will be useful, but
10 ;;; WITHOUT ANY WARRANTY; without even the implied warranty of
11 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ;;; General Public License for more details.
14 ;;; You should have received a copy of the GNU General Public License
15 ;;; along with Haunt. If not, see <http://www.gnu.org/licenses/>.
18 (define-module (dungeon-master geom voronoi)
19 #:use-module (ice-9 receive)
20 #:use-module (rnrs sorting)
21 #:use-module (srfi srfi-1)
22 #:use-module (srfi srfi-9)
23 #:use-module (dungeon-master geom)
24 #:use-module (dungeon-master geom point)
25 #:use-module (dungeon-master geom triangle)
26 #:use-module (dungeon-master geom bowyer-watson)
27 #:export (make-voronoi-mesh
29 voronoi-mesh-triangles
35 "https://github.com/watabou/TownGeneratorOS/blob/master/Source/com/watabou/geom/Voronoi.hx"
37 ;;; Voronoi mesh region
39 (define-record-type <voronoi-region>
40 (make-raw-voronoi-region seed vertices)
42 (seed voronoi-region-seed)
43 (vertices voronoi-region-vertices))
45 (define (make-voronoi-region seed vertices)
46 (define (compare-angles triangle1 triangle2)
47 (let ((c1 (triangle-center triangle1))
48 (c2 (triangle-center triangle2)))
49 (> (angle-sign seed c1 c2) 0)))
50 (make-raw-voronoi-region seed (list-sort compare-angles vertices)))
52 (define (voronoi-region-center region)
53 (let* ((vertices (voronoi-region-vertices region))
54 (centers (map (lambda (v) (triangle-center v)) vertices)))
56 (apply sum-points centers)
57 (/ 1 (length vertices)))))
62 (define-record-type <voronoi-mesh>
63 (make-raw-voronoi-mesh triangles points frame regions)
65 (triangles voronoi-mesh-triangles)
66 (points voronoi-mesh-points)
67 (frame voronoi-mesh-frame)
68 (regions voronoi-mesh-regions))
70 (define (make-voronoi-mesh vertices)
71 ;; Delaunay triangulation
72 (receive (triangles points frame)
73 (bowyer-watson vertices)
74 (make-raw-voronoi-mesh
78 (make-regions points triangles))))
80 (define (partitioning voronoi)
81 (define (is-real-triangle triangle)
82 ;; real triangle points cannot be frame points
83 (let ((frame (voronoi-mesh-frame voronoi)))
84 (let check-points ((points (triangle-points triangle)))
86 #t) ; triangle is real
88 (and (not (member (car points) frame))
89 (check-points (cdr points))))))))
91 (define (is-real-region region)
92 ;; real region points cannot be frame points
93 (let check-vertices ((vertices (voronoi-region-vertices region)))
94 (cond ((null? vertices)
97 (and (is-real-triangle (car vertices))
98 (check-vertices (cdr vertices)))))))
100 (let* ((points (voronoi-mesh-points voronoi))
101 (regions (voronoi-mesh-regions voronoi))
102 ;; we need the regions in the same order as points are
106 (assoc-ref regions p))
108 ;; only real regions without frame points
110 (filter (lambda (r) (is-real-region r))
114 (define* (voronoi-mesh-relax voronoi #:optional (points-to-relax '()))
117 (lambda (r) (cons (voronoi-region-seed r) (voronoi-region-center r)))
118 (partitioning voronoi)))
121 (lambda (p) (not (member p (voronoi-mesh-frame voronoi))))
122 (voronoi-mesh-points voronoi)))
124 (if (null? points-to-relax)
125 (voronoi-mesh-points voronoi)
130 (let ((center (assoc-ref regions point)))
131 (if (and center (member point to-relax))
136 (define (make-regions points triangles)
141 (lambda (tr) (member p (triangle-points tr)))
143 (cons p (make-voronoi-region p vertices))))