計算幾何学パッケージ
計算幾何学とは，幾何問題を解くための効率的なアルゴリズムの研究のことである．最近傍点問題は，ある距離の計測方法に従って点群の中から問合せ点に最も近い1点を見付けるというものである．最近傍問題は，問合せ点への距離の方が点群の他のどの点への距離よりも短いところにあるすべての点の位置を見付けるというものである．このパッケージではこれらの問題と，平面点およびユークリッド(Euclidean)距離の場合にこれと関連した問題を解くための関数を提供している．
| ConvexHull[{{x1,y1},{x2,y2},...}] | 平面上の点群の凸包を求める |
| DelaunayTriangulation[{{x1,y1},{x2,y2},...}] |
| 平面上の点群のドローネ三角形分割を求める |
| VoronoiDiagram[{{x1,y1},{x2,y2},...}] |
| 平面上の点群のボロノイ図を求める |
計算幾何学関数
集合
S の凸包とは，
S を含む最小集合の境界線のことである．
S のボロノイ図(Voronoi diagram)とは，
S の各点についての最近傍領域の集合体である．平面上の点群では，このような近傍領域は多角形となる．
S のドローネ三角形分割(Delaunay Triangulation)とは，三角形がその外接円に
S の点を含まないような
S の点群の三角分割のことである．これは，近接する多角形が辺を共有するかどうかに従って
S の点群を接続することと等しい．
| Out[3]= |  |
|
| Out[4]= |  |
|
これは，ドローネ三角形の各頂点に隣接する頂点のリストを反時計回りに与えたリストである．例えば， {1, {4, 3, 2}}という要素は， data2Dの最初の点が反時計回りに4番目，3番目，2番目の点と接続されることを示す．
| Out[5]//Shallow= |  |
|
DelaunayTriangulationでは点群間の接続を指定するだけでよいが，
VoronoiDiagramではボロノイ点（多角形の各頂点）の集合だけでなくボロノイ点間の接続も指定しなければならない．この2つの関数のもうひとつの違いとして，三角形分割は線分で構成されているのに対して，ボロノイ図は線分と半直線の両方で構成されているということがある．例えば，ボロノイ図の場合，凸包の内部の母点のボロノイ領域（最近傍の多角形）は閉多角形となるが，凸包上の母点のボロノイ領域は開多角形となる．
このような事実により，
VoronoiDiagramの出力は
DelaunayTriangulationの出力よりも複雑なものとなる．ボロノイ図は，最初にボロノイ点のリスト，それに続きボロノイ点の隣接リストとして与えられる．頂点リストの中には，図の有限の点が最初にリストされる．無限の点には頭部
Rayが付き，最後にリストされる．
vorvertにボロノイ点のリストを， vorvalにボロノイ点の隣接リストを割り当てる． |
vorvertの最初の頂点は座標 {-0.0158537, 8.44146}の有限の点である． vorvertの最後の頂点は無限の点である．この点は始点 {10.5172, 3.46115}で {13.95, 0.2}を含む Rayオブジェクトによって表される．
| Out[7]= |  |
|
vorvalの各要素は data2Dで点の指標を与え，その次にその点についてのボロノイ領域を構成するボロノイ点を反時計回り順のリストで与える．
Out[8]//Short= |
| |  |
|
以下は data2Dの最初の点に対するボロノイ点の隣接リストである．
| Out[9]= |  |
|
次では vorvertからボロノイ点の座標を選ぶ．初めの2つの頂点は頭部 Listを持つが，後の2つは頭部 Rayを持つ．したがって， data2Dの最初の点に関連するボロノイ領域は開いており，1つの線分と2つの半直線によって定義されている．
| Out[10]= |  |
|
| VoronoiDiagram[{{x1,y1},{x2,y2},...},delval] |
| ドローネ三角形分割の頂点の隣接リスト delval を使って，ボロノイ図を計算する |
| VoronoiDiagram[{{x1,y1},{x2,y2},...},delval,convexhull] |
| ドローネ三角形分割の頂点の隣接リスト delval と凸包の指標のリスト convexhull を使って，ボロノイ図を計算する |
ドローネ三角形分割と凸包を使ったボロノイ図の計算
ドローネ三角形分割の頂点の隣接リストを利用することにより， data2Dのボロノイ図をより効率的に計算する． |
ここで，ボロノイ図はドローネ三角形分割と凸包の両方を使って計算される． |
| PlanarGraphPlot[{{x1,y1},{x2,y2},...}] |
| 点群のドローネ三角形分割をプロットする |
| PlanarGraphPlot[{{x1,y1},{x2,y2},...},indexlist] |
| indexlist の反時計回りの指標のリストにより描かれるグラフをプロットする |
| PlanarGraphPlot[{{x1,y1},{x2,y2},...},val] |
| 頂点の隣接リスト val により描かれるグラフをプロットする |
| DiagramPlot[{{x1,y1},{x2,y2},...}] | 点群のボロノイ図をプロットする |
| DiagramPlot[{{x1,y1},{x2,y2},...},diagvert,diagval] |
| 頂点リスト diagvert と頂点隣接リスト diagval により描かれる図をプロットする |
| TriangularSurfacePlot[{{x1,y1,z1},{x2,y2,z2},...}] |
| 点群を x-y 平面に投影することにより描かれるドローネ三角形分割に従って表面をプロットする |
| TriangularSurfacePlot[{{x1,y1,z1},{x2,y2,z2},...},trival] |
| 頂点の隣接リスト trival によって描かれる三角形分割に従って表面をプロットする |
計算幾何学のプロット関数
| Out[13]= |  |
|
| Out[14]= |  |
|
下のプロットは， trivalによって与えられた data2Dの三角形分割である．
| Out[16]= |  |
|
| Out[17]= |  |
|
diagvertと diagvalによって与えられた data2Dの図をプロットする．
| Out[20]= |  |
|
data2Dと同じ x- y 座標を持つ3次元の点群の集合である． |
| Out[22]= |  |
|
これは三角形分割 trivalによって確立された接続性に従った z 座標のプロットである．
| Out[23]= |  |
|
| Out[24]= |  |
|
| ConvexHull[{{x1,y1},{x2,y2},...},AllPoints->False] |
| 凸包を定義するために必要な点群の最小集合を与える |
| DelaunayTriangulation[{{x1,y1},{x2,y2},...},Hull->True] |
| ドローネ三角形分割の頂点の隣接リストと凸包の両方を与える |
| PlanarGraphPlot[{{x1,y1},{x2,y2},...},LabelPoints->False] |
| ラベルなしでドローネ三角形分割をプロットする |
| DiagramPlot[{{x1,y1},{x2,y2},...},LabelPoints->False] |
| ラベルなしでボロノイ図をプロットする |
| DiagramPlot[{{x1,y1},{x2,y2},...},TrimPoints->n] |
| 最も外側の半直線と最も外側のボロノイ点(n-1)個を削除したボロノイ図をプロットする |
計算幾何学関数のオプション
| Out[25]= |  |
|
| Out[26]//Shallow= |  |
|
以下は [0, 1]× [0, 1]上に一様に分布した乱数の集合である． |
以下のボロノイ図のプロットでは，外れ値の頂点が著しく目立つ．
| Out[29]= |  |
|
TrimPoints->2とは，最も外側の半直線と最も外側のボロノイ点がそれぞれ1つずつ削除されるように図をプロットすることである．
| Out[30]= |  |
|
TrimPointsオプションは， randomの点群がプロット全体に現れるまで，図を拡大するために使うことができる．
| Out[31]= |  |
|
ドローネ三角形分割のテスト
delvalはドローネ三角形分割なので，以下は Trueを返す．
| Out[32]= |  |
|
trivalはドローネ三角形分割ではないので，以下は Falseを返す．
| Out[33]= |  |
|
| BoundedDiagram[{{a1,b1},{a2,b2},...},{{x1,y1},{x2,y2},...}] |
| 点{x, y}の集合の有界のボロノイ図を計算する．ここで限界は点群{a, b}により描かれる凸多角形である |
| BoundedDiagram[{{a1,b1},{a2,b2},...},{{x1,y1},{x2,y2},...},delval] |
| ドローネ三角形の頂点の隣接リスト delval を使って，有界のボロノイ図を計算する |
| BoundedDiagram[{{a1,b1},{a2,b2},...},{{x1,y1},{x2,y2},...},delval,convexhull] |
| ドローネ三角形の頂点の隣接リスト delval と凸包の指標リスト convexhull を使って有界のボロノイ図を計算する |
有界のボロノイ図の計算
空間データが平面の有限領域内で収集された場合は，点群の非有界のボロノイ図は各点が影響を与える領域を正しく描かない可能性がある．図の周囲のタイルは開いており，影響の無限領域を示しているようだが，実際には，タイルが開いているのは単に空間標本の程度が限られているために過ぎない．データの非有界のボロノイ図を，データが収集された凸領域の境界と交差させるのが役に立つこともある．そうすれば，データの各点は閉じたタイルあるいは影響の有限領域と関連付けることができるようになる．
BoundedDiagramは非有界のボロノイ図を見付けることから始まる．その後，多角形の境界となる頂点を図に統合し，境界の外側に位置するボロノイ点を削除しながら，境界を反時計回りに動く．ボロノイ図の開いたタイルを統合することにより，データの収集が平面上の一部に限られていなかった場合に得られたと思われる真の潜在的な閉じたタイルに近似できる．
有界図は頂点の座標のリストおよび頂点の隣接リストとして表すことができる．もとの非有界図の各点について1つ項目があり，反時計回りの順で関連した有界多角形の頂点を示す．
BoundedDiagramには非有界のボロノイ図が必要なので，ドローネ三角形分割の頂点隣接リストおよび凸包等の付加的な引数を与えることによりより，有界のボロノイ図の計算を効率的に作成することができる．
data2Dの標本が抽出された長方形領域の座標である． |
有界図の頂点のリストを diagvert1に，有界図の頂点の隣接リストを diagval1に割り当てる． |
以下は diagvert1と diagval1によって与えられた data2Dの有界図のプロットである．
| Out[36]= |  |
|
| TileAreas[{{x1,y1},{x2,y2},...},{{q1, q2,...},val}] |
| 頂点の隣接リスト val によって規定されるように，中心が{xi, yi}}で頂点が qj であるタイルの面積を求める |
タイル面積の計算
空間相互作用モデルの構築に，ボロノイ図を利用することもできる．単に各タイルの影響範囲を計算することもできる．
非有界のボロノイ図では，無限領域を持つタイルもある．
| Out[37]= |  |
|
有界のボロノイ図では，すべてのタイルが有限領域を持つ．
| Out[38]= |  |
|
以下は標本が抽出された長方形の面積によりスケールされたタイル面積である．
| Out[39]= |  |
|
