dungeon-master/geom/bowyer-watson.scm

   1 ;;; Dungeon Master --- RPG Adventure Generator
   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 Dungeon Master. If not, see <http://www.gnu.org/licenses/>.
  16
  17
  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))
  25
  26 "
  27 Compute the Delaunay triangulation using Bowyer–Watson algorithm
  28 https://en.wikipedia.org/wiki/Bowyer-Watson_algorithm
  29 "
  30
  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
  41              (list c4 c3 c2 c1)
  42              (list (make-triangle c1 c2 c3)
  43                    (make-triangle c2 c3 c4))
  44              vertices)
  45           (values triangles points frame))))))
  46
  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))
  57                 (- miny (/ dy 2))
  58                 (+ maxx (/ dx 2))
  59                 (+ maxy (/ dy 2)))))))
  60
  61 (define (calculate-triangulation points triangles vertices)
  62   (cond ((null? vertices)
  63          (values points triangles))
  64         (else
  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)))
  70                    (else
  71                     (calculate-triangulation
  72                      (cons vertice points)
  73                      (concatenate
  74                       (list (calculate-new-triangles to-split vertice)
  75                             to-keep))
  76                      (cdr vertices)))))))))
  77
  78 (define (calculate-new-triangles to-split p1)
  79   (receive (a b)
  80       (calculate-new-edges to-split)
  81     (let loop ((p2-list a)
  82                (p3-list b)
  83                (triangles '()))
  84       (cond ((null? p2-list)
  85              triangles)
  86             (else
  87              (let ((p2 (car p2-list))
  88                    (p3 (car p3-list)))
  89                (loop (cdr p2-list)
  90                      (cdr p3-list)
  91                      (cons (make-triangle p1 p2 p3) triangles))))))))
  92
  93 (define* (calculate-new-edges triangles #:optional (original-t triangles) (a '()) (b '()))
  94   (cond ((null? triangles)
  95          (values a b))
  96         (else
  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))
 101                    (p2 (cadr points))
 102                    (p3 (caddr points))
 103                    (e1 (car common-edge))
 104                    (e2 (cadr common-edge))
 105                    (e3 (caddr common-edge)))
 106                (cond (e1
 107                       (set! a (cons p1 a))
 108                       (set! b (cons p2 b))))
 109                (cond (e2
 110                       (set! a (cons p2 a))
 111                       (set! b (cons p3 b))))
 112                (cond (e3
 113                       (set! a (cons p3 a))
 114                       (set! b (cons p1 b))))
 115                (calculate-new-edges (cdr triangles) original-t a b)))))))
 116
 117 (define* (triangles-has-common-edge triangle triangles #:optional (e1 #t) (e2 #t) (e3 #t))
 118   (cond ((not (or e1 e2 e3))
 119          (list e1 e2 e3))
 120         ((null? triangles)
 121          (list e1 e2 e3))
 122         (else
 123          (let ((t (car triangles)))
 124            (cond ((equal? t triangle)
 125                   (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3))
 126                  (else
 127                   (let ((points (triangle-points triangle)))
 128                     (let ((p1 (car points))
 129                           (p2 (cadr points))
 130                           (p3 (caddr points)))
 131                       (when (and e1 (triangle-has-edge t p2 p1))
 132                         (set! e1 #f))
 133                       (when (and e2 (triangle-has-edge t p3 p2))
 134                         (set! e2 #f))
 135                       (when (and e3 (triangle-has-edge t p1 p3))
 136                         (set! e3 #f))))
 137                   (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3)))))))
 138
 139 (define (triangles-contains-point triangles point)
 140   (partition
 141    (lambda (triangle)
 142      (< (points-distance point (triangle-center triangle))
 143         (triangle-radius triangle)))
 144    triangles))