Haskell下Delaunay三角剖分/Voronoi图选型及hgeometry报错咨询

hgeometry测试代码报错原因 #

你遇到的类型不匹配错误，本质是hgeometry的几何实体设计要求所有输入点必须挂载额外元数据：delaunayTriangulation函数的入参类型是NonEmpty (Point 2 r :+ p)，其中:+是hgeometry内置的「几何实体+附加数据」构造器，你传入的裸Point 2 (RealNumber 5)类型没有附带元数据，因此无法通过类型检查。

不需要附加数据时，给每个点挂载空元组()即可通过编译，修正后的代码如下：

import Data.List.NonEmpty (fromList)
import HGeometry.Point
import HGeometry.Number.Real.Rational (RealNumber)
import HGeometry.Triangulation.Delaunay (delaunayTriangulation)
import HGeometry.Triangulation (Triangulation)

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

qsne = fromList qs
t1 = delaunayTriangulation qsne :: Triangulation () (RealNumber 5)

如果之前hgeometry编译失败，优先检查GHC版本与依赖版本的匹配性：当前hgeometry最新版本对GHC 9.2、9.4、9.6均有官方适配，不要手动松散指定依赖版本，用Stack对应LTS快照的预装版本即可正常编译。hgeometry本身也内置Voronoi图实现，可通过Delaunay三角剖分结果直接做对偶转换得到。

其他可用实现方案 #

• 绑定工业级C/C++计算几何库
  适合点规模大、对性能/功能完整性要求高的场景：
  • 可使用triangle绑定包：基于经典的Triangle二维三角剖分库实现，支持约束Delaunay、质量网格生成，包版本更新及时，对新GHC兼容性好，接口简单，没有复杂的类型级语法，上手成本低
  • 可使用CGAL绑定包：基于计算几何标准库CGAL实现，支持任意维度的Delaunay三角剖分、Voronoi图，功能覆盖最全，缺点是需要本地预装CGAL开发环境，编译产物体积较大
• 轻量纯Haskell实现
  适合点规模在数千以内、不想引入外部C依赖的场景：可使用delaunay-triangulation包，该包近年持续维护，支持GHC 9以上版本，代码结构简单，没有复杂类型编程，上手门槛远低于hgeometry，缺点是功能偏基础，不支持约束三角剖分，Voronoi图需要自行基于Delaunay结果做对偶转换。

内容的提问来源于stack exchange，提问作者user855443