technique:delaunay_and_basic_voronoi
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
technique:delaunay_and_basic_voronoi [2021/07/12 20:47] bazoka13 |
technique:delaunay_and_basic_voronoi [2021/07/12 21:09] (当前版本) bazoka13 |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| * 所有的面都是三角形，所有三角形的合集轮廓是 $V$ 的凸包。 | * 所有的面都是三角形，所有三角形的合集轮廓是 $V$ 的凸包。 | ||
| =====Delaunay三角剖分===== | =====Delaunay三角剖分===== | ||
| - | $Delaunay$ 三角剖分是一种特殊的三角剖分，对于 $Delaunay$ 三角剖分中任意三角形做外接圆 | + | $Delaunay$ 三角剖分是一种特殊的三角剖分，对于 $Delaunay$ 三角剖分中任意三角形做外接圆，圆的范围内没有其他点 |
| - | ======Vornoi图====== | + | 具体构造方法可以参考[[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.1626094061.txt.gz · 最后更改: 2021/07/12 20:47 由 bazoka13
