mods/default/voronoi.scm

   1 (define-module (dungeon-master geom voronoi)
   2   #:use-module (ice-9 receive)
   3   #:use-module (srfi srfi-1)
   4   #:use-module (srfi srfi-9)
   5   #:use-module (dungeon-master geom point)
   6   #:use-module (dungeon-master geom triangle)
   7   #:export (make-voronoi-mesh
   8             voronoi-mesh?
   9             voronoi-mesh-triangles
  10             voronoi-mesh-points
  11             voronoi-mesh-frame))
  12
  13 "https://github.com/watabou/TownGeneratorOS/blob/master/Source/com/watabou/geom/Voronoi.hx"
  14
  15 (define-record-type <voronoi-mesh>
  16   (make-raw-voronoi-mesh triangles points frame)
  17   voronoi-mesh?
  18   (triangles voronoi-mesh-triangles set-voronoi-mesh-triangles!)
  19   (points voronoi-mesh-points set-voronoi-mesh-points!)
  20   (frame voronoi-mesh-frame set-voronoi-mesh-frame!))
  21
  22 (define (make-voronoi-mesh vertices)
  23   (receive (minx miny maxx maxy)
  24       (calculate-mesh-limits vertices)
  25     (let ((c1 (make-point minx miny))
  26           (c2 (make-point minx maxy))
  27           (c3 (make-point maxx miny))
  28           (c4 (make-point maxx maxy)))
  29       (let ((frame (list c1 c2 c3 c4))
  30             (points (list c1 c2 c3 c4))
  31             (triangles (list (make-triangle c1 c2 c3)
  32                              (make-triangle c2 c3 c4))))
  33         '()))))
  34
  35 (define (calculate-mesh-limits vertices)
  36   (let ((xs (map (lambda (p) (point-x p)) vertices))
  37         (ys (map (lambda (p) (point-y p)) vertices)))
  38     (let ((minx (apply min (cons (expt 10 10) xs)))
  39           (miny (apply min (cons (expt 10 10) ys)))
  40           (maxx (apply max (cons (- (expt 10 9)) xs)))
  41           (maxy (apply max (cons (- (expt 10 9)) ys))))
  42       (let ((dx (* (- maxx minx) 0.5))
  43             (dy (* (- maxy miny) 0.5)))
  44         (values (- minx (/ dx 2))
  45                 (- miny (/ dy 2))
  46                 (+ maxx (/ dx 2))
  47                 (+ maxy (/ dy 2)))))))
  48
  49 (define (calculate-mesh points triangles vertices)
  50   (cond ((null? vertices)
  51          (values points triangles))
  52         (else
  53          (let ((vertice (car vertices)))
  54            (receive (to-split to-keep)
  55                (triangles-contains-point triangles vertice)
  56              (cond ((null? to-split)
  57                     (calculate-mesh points triangles (cdr vertices)))
  58                    (else
  59                     (calculate-mesh (cons vertice points)
  60                                     (concatenate (calculate-new-triangles to-split vertice)
  61                                                  to-keep)
  62                                     (cdr vertices)))))))))
  63
  64 (define (calculate-new-triangles to-split p1)
  65   (let ((vertices (calculate-new-vertices to-split)))
  66     (let* ((a (car vertices))
  67            (b (cadr vertices))
  68            (len (length a)))
  69       (let loop ((sublist-a a)
  70                  (triangles '()))
  71         (cond (sublist-a
  72                (let ((p2 (car sublist-a))
  73                      (p3 (list-ref b (- len (length sublist-a)))))
  74                  (loop (member p3 a)
  75                        (cons (make-triangle p1 p2 p3) triangles))))
  76               (else
  77                triangles))))))
  78
  79 (define* (calculate-new-vertices triangles #:optional (original-t triangles) (a '()) (b '()))
  80   (cond ((null? triangles)
  81          (list a b))
  82         (else
  83          (let* ((triangle (car triangles))
  84                 (common-edge (triangles-has-common-edge triangle original-t)))
  85            (let ((points (triangle-points triangle)))
  86              (let ((p1 (car points))
  87                    (p2 (cadr points))
  88                    (p3 (caddr points))
  89                    (e1 (car common-edge))
  90                    (e2 (cadr common-edge))
  91                    (e3 (caddr common-edge)))
  92                (cond (e1
  93                       (set! a (cons p1 a))
  94                       (set! b (cons p2 b))))
  95                (cond (e2
  96                       (set! a (cons p2 a))
  97                       (set! b (cons p3 b))))
  98                (cond (e3
  99                       (set! a (cons p3 a))
 100                       (set! b (cons p1 b))))
 101                (calculate-new-vertices (cdr triangles) original-t a b)))))))
 102
 103 (define* (triangles-has-common-edge triangle triangles #:optional (e1 #t) (e2 #t) (e3 #t))
 104   (cond ((not (or e1 e2 e3))
 105          (list e1 e2 e3))
 106         ((null? triangles)
 107          (list e1 e2 e3))
 108         (else
 109          (let ((t (car triangles)))
 110            (cond ((equal? t triangle)
 111                   (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3))
 112                  (else
 113                   (let ((points (triangle-points triangle)))
 114                     (let ((p1 (car points))
 115                           (p2 (cadr points))
 116                           (p3 (caddr points)))
 117                       (when (and e1 (triangle-has-edge t p2 p1))
 118                         (set! e1 #f))
 119                       (when (and e2 (triangle-has-edge t p3 p2))
 120                         (set! e2 #f))
 121                       (when (and e3 (triangle-has-edge t p1 p3))
 122                         (set! e3 #f))))
 123                   (triangles-has-common-edge triangle (cdr triangles) e1 e2 e3)))))))
 124
 125 (define (triangles-contains-point triangles point)
 126   (partition
 127    (lambda (triangle)
 128      (< (points-distance point (triangle-center triangle))
 129         (triangle-radius triangle)))
 130    triangles))