Computational geometr 计算几何教程
计算几何教程 Computational Geometry
计算几何的恶心之处 代码长,难写。 需要讨论各种边界情況。后面所介绍的算 法,有些对于边界情况的处理很完美,不 需要再做讨论;有些则不然,需要自行处 理边界情况
计算几何的恶心之处 ▪ 代码长，难写。 ▪ 需要讨论各种边界情况。后面所介绍的算 法，有些对于边界情况的处理很完美，不 需要再做讨论；有些则不然，需要自行处 理边界情况
精度误差 计算几何问题中,很多时候需要繁杂的浮点运 算和三角函数运算,这样会产生人神共愤的精 度问题。 因此,我们采取以下措施尽量避兔精度误差 (其中ε是个小量,多取108) a=b分|a-b<e a<b台a-b<-E ■a<b台a-b<∈
精度误差 ▪ 计算几何问题中，很多时候需要繁杂的浮点运 算和三角函数运算，这样会产生人神共愤的精 度问题。 ▪ 因此，我们采取以下措施尽量避免精度误差 （其中ε是个小量，多取 10–8）： ▪ 𝑎 = 𝑏 ⇔ 𝑎 − 𝑏 < 𝜖 ▪ 𝑎 < 𝑏 ⇔ 𝑎 − 𝑏 < −𝜖 ▪ 𝑎 ≤ 𝑏 ⇔ 𝑎 − 𝑏 < 𝜖
一维矢量 2-Dimension vector
2-Dimension Vector 二维矢量
矢量 既有大小又有方向的量。 又称为向量。 大家初中都毕业了我就不多说了
矢量 ▪ 既有大小又有方向的量。 ▪ 又称为向量。 ▪ 大家初中都毕业了我就不多说了
矢量的表示 在n维空间下,矢量经常被表达为n个数 的元组a=(a1,a2,…,an) 在二维空间下则以(x,y)-对整数表示 在高等代数中,n维矢量一般表示为列矢 量的飛式(a1a2…an),即n×1的矩阵
矢量的表示 ▪ 在 n 维空间下，矢量经常被表达为 n 个数 的元组 𝒂 = (𝑎1, 𝑎2, … , 𝑎𝑛)。 ▪ 在二维空间下则以 (𝑥, 𝑦) 一对整数表示。 ▪ 在高等代数中，n 维矢量一般表示为列矢 量的形式 𝑎1 𝑎2 … 𝑎𝑛 𝑇，即 n×1 的矩阵
点积 两个n维矢量的点积是一个标量,有 (a1,a2,…,an)·(b1,b2,…,bhn)a1b1+ a2b2+…+ anno 由此,矢量的模(即长度)定义为|a a·a=Va 点积满足交换律
点积 ▪ 两个 n 维矢量的点积是一个标量，有 𝑎1, 𝑎2,… , 𝑎𝑛 ⋅ 𝑏1, 𝑏2,…, 𝑏𝑛 ≝ 𝑎1𝑏1 + 𝑎2𝑏2 + ⋯ + 𝑎𝑛𝑏𝑛。 ▪ 由此，矢量的模（即长度）定义为 𝒂 ≝ 𝒂 ⋅ 𝒂 = 𝒂2 。 ▪ 点积满足交换律
夹角 点积之另一定义为a·b=|a|b(cose,其 中为和b之夹角 ■如下图,n与b的点积的值实际上就是a的 模乘班在a上的投影的“模”,但是若其投 影与a方向相反则为负 b在a上的投影
夹角 ▪ 点积之另一定义为 𝒂 ⋅ 𝒃 = 𝒂 𝒃 cos𝜃，其 中 θ为 a和 b之夹角。 ▪ 如下图，a与 b的点积的值实际上就是 a的 模乘 b在 a上的投影的“模”，但是若其投 影与 a方向相反则为负
矢量的垂直 垂直的矢量有e=丌/2,即cos=0 所以4和b垂直定义为a·b=0
矢量的垂直 ▪ 垂直的矢量有 𝜃 = 𝜋Τ2，即 cos𝜃 = 0. ▪ 所以 a和 b垂直定义为 𝒂 ⋅ 𝒃 = 0
矢量的缩放 矢量江是与o同向的单位矢量,即模长是 1的矢量。 所以与a同向,但长度是-矢量,为l 而与a共线但方向相反,长度是矢量为
矢量的缩放 ▪ 矢量 𝒂 𝒂 是与 a同向的单位矢量，即模长是 1 的矢量。 ▪ 所以与 a同向，但长度是 l的矢量，为𝑙 𝒂 𝒂 。 ▪ 而与 a共线但方向相反，长度是 l的矢量为 − 𝑙 𝒂 𝒂