+;;; 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)
voronoi-mesh-triangles
voronoi-mesh-points
voronoi-mesh-frame
- voronoi-mesh-regions))
+ 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-voronoi-region seed vertices)
+ (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?
(frame voronoi-mesh-frame)
(regions voronoi-mesh-regions))
-(define* (make-voronoi-mesh vertices #:optional (relax-steps 3))
- ; Delaunay triangulation
+(define (make-voronoi-mesh vertices)
+ ;; Delaunay triangulation
(receive (triangles points frame)
(bowyer-watson vertices)
- ; Relaxing central wards
- ;; (let relax ((step relax-steps))
- ;; (cond ((> step 0)
- ;; (relax (- step 1)))
- ;; (else
- ;; #t)))
(make-raw-voronoi-mesh
triangles
points
frame
(make-regions points triangles))))
-(define* (make-regions points triangles #:optional (regions '()))
- (cond ((null? points)
- regions)
- (else
- (let* ((p (car points))
- (vertices (filter
- (lambda (tr) (member p (triangle-points tr)))
- triangles)))
- (display p)(newline)
- (make-regions (cdr points)
- triangles
- (cons (make-voronoi-region p vertices) regions))))))
+(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))