about summary refs log tree commit diff
diff options
context:
space:
mode:
authorGriffin Smith <root@gws.fyi>2020-01-19T18·19-0500
committerGriffin Smith <root@gws.fyi>2020-01-19T18·19-0500
commitd62aba218d1996b2c0541553c182313cfcc9843d (patch)
treeebef53895fc1d763420e7a099571e6868f10ba77
parentb6f170c02cb8231238ba0909fd311efc83b6bf69 (diff)
Switch to DelaunayTriangulation.Naive
Per https://github.com/noinia/hgeometry/issues/28, occasionally
DelaunayTriangulation.DivideAndConquer loops infinitely - in this case,
I was able to consistently use the seed 127624940715530481, to generate
a dungeon which had the following room centroids:

    [ Point2 [38.5,3.5] :+ 0
    , Point2 [67.0,33.0] :+ 1
    , Point2 [46.0,45.5] :+ 2
    , Point2 [55.5,42.0] :+ 3
    , Point2 [36.0,25.0] :+ 4
    , Point2 [76.5,12.0] :+ 5
    , Point2 [29.0,26.5] :+ 6
    , Point2 [55.0,10.5] :+ 7
    ]

and cause delaunay triangulation to loop indefinitely (or at least
longer than I cared to wait for). Given the size of our graphs switching
to naive generation should be fine performance-wise, and avoids the
infinite loop.
-rw-r--r--src/Xanthous/Util/Graphics.hs5
1 files changed, 4 insertions, 1 deletions
diff --git a/src/Xanthous/Util/Graphics.hs b/src/Xanthous/Util/Graphics.hs
index bd6a0906a6d5..fc704abf64fd 100644
--- a/src/Xanthous/Util/Graphics.hs
+++ b/src/Xanthous/Util/Graphics.hs
@@ -10,7 +10,10 @@ module Xanthous.Util.Graphics
 --------------------------------------------------------------------------------
 import           Xanthous.Prelude
 --------------------------------------------------------------------------------
-import qualified Algorithms.Geometry.DelaunayTriangulation.DivideAndConquer
+-- https://github.com/noinia/hgeometry/issues/28
+-- import qualified Algorithms.Geometry.DelaunayTriangulation.DivideAndConquer
+--               as Geometry
+import qualified Algorithms.Geometry.DelaunayTriangulation.Naive
               as Geometry
 import qualified Algorithms.Geometry.DelaunayTriangulation.Types as Geometry
 import           Codec.Picture (imagePixels)