计算几何的恶心之处 代码长,难写。 需要讨论各种边界情況。后面所介绍的算 法,有些对于边界情况的处理很完美,不 需要再做讨论;有些则不然,需要自行处 理边界情况
计算几何的恶心之处 ▪ 代码长,难写。 ▪ 需要讨论各种边界情况。后面所介绍的算 法,有些对于边界情况的处理很完美,不 需要再做讨论;有些则不然,需要自行处 理边界情况
精度误差 计算几何问题中,很多时候需要繁杂的浮点运 算和三角函数运算,这样会产生人神共愤的精 度问题。 因此,我们采取以下措施尽量避兔精度误差 (其中ε是个小量,多取108) a=b分|a-b<e a<b台a-b<-E ■a<b台a-b<∈
精度误差 ▪ 计算几何问题中,很多时候需要繁杂的浮点运 算和三角函数运算,这样会产生人神共愤的精 度问题。 ▪ 因此,我们采取以下措施尽量避免精度误差 (其中ε是个小量,多取 10–8): ▪ 𝑎 = 𝑏 ⇔ 𝑎 − 𝑏 < 𝜖 ▪ 𝑎 < 𝑏 ⇔ 𝑎 − 𝑏 < −𝜖 ▪ 𝑎 ≤ 𝑏 ⇔ 𝑎 − 𝑏 < 𝜖
矢量的表示 在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 。 ▪ 点积满足交换律