计算几何..Basic but most useful
标题的意思不是说计算几何是basic but most useful, 是说我学到的几个算法是这样的. 每一次这样的标题下MS都是对CLRS的一次复述. 说句良心话, CLRS实在是一本好书, 一本大好书. 切入正题.
先说凸组合, 设点 p1, p2, p3. 若 p3 = x * p1 + ( 1 – x ) * p2 ( x, y 坐标对就相乘, 0<= x <= 1 ), 则称p3是p1-p2的凸组合. p1-p2 ( 包括p1和p2 ) 是全体p3. 矢量就不说了, 我自己也没完全弄懂它呢. 暂且理解为有向线段, 即有长度限制的射线.
叉积, 我完全是用一次函数推出来的, 它所算的有向面积, 我不明白原理, 或者它只是一个很本质的东西? 就像矩形的面积是长乘高般原始? 不知道, 这些以后再扩充吧. 我的主要目的是弄懂凸包. 三维空间中的一个向量, 这就更不用说了, 不知道.
相对原点p0, p1 和 p2 的叉积公式: p1 * p2 = ( x1 * y2 ) – ( x2 * y1 ) . 当叉积大于零,p1 在 p2 的顺时针方向, 当叉积小于零, p1 在 p2 的逆时针方向. 当它等于零, p0, p1, p2共线. 共线时, 可以用判断p2是否在p0-p1为对角线的矩形中的方法, 判断点是否在一条线段上. More »
Tags: 计算几何