dungeon-master/geom/voronoi.scm

   1 ;;; Dungeon Master --- Adventure generator for GNU Guile
   2 ;;; Copyright © 2019 Javier Sancho <jsf@jsancho.org>
   3 ;;;
   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.
   8 ;;;
   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.
  13 ;;;
  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/>.
  16
  17
  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
  28             voronoi-mesh?
  29             voronoi-mesh-triangles
  30             voronoi-mesh-points
  31             voronoi-mesh-frame
  32             voronoi-mesh-regions
  33             voronoi-mesh-relax))
  34
  35 "https://github.com/watabou/TownGeneratorOS/blob/master/Source/com/watabou/geom/Voronoi.hx"
  36
  37 ;;; Voronoi mesh region
  38
  39 (define-record-type <voronoi-region>
  40   (make-raw-voronoi-region seed vertices)
  41   voronoi-region?
  42   (seed voronoi-region-seed)
  43   (vertices voronoi-region-vertices))
  44
  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)))
  51
  52 (define (voronoi-region-center region)
  53   (let* ((vertices (voronoi-region-vertices region))
  54          (centers (map (lambda (v) (triangle-center v)) vertices)))
  55     (scale-point
  56      (apply sum-points centers)
  57      (/ 1 (length vertices)))))
  58
  59
  60 ;;; Voronoi mesh
  61
  62 (define-record-type <voronoi-mesh>
  63   (make-raw-voronoi-mesh triangles points frame regions)
  64   voronoi-mesh?
  65   (triangles voronoi-mesh-triangles)
  66   (points voronoi-mesh-points)
  67   (frame voronoi-mesh-frame)
  68   (regions voronoi-mesh-regions))
  69
  70 (define (make-voronoi-mesh vertices)
  71   ;; Delaunay triangulation
  72   (receive (triangles points frame)
  73       (bowyer-watson vertices)
  74     (make-raw-voronoi-mesh
  75      triangles
  76      points
  77      frame
  78      (make-regions points triangles))))
  79
  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)))
  85         (cond ((null? points)
  86                #t)  ; triangle is real
  87               (else
  88                (and (not (member (car points) frame))
  89                     (check-points (cdr points))))))))
  90
  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)
  95              #t)  ; region is real
  96             (else
  97              (and (is-real-triangle (car vertices))
  98                   (check-vertices (cdr vertices)))))))
  99
 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
 103          (ordered-regions
 104           (map-in-order
 105            (lambda (p)
 106              (assoc-ref regions p))
 107            points))
 108          ;; only real regions without frame points
 109          (filtered-regions
 110           (filter (lambda (r) (is-real-region r))
 111                   ordered-regions)))
 112     filtered-regions))
 113
 114 (define* (voronoi-mesh-relax voronoi #:optional (points-to-relax '()))
 115   (let ((regions
 116          (map
 117           (lambda (r) (cons (voronoi-region-seed r) (voronoi-region-center r)))
 118           (partitioning voronoi)))
 119         (points
 120          (filter
 121           (lambda (p) (not (member p (voronoi-mesh-frame voronoi))))
 122           (voronoi-mesh-points voronoi)))
 123         (to-relax
 124          (if (null? points-to-relax)
 125              (voronoi-mesh-points voronoi)
 126              points-to-relax)))
 127     (make-voronoi-mesh
 128      (map
 129       (lambda (point)
 130         (let ((center (assoc-ref regions point)))
 131           (if (and center (member point to-relax))
 132               center
 133               point)))
 134       points))))
 135
 136 (define (make-regions points triangles)
 137   (map-in-order
 138    (lambda (p)
 139      (let ((vertices
 140             (filter
 141              (lambda (tr) (member p (triangle-points tr)))
 142              triangles)))
 143        (cons p (make-voronoi-region p vertices))))
 144    points))