文档介绍：COMPUTATIONAL GEOMETRY for R-MESH
by 王宇旸& 胡楠
1
用R-MESH实现计算几何学的算法
计算几何学
抽象的几何问题
大量的点构成,计算量大
理解算法的重点是其几何意义
凸壳(凸包)
Voronoi图
2
一个凸多边形相关的问题
Convexity
Inclusion
Supporting lines
Stabbing
3
Convexity
判定一个多边形是否凸多边形
引理:X轴正方向和边之间的夹角是否单调
4
Convexity数据结构
对于多边行N个顶点的集合D,取平面最右边且y坐标最小的点为起点,按照顺时针方向排成序列
R-Mesh
N个顶点按照行主序排列
5
Convexity过程
和相邻顶点形成一条边,计算边和x轴夹角,值保存在当前处理器上
和相邻处理器比较夹角大小,如果小于后一个标记为1,否则为0
所有的节点AND
6
Inclusion
内部:被判断点是否被所有的边包裹
被判断点在有向边的同侧
定义:有向边的内侧
数据结构和算法与Convexity类似
7
凸壳
概念:包含平面上所有点的最小面积的多边形
支撑线(切线)
8
凸壳解法思想:分治
计算点的子集的上壳
计算相邻子集的支撑线
合并
9
分治: 点的上壳算法
找四个角点
角点必然属于凸壳
哪些点不可能属于凸壳?
10