Voronoi mesh (work in progress)

diff --git a/dungeon-master/generators/town.scm b/dungeon-master/generators/town.scm
index 745a6425544a5aee5c32e13499fae665f4652ba6..2f7013a14d0097ccb62b3f9ee811844108e6098e 100644 (file)
--- a/dungeon-master/generators/town.scm
+++ b/dungeon-master/generators/town.scm
@@ -31,4 +31,4 @@
   (let* ((sa (* (random:exp) 2 pi))
          (points (get-points (* 8 patches) sa))
          (voronoi (make-voronoi-mesh points)))
   (let* ((sa (* (random:exp) 2 pi))
          (points (get-points (* 8 patches) sa))
          (voronoi (make-voronoi-mesh points)))

-    voronoi))
+    (format #t "~a~%~%~a~%" (voronoi-mesh-frame voronoi) (voronoi-mesh-points voronoi))))

diff --git a/dungeon-master/geom/bowyer-watson.scm b/dungeon-master/geom/bowyer-watson.scm
index e8b9ea5a19998d9f53f0263a8751a143670b55a9..29bf07c0d0f39c58868f7ffd580df02fc328c6cc 100644 (file)
--- a/dungeon-master/geom/bowyer-watson.scm
+++ b/dungeon-master/geom/bowyer-watson.scm
@@ -6,7 +6,10 @@
   #:use-module (dungeon-master geom triangle)
   #:export (bowyer-watson))
 
   #: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)
 
 (define (bowyer-watson vertices)
   (receive (minx miny maxx maxy)

diff --git a/dungeon-master/geom/voronoi.scm b/dungeon-master/geom/voronoi.scm
index 7a9c457a4674308023f702a71666c9c1b6ae4e26..a748634dad75eb54580c26917b5b8bb900f05d05 100644 (file)
--- a/dungeon-master/geom/voronoi.scm
+++ b/dungeon-master/geom/voronoi.scm
@@ -9,18 +9,50 @@
             voronoi-mesh?
             voronoi-mesh-triangles
             voronoi-mesh-points
             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"
 
 
 "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>
 (define-record-type <voronoi-mesh>

-  (make-raw-voronoi-mesh triangles points frame)
+  (make-raw-voronoi-mesh triangles points frame regions)

   voronoi-mesh?
   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)
   (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))))))