-;;; 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))