1 ;;; Dungeon Master --- RPG Adventure Generator
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 Dungeon Master. If not, see <http://www.gnu.org/licenses/>.
18 (define-module (dungeon-master geom bowyer-watson)
19 #:use-module (ice-9 receive)
20 #:use-module (srfi srfi-1)
21 #:use-module (srfi srfi-9)
22 #:use-module (dungeon-master geom point)
23 #:use-module (dungeon-master geom triangle)
24 #:export (bowyer-watson))
27 Compute the Delaunay triangulation using Bowyer–Watson algorithm
28 https://en.wikipedia.org/wiki/Bowyer-Watson_algorithm
31 (define (bowyer-watson vertices)
32 (receive (minx miny maxx maxy)
33 (calculate-limits vertices)
34 (let ((c1 (make-point minx miny))
35 (c2 (make-point minx maxy))
36 (c3 (make-point maxx miny))
37 (c4 (make-point maxx maxy)))
38 (let ((frame (list c1 c2 c3 c4)))
39 (receive (points triangles)
40 (calculate-triangulation
42 (list (make-triangle c1 c2 c3)
43 (make-triangle c2 c3 c4))
45 (values triangles points frame))))))
47 (define (calculate-limits vertices)
48 (let ((xs (map (lambda (p) (point-x p)) vertices))
49 (ys (map (lambda (p) (point-y p)) vertices)))
50 (let ((minx (apply min (cons (expt 10 10) xs)))
51 (miny (apply min (cons (expt 10 10) ys)))
52 (maxx (apply max (cons (- (expt 10 9)) xs)))
53 (maxy (apply max (cons (- (expt 10 9)) ys))))
54 (let ((dx (* (- maxx minx) 0.5))
55 (dy (* (- maxy miny) 0.5)))
56 (values (- minx (/ dx 2))
59 (+ maxy (/ dy 2)))))))
61 (define (calculate-triangulation points triangles vertices)
62 (cond ((null? vertices)
63 (values points triangles))
65 (let ((vertice (car vertices)))
66 (receive (to-split to-keep)
67 (triangles-contains-point triangles vertice)
68 (cond ((null? to-split)
69 (calculate-triangulation points triangles (cdr vertices)))
71 (calculate-triangulation
74 (list (calculate-new-triangles to-split vertice)
76 (cdr vertices)))))))))
78 (define (calculate-new-triangles to-split p1)
80 (calculate-new-edges to-split)
81 (let loop ((p2-list a)
84 (cond ((null? p2-list)
87 (let ((p2 (car p2-list))
91 (cons (make-triangle p1 p2 p3) triangles))))))))
93 (define* (calculate-new-edges triangles #:optional (original-t triangles) (a '()) (b '()))
94 (cond ((null? triangles)
97 (let* ((triangle (car triangles))
98 (common-edge (triangles-has-common-edge triangle original-t)))
99 (let ((points (triangle-points triangle)))
100 (let ((p1 (car points))
103 (e1 (car common-edge))
104 (e2 (cadr common-edge))
105 (e3 (caddr common-edge)))
108 (set! b (cons p2 b))))
111 (set! b (cons p3 b))))
114 (set! b (cons p1 b))))
115 (calculate-new-edges (cdr triangles) original-t a b)))))))
117 (define* (triangles-has-common-edge triangle triangles #:optional (e1 #t) (e2 #t) (e3 #t))
118 (cond ((not (or e1 e2 e3))
123 (let ((t (car triangles)))
124 (cond ((equal? t triangle)
125 (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3))
127 (let ((points (triangle-points triangle)))
128 (let ((p1 (car points))
131 (when (and e1 (triangle-has-edge t p2 p1))
133 (when (and e2 (triangle-has-edge t p3 p2))
135 (when (and e3 (triangle-has-edge t p1 p3))
137 (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3)))))))
139 (define (triangles-contains-point triangles point)
142 (< (points-distance point (triangle-center triangle))
143 (triangle-radius triangle)))