三角測距
三角形分割
【英】：triangulation
概要
点集合の三角形分割とは, 2次元においてはその凸包を2-単体すなわち三角形に, 3次元では3--単体すなわち四面体に分割することである(四面体分割ともいう). 一般の次元の場合は単体分割あるいは簡単に三角形分割といわれる. 三角形分割は, 凸包・凸多面体とならんで基本的な幾何構造であり, 理論的に重要であるだけでなく, コンピュータグラフィクスや有限要素解析・内挿で のメッシュ生成など広く応用がある.
詳説
点集合の三角形分割(triangulation)とは, 2次元においてはその凸包を2-単体 すなわち三角形に, 3次元では3-単体すなわち四面体に分割した構造である(四面体分割ともいう). 一般の次元の場合は単体分割あるいは簡単に三角形分割といわれる. 三角形分割は, 凸包・凸多面体とならんで基本的な幾何構造であり, 理論的に 重要であるだけでなく, コンピューターグラフィクスや有限要素解析・内挿でのメッシュ生成など広く応用がある.
を
次元の
点の集合, 
を
の凸包とする. の三角形分割
と は, 次の条件を満たすものである.
平面上の一般の位置にある点集合との点をすべて用いる三角形分割を考える. のどの三角形分割も, オイラー(L. Euler)の公式から同じ数の三角形をもつ. また, 三角形分割の個数については, 三角形分割の平面性に着目して解析することにより 
であることがいえる. 凸角形の頂点の場合は, 三角形分割の個数は
である. 動的計画法を用いることにより, 多角形内部の三角形分割の数を数える ことは多項式時間で行えるが, 一般の点集合の三角形分割の個数を多項式時間 で数えることができるかどうかは未解決の問題である. 多数の三角形分割の中から1つ選ぶ際の基準として代表的なものを上げる.
他にも色々な評価規準が考えられる. 以下で述べるドロネー三角形分割は, このうち最小角最大, 最大包含円最小という性質を満たし(最大外接円最小も), かつ
の高速の時間で求めることができる. 最大角を最小にする
)時間の動的計画法を用いたアルゴリズム も知られている. 一方, 辺長和を最小にする重み最小三角形分割 問題の複雑さについてはまだよくわかっていないが, 2次元の場合は解法が与えられている. 点集合が凸角形の頂点集合の場合, 辺長和最小問題は動的計画法によって 
時間で解ける. アスベクト比最適化なども含めた整数計画によるアプローチも はかられている.
三角形分割を応用上も役立つものにしているのは, ドロネー三角形分割あるいはドロネー図である. これはボロノイ図の双対グラフとして定義される. ここでは, アルゴリズム的にも 有用な定義を与えておく. 2次元の点
に対して, 新たに
軸を考え, 3次元の点
を対応させる. このとき, 
の3次元の凸包の軸に関する下側境界 を
平面に正射影したものを, 
のドロネー図 と定める.
ドロネー三角形分割は, 各三角形の外接円が他の点を内部に含まない三角形分割 として特徴づけられる. ドロネー三角形分割でないと, 点集合の中で凸四角形 
の三角形分割で, その三角形の外接円が他の点を含んでいる ものが存在する. このとき使っている対角線をもう1つの対角線に取り換えると, 局 所的に外接円に残りの1つの点は入らなくなる. 対角線を入れ換えることを対角変形といい, このように局所的にドロネー図に近付ける方向をドロネー対角変形と いう. 2次元では任意の三角形分割から
回ドロネー対角変形を行なう ことで, 必ずドロネー三角形分割に変換できる.
ドロネー三角形分割は, 上述のような様々な最適化基準を満たすが, その多く はこのドロネー対角変形によりその基準が改善されるという論法で証明され る. その場合, 最小角最大を例にすると, 全ての角度を小さい順に並べたベク トルについて, ドロネー三角形分割は辞書式順序で最大なベクトルを与えることも示すことができる.
三角形分割を2変数関数
の内挿関数
に適用した際, 曲面の三角形パッチによる近似の粗さの度合を ![\textstyle {\sum}_{S_i\in\tau}\int_{S_i}
\left[
\left(\partial g/\partial x\right)^2+
\left(\partial g/\partial y\right)^2
\right]{\rm d}x{\rm d}y
\,](http://weblio.hs.llnwd.net/e7/img/dict/orjtn/a19ec67f5c68c914f17b2c2a759469ee.png)
で定義すると, ドロネー対角変形は粗さ度を改善し, 最適性が導かれる. 最大最小包含円最小性は, 放物線のポテンシャル関数の性質によっている.
高次元の三角形分割の構造は一般に難しい. 三角形(単体)の個数も一定ではなく, 一般化された高次元対角変形により任意の三角形分割間で変換できるかどうかもわかっ ていない. 3次元で, 非凸の多面体の内部を新しい点を導入することなく四面体に分割することができるかどうかという問題は, NP困難である.
高次元三角形分割の性質のよい有用な部分クラスとして, 正則三角形分割(regular triangulation)がある. これは, 点集合に対して新たなもう1次元方向を考え, その方向に各点に高さを与え, その分だけ新しい次元方向に持ち上げた点集合の凸包の下側境界を元の空間に正射影することにより得られるものである. もし, その凸包の下側境界にすべてのもち上げられた点がのっており, さらにそれらが一般の位置にあれば, 正射影されたものはまさしくこれまでの定義の三角形分割である. 正則三角形分割では与えられた点で三角形分割の頂点として使われないものもある. 2次元でも正則でない三角形分割は存在する.
ドロネー三角形分割は正則であり, 正則三角形分割は高次元の場合も任意の2つの正則三角形分割は一般化対角変形で変換することができ, 2次元の三角形分割に通じるよい性質をもっている. さらに, 正則三角形分割は凸多面体と密接な関係をもった概念で, 数学・組合せ論で色々な展開が図られている. 詳細は [1] 参照.
[1] 今井桂子, 「三角形分割全体の離散構造」, 『離散構造とアルゴリズムVI』 (藤重悟編), 近代科学社, 1999.
三角測量
(triangulation から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/28 04:08 UTC 版)
三角測量（さんかくそくりょう）は、ある基線の両端にある既知の点から測定したい点への角度をそれぞれ測定することによって、その点の位置を決定する三角法および幾何学を用いた測量方法である。その点までの距離を直接測る三辺測量と対比される。既知の1辺と2か所の角度から、三角形の3番目の頂点として測定点を決定することができる。
- ^ Diogenes Laërtius, “Life of Thales”, The Lives and Opinions of Eminent Philosophers 2008年2月22日閲覧。 I, 27
- ^ Proclus, In Euclidem
- ^ Joseph Needham (1986). Science and Civilization in China: Volume 3, Mathematics and the Sciences of the Heavens and the Earth. Taipei: Caves Books Ltd. pp. 539-540
- ^ 劉徽, 『海島算経』
- ^ Kurt Vogel (1983; 1997), A Surveying Problem Travels from China to Paris, in Yvonne Dold-Samplonius (ed.), From China to Paris, Proceedings of a conference held July, 1997, Mathematisches Forschungsinstitut, Oberwolfach, Germany. ISBN 3-515-08223-9.
- ^ a b Donald Routledge Hill (1984), A History of Engineering in Classical and Medieval Times, London: Croom Helm & La Salle, Illinois: Open Court. ISBN 0-87548-422-0. pp. 119-122
- ^ O'Connor, John J.; Robertson, Edmund F., “Abu Arrayhan Muhammad ibn Ahmad al-Biruni”, MacTutor History of Mathematics archive, University of St Andrews.
- ^ 武藤勝彦『地図の話』岩波書店、1949年、123-128頁
- ^ Michael Jones (2004), "Tycho Brahe, Cartography and Landscape in 16th Century Scandinavia", in Hannes Palang (ed), European Rural Landscapes: Persistence and Change in a Globalising Environment, p.210
- ^ Martin and Jean Norgate (2003), Saxton's Hampshire: Surveying, University of Portsmouth
- ^ 武藤勝彦『地図の話』岩波書店、1949年、130頁
- ^ 武藤勝彦『地図の話』岩波書店、1949年、131頁
- ^ 武藤勝彦『地図の話』岩波書店、1949年、134頁
- ^ a b c 武藤勝彦『地図の話』岩波書店、1949年、133頁
- ^ 武藤勝彦『地図の話』岩波書店、1949年、136頁
- ^ 質問6-1）星までの距離はどうやって測定するの？ - 国立天文台
- ^ 『三角測量原理』による"星までの距離"の測定と限界について。 - オリックス・レンテック
- ^ 宇宙の質問箱-恒星編 - 国立科学博物館
- ^ “史跡「開拓使札幌本庁本庁舎跡および旧北海道庁本庁舎」保存活用計画(素案)”. 北海道. 2020年12月4日閲覧。
- ^ “北海道実測図”. 函館市中央図書館デジタル資料館. 2020年12月4日閲覧。
- ^ 加藤芳夫「明治初期の勇払基線と苫小牧の発展:わが国最初の系統的な基線測量と三角測量をめぐって」『地図』第16巻第4号、日本地図学会、1978年、 11-16頁、 doi:10.11212/jjca1963.16.4_11、 ISSN 0009-4897、 NAID 130003812982。
- ^ “開拓使三角測量一本木基点”. 文化遺産オンライン. 2020年12月4日閲覧。
- ^ “江戸の数学 第一部 和算の歴史 第4章 実学としての和算 コラム 測量の方法”. 国立国会図書館. 2020年12月6日閲覧。
- ^ “伊能忠敬が仰いだ山々”. 2020年12月6日閲覧。
- triangulationのページへのリンク
