//: [Previous](@previous) // Xcode で Editor メニュー > Show Render Markup でお読みください //import UIKit import Foundation /*: # 中学３年の数学 */ /*: ## 相似 */ /*: ## 相似な図形 ここでは平面図形を考える ２つの平面図形が、一方をスケール(拡大または縮小)したとき、他方と合同となるとき、これらの図形は「相似」である */ /*: まず、２つの図形の一方が他方に対して「回転」していない、また始点もずれていないものと仮定する。 最初の座標を原点に並行移動し、最大２点間距離 𝑑 でスケールを正規化した２つの多角形のそれぞれ順にすべての座標が一致すれば、それらは相似である 座標列 𝑝(𝑖) = ((𝑥(𝑖) - 𝑥(0))/𝑑, (𝑦(𝑖) - 𝑦(0))/𝑑) が最初の座標を原点に並行移動し、スケールを正規化した図形となる 一方の多角形の 𝑖 番目の座標を 𝑝₁(𝑖)、他方の多角形の 𝑖 番目の座標を 𝑝₂(𝑖) とすると、 すべての 𝑖 について |𝑝₁(𝑖).𝑥 − 𝑝₂(𝑖).𝑥| = 0 かつ |𝑝₁(𝑖).𝑦 − 𝑝₂(𝑖).𝑦| = 0 のとき、 ２つの多角形が相似であれば、それぞれ順にすべての座標が一致する */ /*: 但し、これだと相似の図形であるのに始点が互いに異なる場合に合同にならない よって、他方の始点をずらした座標列すべてを調べる必要がある */ /*: この方法では、２つの図形の一方が他方に対して回転しているときに対応ができないので注意 */ /*: #### 計算機における浮動小数点の一致の判定 先の説明で、|𝑥₁ − 𝑥₂| = 0 などとあるが、計算機では、 return x1 == x2 などとはできない。それは、数値誤差があるからで、以下のように、ほぼ等しいという判定をしなくてはならない return fabs(x1 - x2) < 1e-10 // 十分小さい値 この十分小さい値も、問題によって経験的に決めていくしかない このことは 2_4 の「合同」のところでも説明した */ func fabs(_ v: (x: Double, y: Double)) -> Double { return sqrt(v.x*v.x + v.y*v.y) } func 最大２点間距離(座標列: [(x: Double, y: Double)]) -> Double { var ２点間距離 = 0.0 for i in 0..<座標列.count { for j in i..<座標列.count { ２点間距離 = Double.maximum(２点間距離, fabs((x: 座標列[i].x - 座標列[j].x, y: 座標列[i].x - 座標列[j].x))) } } return ２点間距離 } func 始点が等しく回転してない多角形が相似か(座標列A: [(x: Double, y: Double)], 座標列B: [(x: Double, y: Double)]) -> Bool { if 座標列A.count < 1 || 座標列B.count < 1 || 座標列A.count != 座標列B.count { return false } // ここでは２角形！(直線)も多角形と定義する var 座標列A = 座標列A.map({ (x: $0.x - 座標列A[0].x, y: $0.y - 座標列A[0].y) }) // 最初の座標を原点に並行移動 var 座標列B = 座標列B.map({ (x: $0.x - 座標列B[0].x, y: $0.y - 座標列B[0].y) }) // 同上 let 最大２点間距離A = 最大２点間距離(座標列: 座標列A) let 最大２点間距離B = 最大２点間距離(座標列: 座標列B) 座標列A = 座標列A.map({ (x: $0.x / 最大２点間距離A, y: $0.y / 最大２点間距離A) }) // 最初の座標を原点に並行移動 座標列B = 座標列B.map({ (x: $0.x / 最大２点間距離B, y: $0.y / 最大２点間距離B) }) // 同上 for i in 0..<座標列A.count { if fabs(座標列A[i].x - 座標列B[i].x) > 1e-14 || fabs(座標列A[i].y - 座標列B[i].y) > 1e-14 { return false } } return true } func 回転してない多角形が相似か(座標列A: [(x: Double, y: Double)], 座標列B: [(x: Double, y: Double)]) -> Bool { if 座標列A.count < 1 || 座標列B.count < 1 || 座標列A.count != 座標列B.count { return false } // ここでは２角形！(直線)も多角形と定義する #if false // rotated for i in 0..<座標列A.count { // 他方の始点をずらして調べる if 始点が等しく回転してない多角形が相似か(座標列A: 座標列A, 座標列B: 座標列B.rotated(at: i)) { return true } } #else // rotate for _ in 0..<座標列A.count { var 座標列B = 座標列B if 始点が等しく回転してない多角形が相似か(座標列A: 座標列A, 座標列B: 座標列B) { return true } 座標列B.rotate(at: 1) // 他方の始点をずらして調べる } #endif return false } /*: 任意の多角形のベクトル列を以下のルーチンで求めることにする これは、のちに「合同」や「相似」を求めるために使用する */ func 多角形のベクトル列(座標列: [(x: Double, y: Double)]) -> [(x: Double, y: Double)] { var ベクトル列 = [(x: Double, y: Double)]() for i in 1..<座標列.count { ベクトル列.append((x: 座標列[i].x - 座標列[i - 1].x, y: 座標列[i].y - 座標列[i - 1].y)) } ベクトル列.append((x: 座標列[0].x - 座標列[座標列.count - 1].x, y: 座標列[0].y - 座標列[座標列.count - 1].y)) return ベクトル列 } /*: ２つの多角形の一方をスケールして、それぞれ順にすべての線の移動方向が一致すれば、それらは相似である 座標 (𝑥₁, 𝑦₁) から座標 (𝑥₂, 𝑦₂) への一つの線の移動方向は、高校数学で習う「ベクトル」に相当する ベクトル (𝑥₂ − 𝑥₁, 𝑦₂ − 𝑦₁) = (𝑣.𝑥, 𝑣.𝑦) = 𝑣 とあらわす 一方の多角形の 𝑖 番目のベクトルを 𝑣₁(𝑖)、他方の多角形の 𝑖 番目のベクトルを 𝑣₂(𝑖) とすると、 それぞれ最初のベクトルの大きさ 𝑙₁ = |(𝑣₁(0).𝑥, 𝑣₁(0).𝑦)|, 𝑙₂ = |(𝑣₂(0).𝑥, 𝑣₂(0).𝑦)| ですべて正規化したものについて、 すべての 𝑖 について |𝑣₁(𝑖).𝑥 − 𝑣₂(𝑖).𝑥|/𝑙₁ = 0 かつ |𝑣₁(𝑖).𝑦 − 𝑣₂(𝑖).𝑦|/𝑙₂ = 0 のとき、 ２つの多角形が相似であれば、それぞれ順にすべての線の移動方向が一致する 但しここで、ベクトルの絶対値は以下のように定義する 𝑙 = |𝑣| = |(𝑣.𝑥, 𝑣.𝑦)| = √{𝑣.𝑥² + 𝑣.𝑦²} 先の、最大２点間距離でスケールを正規化したものは、それを検索するために 𝑂(𝑛²) の計算量が掛かる。一方で、ベクトルの方法ではその手間が掛からない。 */ /*: 但し、これだと相似の図形であるのに始点が互いに異なる場合に合同にならない よって、他方の始点をずらした座標列すべてを調べる必要がある */ /*: この方法では、２つの図形の一方が他方に対して回転しているときに対応ができないので注意 */ extension Array { func rotated(at: Int) -> Array { // この配列を添字 at を先頭に「回転」したものを返す var r = self guard at < count else { return r } for i in 0.. Bool { if 座標列A.count < 1 || 座標列B.count < 1 || 座標列A.count != 座標列B.count { return false } // ここでは２角形！(直線)も多角形と定義する var ベクトル列A = 多角形のベクトル列(座標列: 座標列A) var ベクトル列B = 多角形のベクトル列(座標列: 座標列B) let 最初のベクトルA = ベクトル列A.first! let 最初のベクトルB = ベクトル列B.first! let 最初のベクトルAの長さ = sqrt(最初のベクトルA.x*最初のベクトルA.x + 最初のベクトルA.y*最初のベクトルA.y) let 最初のベクトルBの長さ = sqrt(最初のベクトルB.x*最初のベクトルB.x + 最初のベクトルB.y*最初のベクトルB.y) ベクトル列A = ベクトル列A.map({ (x: $0.x/最初のベクトルAの長さ, y: $0.y/最初のベクトルAの長さ) }) ベクトル列B = ベクトル列B.map({ (x: $0.x/最初のベクトルBの長さ, y: $0.y/最初のベクトルBの長さ) }) for i in 0..<ベクトル列A.count { if fabs(ベクトル列A[i].x - ベクトル列B[i].x) > 1e-14 || fabs(ベクトル列A[i].y - ベクトル列B[i].y) > 1e-14 { return false } } return true } func 回転してない多角形が相似か（ベクトル版）(座標列A: [(x: Double, y: Double)], 座標列B: [(x: Double, y: Double)]) -> Bool { if 座標列A.count < 1 || 座標列B.count < 1 || 座標列A.count != 座標列B.count { return false } // ここでは２角形！(直線)も多角形と定義する #if false // rotated for i in 0..<座標列A.count { if 始点が等しい回転してない多角形が相似か（ベクトル版）(座標列A: 座標列A, 座標列B: 座標列B.rotated(at: i)) { return true } } #else // rotate var 座標列B = 座標列B for _ in 0..<座標列A.count { if 始点が等しい回転してない多角形が相似か（ベクトル版）(座標列A: 座標列A, 座標列B: 座標列B) { return true } 座標列B.rotate(at: 1) } #endif return false } /*: ２つの多角形のそれぞれ順に２辺の角度が一致すれば、それらは相似である 座標 (𝑥₁, 𝑦₁) から座標 (𝑥₂, 𝑦₂) への一つの線の移動方向は、高校数学で習う「ベクトル」に相当する ベクトル (𝑥₂ − 𝑥₁, 𝑦₂ − 𝑦₁) = (𝑣.𝑥, 𝑣.𝑦) = 𝑣 とあらわす 一方の多角形の 𝑖 番目のベクトルを 𝑣₁(𝑖)、他方の多角形の 𝑖 番目のベクトルを 𝑣₂(𝑖) とすると、 すべての 𝑖 について、 𝜃₁(𝑖) − 𝜃₂(𝑖) = 0 のとき、 ２つの多角形が相似であれば、それぞれ順にすべての角度が一致する 但しここで、 𝜃₁ = tan^{−1}((𝑣₁(𝑖).𝑥⋅𝑣₁(𝑖−1).𝑦 − 𝑣₁(𝑖−1).𝑥⋅𝑣₁(𝑖).𝑦)/(𝑣₁(𝑖).𝑥⋅𝑣₁(𝑖−1).𝑥 + 𝑣₁(𝑖).𝑥⋅𝑣₁(𝑖−1).𝑥)) 𝜃₂ = tan^{−1}((𝑣₂(𝑖).𝑥⋅𝑣₂(𝑖−1).𝑦 − 𝑣₂(𝑖−1).𝑥⋅𝑣₂(𝑖).𝑦)/(𝑣₂(𝑖).𝑥⋅𝑣₂(𝑖−1).𝑥 + 𝑣₂(𝑖).𝑥⋅𝑣₂(𝑖−1).𝑥)) であるのは、高校数学で習う。 */ func 始点が等しい多角形が相似か(座標列A: [(x: Double, y: Double)], 座標列B: [(x: Double, y: Double)]) -> Bool { if 座標列A.count < 1 || 座標列B.count < 1 || 座標列A.count != 座標列B.count { return false } // ここでは２角形！(直線)も多角形と定義する let ベクトル列A = 多角形のベクトル列(座標列: 座標列A) let ベクトル列B = 多角形のベクトル列(座標列: 座標列B) for i in 1..<ベクトル列A.count { let 角度A = atan2(ベクトル列A[i].x * ベクトル列A[i-1].y - ベクトル列A[i-1].x * ベクトル列A[i].y, ベクトル列A[i].x * ベクトル列A[i].x + ベクトル列A[i-1].y * ベクトル列A[i-1].y) let 角度B = atan2(ベクトル列B[i].x * ベクトル列B[i-1].y - ベクトル列B[i-1].x * ベクトル列B[i].y, ベクトル列B[i].x * ベクトル列B[i].x + ベクトル列B[i-1].y * ベクトル列B[i-1].y) if fabs(角度A - 角度B) > 1e-13 { return false } } return true } func 多角形が相似か(座標列A: [(x: Double, y: Double)], 座標列B: [(x: Double, y: Double)]) -> Bool { if 座標列A.count < 1 || 座標列B.count < 1 || 座標列A.count != 座標列B.count { return false } // ここでは２角形！(直線)も多角形と定義する #if false // rotated for i in 0..<座標列A.count { if 始点が等しい多角形が相似か(座標列A: 座標列A, 座標列B: 座標列B.rotated(at: i)) { return true } } #else // rotate var 座標列B = 座標列B for _ in 0..<座標列A.count { if 始点が等しい多角形が相似か(座標列A: 座標列A, 座標列B: 座標列B) { return true } 座標列B.rotate(at: 1) } #endif return false } /*: #### 正多角形の座標 𝑛角形の正多角形の座標𝑖は、高校数学で習う sin, cos を用いて、以下のように表せられる 𝑥 = sin(2𝜋𝑖/𝑛), 𝑦 = −cos(2𝜋𝑖/𝑛) */ for n in [ 3, 4, 5, 6, 7, 8, 9, 10, 100, ] { // 正多角形の面積 var 形A = [(x: Double, y: Double)]() #if false // 座標 #elseif false // ベクトル #else // 角度 var 形B = [(x: Double, y: Double)]() #endif var 形C = [(x: Double, y: Double)]() var 形D = [(x: Double, y: Double)]() var 形E = [(x: Double, y: Double)]() for i in 0..