前言
这篇文章对Voronoi diagram相关第三方库介绍的比较详细:https://bbs.huaweicloud.com/blogs/detail/196128
最近了解了下Voronoi diagram的几何计算方法,记录一下。
一、维诺图是什么
Voronoi diagram 主要是对空间的一种剖分,在众多领域应用广泛,相关数学完备的定义见百度百科/wiki百科。原始图形可以有点、线段、圆弧、等有界曲线,在一些文章中被称为site。
二、相关文献
Voronoi diagram 的计算分为三类。第一类是近似计算,有格栅法、离散后使用delaunay三角剖分计算等方法,这类方法计算速度快,不求特别精确,常用在图形处理等方面。第二类是跟踪计算类(离散点微分),主要有追踪法(利用曲率等几何性质),这类算法主要是数值求解,目前在加工领域也有应用,适用性也比较好。第三类是精确计算类,有扫描线方法、分治法、增量法等,目前看到的库最多支持精确计算到圆弧(对于样条等其他曲线离散成圆弧或线段输入),这类算法计算精度高,但难以在复杂曲线上做推广。例如光添加圆弧进来就要处理所有二次曲线的求交问题,更遑论其他。
1.跟踪计算类
这里选取比较有代表性的,也是利用了较多几何性质的(中文作者也有博士论文,更方便阅读,在知网可以获取)。
2.精确计算类算法
分治计算,不支持圆弧。
增量算法,动态插入,逐步删除受影响的树枝。
这篇论文是商业库VRONI的指导论文,也有Held教授学生毕业论文版本(有更多的细节)。
线段和圆弧的作用域:
文章中的有些引理的证明还有jordan曲线,比较难读。