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

diff --git a/modules/dungeon-master/geom/voronoi.scm b/modules/dungeon-master/geom/voronoi.scm
new file mode 100644
index 0000000..553beec
--- /dev/null
+++ b/modules/dungeon-master/geom/voronoi.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 voronoi)
+  #:use-module (ice-9 receive)
+  #:use-module (rnrs sorting)
+  #:use-module (srfi srfi-1)
+  #:use-module (srfi srfi-9)
+  #:use-module (dungeon-master geom)
+  #:use-module (dungeon-master geom point)
+  #:use-module (dungeon-master geom triangle)
+  #:use-module (dungeon-master geom bowyer-watson)
+  #:export (make-voronoi-mesh
+            voronoi-mesh?
+            voronoi-mesh-triangles
+            voronoi-mesh-points
+            voronoi-mesh-frame
+            voronoi-mesh-regions
+            voronoi-mesh-relax))
+
+"https://github.com/watabou/TownGeneratorOS/blob/master/Source/com/watabou/geom/Voronoi.hx"
+
+;;; Voronoi mesh region
+
+(define-record-type <voronoi-region>
+  (make-raw-voronoi-region seed vertices)
+  voronoi-region?
+  (seed voronoi-region-seed)
+  (vertices voronoi-region-vertices))
+
+(define (make-voronoi-region seed vertices)
+  (define (compare-angles triangle1 triangle2)
+    (let ((c1 (triangle-center triangle1))
+          (c2 (triangle-center triangle2)))
+      (> (angle-sign seed c1 c2) 0)))
+  (make-raw-voronoi-region seed (list-sort compare-angles vertices)))
+
+(define (voronoi-region-center region)
+  (let* ((vertices (voronoi-region-vertices region))
+         (centers (map (lambda (v) (triangle-center v)) vertices)))
+    (scale-point
+     (apply sum-points centers)
+     (/ 1 (length vertices)))))
+
+
+;;; Voronoi mesh
+
+(define-record-type <voronoi-mesh>
+  (make-raw-voronoi-mesh triangles points frame regions)
+  voronoi-mesh?
+  (triangles voronoi-mesh-triangles)
+  (points voronoi-mesh-points)
+  (frame voronoi-mesh-frame)
+  (regions voronoi-mesh-regions))
+
+(define (make-voronoi-mesh vertices)
+  ;; Delaunay triangulation
+  (receive (triangles points frame)
+      (bowyer-watson vertices)
+    (make-raw-voronoi-mesh
+     triangles
+     points
+     frame
+     (make-regions points triangles))))
+
+(define (partitioning voronoi)
+  (define (is-real-triangle triangle)
+    ;; real triangle points cannot be frame points
+    (let ((frame (voronoi-mesh-frame voronoi)))
+      (let check-points ((points (triangle-points triangle)))
+        (cond ((null? points)
+               #t)  ; triangle is real
+              (else
+               (and (not (member (car points) frame))
+                    (check-points (cdr points))))))))
+
+  (define (is-real-region region)
+    ;; real region points cannot be frame points
+    (let check-vertices ((vertices (voronoi-region-vertices region)))
+      (cond ((null? vertices)
+             #t)  ; region is real
+            (else
+             (and (is-real-triangle (car vertices))
+                  (check-vertices (cdr vertices)))))))
+
+  (let* ((points (voronoi-mesh-points voronoi))
+         (regions (voronoi-mesh-regions voronoi))
+         ;; we need the regions in the same order as points are
+         (ordered-regions
+          (map-in-order
+           (lambda (p)
+             (assoc-ref regions p))
+           points))
+         ;; only real regions without frame points
+         (filtered-regions
+          (filter (lambda (r) (is-real-region r))
+                  ordered-regions)))
+    filtered-regions))
+
+(define* (voronoi-mesh-relax voronoi #:optional (points-to-relax '()))
+  (let ((regions
+         (map
+          (lambda (r) (cons (voronoi-region-seed r) (voronoi-region-center r)))
+          (partitioning voronoi)))
+        (points
+         (filter
+          (lambda (p) (not (member p (voronoi-mesh-frame voronoi))))
+          (voronoi-mesh-points voronoi)))
+        (to-relax
+         (if (null? points-to-relax)
+             (voronoi-mesh-points voronoi)
+             points-to-relax)))
+    (make-voronoi-mesh
+     (map
+      (lambda (point)
+        (let ((center (assoc-ref regions point)))
+          (if (and center (member point to-relax))
+              center
+              point)))
+      points))))
+
+(define (make-regions points triangles)
+  (map-in-order
+   (lambda (p)
+     (let ((vertices
+            (filter
+             (lambda (tr) (member p (triangle-points tr)))
+             triangles)))
+       (cons p (make-voronoi-region p vertices))))
+   points))