X-Git-Url: https://git.jsancho.org/?p=dungeon-master.git;a=blobdiff_plain;f=modules%2Fdungeon-master%2Fgeom%2Fbowyer-watson.scm;fp=modules%2Fdungeon-master%2Fgeom%2Fbowyer-watson.scm;h=14455394d4b7c640c55dbc5865784c0278397754;hp=0000000000000000000000000000000000000000;hb=8f36ecdca1766ddd2a177fa46dc885c7f8e14130;hpb=4fce641cc077d18f972e250d2fe3be5067618127

diff --git a/modules/dungeon-master/geom/bowyer-watson.scm b/modules/dungeon-master/geom/bowyer-watson.scm
new file mode 100644
index 0000000..1445539
--- /dev/null
+++ b/modules/dungeon-master/geom/bowyer-watson.scm
@@ -0,0 +1,144 @@
+;;; Dungeon Master --- RPG Adventure Generator
+;;; Copyright © 2019 Javier Sancho <jsf@jsancho.org>
+;;;
+;;; Dungeon Master is free software; you can redistribute it and/or modify it
+;;; under the terms of the GNU General Public License as published by
+;;; the Free Software Foundation; either version 3 of the License, or
+;;; (at your option) any later version.
+;;;
+;;; Dungeon Master is distributed in the hope that it will be useful, but
+;;; WITHOUT ANY WARRANTY; without even the implied warranty of
+;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+;;; General Public License for more details.
+;;;
+;;; You should have received a copy of the GNU General Public License
+;;; along with Dungeon Master. If not, see <http://www.gnu.org/licenses/>.
+
+
+(define-module (dungeon-master geom bowyer-watson)
+  #:use-module (ice-9 receive)
+  #:use-module (srfi srfi-1)
+  #:use-module (srfi srfi-9)
+  #:use-module (dungeon-master geom point)
+  #:use-module (dungeon-master geom triangle)
+  #:export (bowyer-watson))
+
+"
+Compute the Delaunay triangulation using Bowyer–Watson algorithm
+https://en.wikipedia.org/wiki/Bowyer-Watson_algorithm
+"
+
+(define (bowyer-watson vertices)
+  (receive (minx miny maxx maxy)
+      (calculate-limits vertices)
+    (let ((c1 (make-point minx miny))
+          (c2 (make-point minx maxy))
+          (c3 (make-point maxx miny))
+          (c4 (make-point maxx maxy)))
+      (let ((frame (list c1 c2 c3 c4)))
+        (receive (points triangles)
+            (calculate-triangulation
+             (list c4 c3 c2 c1)
+             (list (make-triangle c1 c2 c3)
+                   (make-triangle c2 c3 c4))
+             vertices)
+          (values triangles points frame))))))
+
+(define (calculate-limits vertices)
+  (let ((xs (map (lambda (p) (point-x p)) vertices))
+        (ys (map (lambda (p) (point-y p)) vertices)))
+    (let ((minx (apply min (cons (expt 10 10) xs)))
+          (miny (apply min (cons (expt 10 10) ys)))
+          (maxx (apply max (cons (- (expt 10 9)) xs)))
+          (maxy (apply max (cons (- (expt 10 9)) ys))))
+      (let ((dx (* (- maxx minx) 0.5))
+            (dy (* (- maxy miny) 0.5)))
+        (values (- minx (/ dx 2))
+                (- miny (/ dy 2))
+                (+ maxx (/ dx 2))
+                (+ maxy (/ dy 2)))))))
+
+(define (calculate-triangulation points triangles vertices)
+  (cond ((null? vertices)
+         (values points triangles))
+        (else
+         (let ((vertice (car vertices)))
+           (receive (to-split to-keep)
+               (triangles-contains-point triangles vertice)
+             (cond ((null? to-split)
+                    (calculate-triangulation points triangles (cdr vertices)))
+                   (else
+                    (calculate-triangulation
+                     (cons vertice points)
+                     (concatenate
+                      (list (calculate-new-triangles to-split vertice)
+                            to-keep))
+                     (cdr vertices)))))))))
+
+(define (calculate-new-triangles to-split p1)
+  (receive (a b)
+      (calculate-new-edges to-split)
+    (let loop ((p2-list a)
+               (p3-list b)
+               (triangles '()))
+      (cond ((null? p2-list)
+             triangles)
+            (else
+             (let ((p2 (car p2-list))
+                   (p3 (car p3-list)))
+               (loop (cdr p2-list)
+                     (cdr p3-list)
+                     (cons (make-triangle p1 p2 p3) triangles))))))))
+
+(define* (calculate-new-edges triangles #:optional (original-t triangles) (a '()) (b '()))
+  (cond ((null? triangles)
+         (values a b))
+        (else
+         (let* ((triangle (car triangles))
+                (common-edge (triangles-has-common-edge triangle original-t)))
+           (let ((points (triangle-points triangle)))
+             (let ((p1 (car points))
+                   (p2 (cadr points))
+                   (p3 (caddr points))
+                   (e1 (car common-edge))
+                   (e2 (cadr common-edge))
+                   (e3 (caddr common-edge)))
+               (cond (e1
+                      (set! a (cons p1 a))
+                      (set! b (cons p2 b))))
+               (cond (e2
+                      (set! a (cons p2 a))
+                      (set! b (cons p3 b))))
+               (cond (e3
+                      (set! a (cons p3 a))
+                      (set! b (cons p1 b))))
+               (calculate-new-edges (cdr triangles) original-t a b)))))))
+
+(define* (triangles-has-common-edge triangle triangles #:optional (e1 #t) (e2 #t) (e3 #t))
+  (cond ((not (or e1 e2 e3))
+         (list e1 e2 e3))
+        ((null? triangles)
+         (list e1 e2 e3))
+        (else
+         (let ((t (car triangles)))
+           (cond ((equal? t triangle)
+                  (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3))
+                 (else
+                  (let ((points (triangle-points triangle)))
+                    (let ((p1 (car points))
+                          (p2 (cadr points))
+                          (p3 (caddr points)))
+                      (when (and e1 (triangle-has-edge t p2 p1))
+                        (set! e1 #f))
+                      (when (and e2 (triangle-has-edge t p3 p2))
+                        (set! e2 #f))
+                      (when (and e3 (triangle-has-edge t p1 p3))
+                        (set! e3 #f))))
+                  (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3)))))))
+
+(define (triangles-contains-point triangles point)
+  (partition
+   (lambda (triangle)
+     (< (points-distance point (triangle-center triangle))
+        (triangle-radius triangle)))
+   triangles))