清华大学-计算几何-点集三角化
1、Point Set Triangulation
目标：对一系列的点进行三角化(网格化)
当我们有一系列点集时，我们需要对这些点集数据进行结构化。对点集进行结构化的一个重要的方法就是对这些点进行三角化。
这里的对角线分为两类，如上图所示，深绿色的外面的边对应于原来的凸包，另外一些内部的浅绿色的线则是凸包的内对角线。
所谓的点集的三角化，其实就是对这个点集所对应的凸包的区域进行剖分。
对于点集的三角化并不唯一
如果一个点集的点数目是n，如果凸包的size记做h，那么任意一个极大的对角线的集合都是由3(n-1)-h条对角线组成；这些对角线剖分出来的三角形的数目为2(n-1)-h。
每新增一个点，大致就增加三条对角线，两个三角形。
边翻转（Edge Flipping）：如上面不唯一的剖分所示，从左边的竖着的那条红色的内对角线变成右边横着的内对角线的这个操作称作边翻转。每进行一次边翻转就会得到一个不同的剖分方案。
剖分算法的界
如图所示，若我们已经有两个做好剖分的子集，那么根据第一章凸包算法找上下边界的Zigzag方法，我们就可以得到两个子集连接后的三角化，时间复杂度为O( ...
清华大学-计算几何-维诺图
本周目标：对空间进行剖分，然后对这个几何体进行探究。
Voronoi图（维诺图）
1、Terminologies
几个概念
基点Site：具有一些几何意义的点
细胞Cell：这个Cell中的任何一个点到Cell中基点中的距离都是最近的，离其他Site比离内部Site的距离都要远。
Cell的划分：基点Site与其它的n-1个点所对应的那个平分线所确定的那个离它更近的那个半平面。把所有这些半平面公共的交集求出来就是这个cell.
因此每个Cell都是凸的，图中一定会有一些Cell是无界的
在本课程中只讨论二维平面上的Voronoi图，并且我们存储Voronoi图时只需要存储点和边界信息。
Voronoi图中包括Voronoi点（线段与线段之间的交点）、线段Segment、射线Ray或直线，这些线都被称为Voronoi edge。
2、Properties
（1）非空性：每个Site都拥有一个非空的Site
（2）空圆性：在任何一个Site所对应的Cell中，任何一个点以这个点为圆心，以到这个Site的距离为半径的圆必然是空的。
这里的空指的是：圆其中它的内部不包含任何的Si ...
清华大学-计算几何-多边形三角剖分
目标：将多边形剖分成三角形
1、画廊问题
问题描述：在画廊（如下图的多边形）中，如何设置哨兵可以监控整个画廊？
画廊，其中的点为哨兵
直观解：如果多边形是凸多边形或星形多边形，那么只须在中间的核设置一个即可。如果多边形不规则，那么最多n个点，即n多边形的每个顶点都设置一个哨兵，就可以将整个多边形覆盖。因此问题的解的上界为n.
然而在数学上有证明指出画廊问题是NP-Hard问题，这里不做多的赘述。
实际上，对于不规则多边形而言，最对只须n/3个点即可覆盖多边形（如下图）。
锯齿形，需要最多的哨兵。因为每三个顶点构成的三角形一定需要一个哨兵。
2、Fisk’s Proof
几个概念
扇形：一个有核点的星形多边形。每个扇形可以由一个点覆盖整个扇形。
内对角线：多边形顶点之间的内部连线
切线：某个点相切。任意一个边或切线都不是对角线
对角线的集合是连续的如果任意两条对角线不相交。
上：内对角线 下：切线
三角剖分问题
多边形P的最大的连续对角线的集合称为P的三角剖分。
着色：任意一条边和内对角线连接的两个点颜色互异。
顶点着色
Fisk’s的证明指出：对于进行三角剖分后 ...
清华大学-计算几何-几何求交
目标：对一系列的几何体，判断它们是否有交集，计算它们交集的个数，枚举所有的交集，构建这些交。
1、Preliminary
EU问题
问题描述：给定一系列的实数，判断是否互异。
算法：将他们排序，然后可以通过线性扫描找到。复杂度O(nlogn)
Minimum Gap：对于实轴上的n个点，找到相邻两个的最小距离
对于这个问题，我们可以利用EU问题来规约，两个问题的输入都是n个整数，Minimum Gap如果是正数，那么EU的输出为Yes，如果是0，EU的输出是No。因此Minimum Gap的下界也是O(nlogn)
Maximum Gap：
算法描述：先找到最小值lo,和最大值hi，然后将这段分成n-1段，然后对每一个元素进行整除放进桶里。接着做线性扫描，先除去那些空桶。对于前面的桶考虑最右元素和后面桶的最左元素。考虑这两者然后找到最大的缝隙。
Integer Element Uniqueness：EU问题中的元素全都为整数
2、Interval Intersection Detection：区间交问题
问题描述：给定一系列数轴上的区间，判断它们是否有交
简单算法 ...
慢煮生活
6d63b89221e13b3febb0d4b727fe1cb7b9a5d0e0ce86e70d76eba31de419c45e
其实我很会吃。需要密钥
志愿活动
17289f4fd8cc2af956ca06fbbcbbc3ceee270d23331ae046282c79f19ce763204679d39279cf7a5be5a57e187d813b6f
这篇文章记录我在大学期间参加的各个社团与志愿活动、青协活动等经历，需要密钥。
荣誉记录
121020c51dd2a6d451cd928e21400bc4a2f9ccf110435a8cd7adb67156c7f1a7c8c348b94b66e7a7ec707c6d3ce260b84aff699ae2671f349f069d6b8615be2f3d7b45b2685f964739481bf22e411d9e47c19657d8ff99b6754a290ab3222c5722cfefff7e53e2e7328f63611d8fa5b1c65420a9dcab704d018fe5e921a1c3caf7f768621a7932b089a3dd01a96cdf99143fea4ba0863796bd95b8a12a42342202d6876dab74c138ee8193ca2c84b1fadf6b39aea7f59f18cfa9e5be76e5fcd52eb3ddb6560970e020d77bc192eb7754cd1c8f1eb51028a36a2a242d2ed17440f2a6475d15a902603e73bbea6324f43df1330a191cc5f56d9 ...
教育经历
6d63b89221e13b3febb0d4b727fe1cb7b9a5d0e0ce86e70d76eba31de419c45e
我的教育经历与毕业照片。需要密钥
游泳健身
85d85000c6eae48376b9559cb0794201e1e933e326fefcf6e98bac5473f00347
这篇文章记录我的运动、健身活动与打卡记录。需要密钥
清华大学-计算几何-凸包
1、凸性(Convexity)
以颜色为例
假设x,y,z是三种颜色，如果仅以x,y就能调出来的颜色，那么如u所示它一定会落在x,y中；若需要x,y,z三种 一起，那么如v所示会落在以x,y,z三点连成的三角形内部。
2、极点(Extreme Point)
在一组点中，沿着这个点作直线，必然能找到一条直线，使得其他所有点都在该直线的一侧。
判断一个点是否为极点：看该点是否存在于其中的三个点围成的三角形的内部
s点就不是极点
To-Left Test：判断一个点是否存在于三个点围成的三角形内部，那么就对该三个点以逆时针方向两两连成有向边，如果该点在这三条直线的左侧，那么成立。（复杂度为O(n^4)）
123456bool InTriangle(Point p, Point q, Point r, Point s) { bool pqLeft = ToLeft(p, q, s); bool qrLeft = ToLeft(q, r, s); bool rpLeft = ToLeft(r, p, s); return (pdLeft == qrLeft) ...