CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

======Delaunay三角剖分======
=====三角剖分=====
假设有平面点集 $V$,设 $e$ 表示 $V$ 中两点构成的线段，$E$ 是 $e$ 的集合，平面图 $G=(V,E)$ 是点集的三角剖分且 $G$ 满足下列条件:
  * 任意两条边除端点外不相交
  * 除端点外，边上没有点集中的点
  * 所有的面都是三角形，所有三角形的合集轮廓是 $V$ 的凸包。
=====Delaunay三角剖分=====
$Delaunay$ 三角剖分是一种特殊的三角剖分，对于 $Delaunay$ 三角剖分中任意三角形做外接圆，圆的范围内没有其他点
具体构造方法可以参考[[https://oi-wiki.org/geometry/triangulation/|OIWIKI]]
======Voronoi图======
考虑点集 $V$ 中任意两点连线的垂直平分线，显然垂直平分线两侧的点到连线相应端点的距离更近，中垂线上面的点到端点的距离相等。根据这个性质我们构造出 $Voronoi$ 图，对于点 $A$ 作出它和其他点连线的垂直平分线，从而构成封闭多边形（或者一部分），对于所有点进行相同的操作，即可得到 $Voronoi$ 图，$Voronoi$ 图中边到两侧源点（$V$ 中的点）的距离相等，而多边形内的点到对应源点的距离小于到其他源点的距离。

$Voronoi$ 图同时也是 $Delaunay$ 三角剖分的对偶图，可以先构造后者从而转换得到 $Voronoi$ 图。
======参考资料======
  * [[https://oi-wiki.org/geometry/triangulation/|OIWIKI]]
  * {{ :technique:王栋.ppt |}}

CVBB ACM Team

用户工具

站点工具

页面工具