#:use-module (dungeon-master geom triangle)
#:export (bowyer-watson))
-"Compute the Delaunay triangulation using Bowyer–Watson algorithm"
+"
+Compute the Delaunay triangulation using Bowyer–Watson algorithm
+https://en.wikipedia.org/wiki/Bowyer-Watson_algorithm
+"
(define (bowyer-watson vertices)
(receive (minx miny maxx maxy)
voronoi-mesh?
voronoi-mesh-triangles
voronoi-mesh-points
- voronoi-mesh-frame))
+ voronoi-mesh-frame
+ voronoi-mesh-regions))
"https://github.com/watabou/TownGeneratorOS/blob/master/Source/com/watabou/geom/Voronoi.hx"
+(define-record-type <voronoi-region>
+ (make-voronoi-region seed vertices)
+ voronoi-region?
+ (seed voronoi-region-seed)
+ (vertices voronoi-region-vertices))
+
(define-record-type <voronoi-mesh>
- (make-raw-voronoi-mesh triangles points frame)
+ (make-raw-voronoi-mesh triangles points frame regions)
voronoi-mesh?
- (triangles voronoi-mesh-triangles set-voronoi-mesh-triangles!)
- (points voronoi-mesh-points set-voronoi-mesh-points!)
- (frame voronoi-mesh-frame set-voronoi-mesh-frame!))
+ (triangles voronoi-mesh-triangles)
+ (points voronoi-mesh-points)
+ (frame voronoi-mesh-frame)
+ (regions voronoi-mesh-regions))
-(define (make-voronoi-mesh vertices)
+(define* (make-voronoi-mesh vertices #:optional (relax-steps 3))
+ ; Delaunay triangulation
(receive (triangles points frame)
(bowyer-watson vertices)
- (make-raw-voronoi-mesh triangles points frame)))
+ ; 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))))))