Need triangulation in haskell-CodePudding

I look for code to computer a triangulation (prefered Delaunay triangulation) in Haskell (oder callable from Haskell) or for a Voronoi diagram.

I have checked various packages I found with hackage, but they seem to be old and do not compile with current ghc (delaunay, triangulation) or not well documented that I cannot get them to compile (e.g. hgeometry).

What should I use? Any pointers would be appreciated!

I currently have with hgeometry:

qs :: [Point 2 (RealNumber 5)]
qs = [Point2  0 0, Point2  1 1, Point2  0 2, Point2  2 2]

qsne = fromList qs   
t1 = delaunayTriangulation qsne

and get the error I cannot understand:

Code/Lib/TryDelaunay.hs:65:28: error:
    • Couldn't match type ‘Point 2 (RealNumber 5)’
                     with ‘Point 2 r :  p’
      Expected type: NonEmpty (Point 2 r :  p)
        Actual type: NonEmpty (Point 2 (RealNumber 5))
    • In the first argument of ‘delaunayTriangulation’, namely ‘qsne’
      In the expression: delaunayTriangulation qsne
      In an equation for ‘t1’: t1 = delaunayTriangulation qsne
    • Relevant bindings include
        t1 :: Triangulation p r (bound at Code/Lib/TryDelaunay.hs:65:1)

CodePudding user response：

: is just a type for "annotated points". You can attach any data you like to each of the points, without affecting the triangulation. (You see that it doesn't affect it from the fact that the type variable p is completely unconstrained, i.e. the function has no way to take these values into account, it can only store them / reference them from the resulting data structure.)

If you don't want to add any annotations... well, you can always add an annotation that doesn't actually contain any information, by writing p : (). Or if you already have a (nonempty-) list qsne, you can use

  fmap (: ()) qsne

to make it conformant to delauneyTriangulation.

CodePudding user response：

I post here the full code and hope it helps others. It lists all the language extensions I found necessary and the imports required (with the dependencies). Suggestions for improvements are welcome!

-- -- Module : an example how to use the triangulation from hgeometry

-- dependencies:
--  - hgeometry 
--   - hgeometry-combinatorial
--   - linear
-- all language extensions are explicitely in the file

-----------------------------------------------------------------------------
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE TypeFamilies          #-}
{-# LANGUAGE TypeSynonymInstances  #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE TypeApplications     #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeOperators #-}

{-# OPTIONS_GHC -Wno-missing-signatures #-}

module Lib.TryDelaunay 
     where

import Data.Geometry ( Point(Point2) )  
import Algorithms.Geometry.DelaunayTriangulation.DivideAndConquer
    ( delaunayTriangulation )
import Data.Ext ( type (: )(..) )
import Data.List.NonEmpty ( NonEmpty, fromList )
import Algorithms.Geometry.DelaunayTriangulation.Types (toPlanarSubdivision)

qs :: [Point 2 Float :  Char]
qs = [(Point2  0 0) :  'a' , Point2  1.5 1.5 :  'b' , Point2  0 2  :  'c', Point2  2 0  :  'd']

-- qsne = fmap (: ()) $ fromList qs
qsne :: NonEmpty (Point 2 Float :  Char)
qsne =  fromList qs

t1 = delaunayTriangulation qsne 
g1 = toPlanarSubdivision t1
-- NonEmpty.fromList [4, 5]
-- p2 :: Point 2 Int
mainDel1:: IO ()
mainDel1 = do 
    print.unwords  $ ["qs", show qs]
    print.unwords  $  ["t1", show t1]