technique:delaunay_and_basic_voronoi
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
technique:delaunay_and_basic_voronoi [2021/07/12 18:16] bazoka13 创建 |
technique:delaunay_and_basic_voronoi [2021/07/12 21:09] (当前版本) bazoka13 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ======Delaunay三角剖分====== | ======Delaunay三角剖分====== | ||
| - | =====Vornoi图===== | + | =====三角剖分===== |
| + | 假设有平面点集 $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 |}} | ||
technique/delaunay_and_basic_voronoi.1626085002.txt.gz · 最后更改: 2021/07/12 18:16 由 bazoka13
