WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

計算幾何学パッケージ

バージョン10で，ComputationalGeometryパッケージのすべての機能がWolframシステムに組み込まれている． »

計算幾何学とは，幾何問題を解くための効率的なアルゴリズムの研究のことである．最近傍点問題は，ある距離の計測方法に従って点群の中から問合せ点に最も近い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 の点群を接続することと等しい．

パッケージをロードする．
Wolfram Language code: <<ComputationalGeometry`
平面上の点群のリストである．
Wolfram Language code: data2D = {{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {2.1, 11.1}, {9.5, 14.9}, {13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, {5.3, 2.4}, {8.45, 4.7}, {11.5, 9.6}, {13.8, 7.3}, {12.9, 3.1}, {11, 1.1}};
凸包にある点群の指標を反時計回りの順に与える．
Wolfram Language code: convexhull = ConvexHull[data2D]
重複する点は無視される．
Wolfram Language code: ConvexHull[{{0, 0}, {1, 0}, {0, 0}, {2, 0}, {1, 1}}]
これは，ドロネー三角形の各頂点に隣接する頂点のリストを反時計回りに与えたリストである．例えば，{1,{4,3,2}}という要素は，data2Dの最初の点が反時計回りに4番目，3番目，2番目の点と接続されることを示す．
Wolfram Language code: (Shallow[#, {5, 6}]&)[delval = DelaunayTriangulation[data2D]]

DelaunayTriangulationでは点群間の接続を指定するだけでよいが，VoronoiDiagramではボロノイ点（多角形の各頂点）の集合だけでなくボロノイ点間の接続も指定しなければならない．この2つの関数のもうひとつの違いとして，三角形分割は線分で構成されているのに対して，ボロノイ図は線分と半直線の両方で構成されているということがある．例えば，ボロノイ図の場合，凸包の内部の母点のボロノイ領域（最近傍の多角形）は閉多角形となるが，凸包上の母点のボロノイ領域は開多角形となる．

このような事実により，VoronoiDiagramの出力はDelaunayTriangulationの出力よりも複雑なものとなる．ボロノイ図は，最初にボロノイ点のリスト，それに続きボロノイ点の隣接リストとして与えられる．頂点リストの中には，図の有限の点が最初にリストされる．無限の点には頭部Rayが付き，最後にリストされる．

vorvertにボロノイ点のリストを，vorvalにボロノイ点の隣接リストを割り当てる．
Wolfram Language code: {vorvert, vorval} = VoronoiDiagram[data2D];
vorvertの最初の頂点は座標{-0.0158537,8.44146}の有限の点である．vorvertの最後の頂点は無限の点である．この点は始点{10.5172,3.46115}で{13.95,0.2}を含むRayオブジェクトによって表される．
Wolfram Language code: {First[vorvert], Last[vorvert]}
vorvalの各要素はdata2Dで点の指標を与え，その次にその点についてのボロノイ領域を構成するボロノイ点を反時計回り順のリストで与える．
Wolfram Language code: vorval // Short
以下はdata2Dの最初の点に対するボロノイ点の隣接リストである．
Wolfram Language code: vorval[[1, 2]]
次ではvorvertからボロノイ点の座標を選ぶ．初めの2つの頂点は頭部Listを持つが，後の2つは頭部Rayを持つ．したがって，data2Dの最初の点に関連するボロノイ領域は開いており，1つの線分と2つの半直線によって定義されている．
Wolfram Language code: vorvert[[%]]
VoronoiDiagram[{{x1,y1},{x2,y2},…},delval]
ドロネー三角形分割の頂点の隣接リスト delval を使って，ボロノイ図を計算する
VoronoiDiagram[{{x1,y1},{x2,y2},…},delval,convexhull]
ドロネー三角形分割の頂点の隣接リスト delval と凸包の指標のリスト convexhull を使って，ボロノイ図を計算する

ドロネー三角形分割と凸包を使ったボロノイ図の計算

ドロネー三角形分割の頂点の隣接リストを利用することにより，data2Dのボロノイ図をより効率的に計算する．
Wolfram Language code: VoronoiDiagram[data2D, delval];
ここで，ボロノイ図はドロネー三角形分割と凸包の両方を使って計算される．
Wolfram Language code: VoronoiDiagram[data2D, delval, convexhull];
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 によって描かれる三角形分割に従って表面をプロットする

計算幾何学のプロット関数

PlanarGraphPlotのデフォルトは，点群のドロネー三角形分割のプロットである．
Wolfram Language code: PlanarGraphPlot[data2D]
以下は点群の凸包のプロットである．
Wolfram Language code: PlanarGraphPlot[data2D, convexhull]
以下は別の三角形分割法である．
Wolfram Language code: trival = Insert[Insert[Delete[delval, {{12, 2, 4}, {16, 2, 2}}], 15, {11, 2, 2}], 11, {15, 2, 3}];
下のプロットは，trivalによって与えられたdata2Dの三角形分割である．
Wolfram Language code: PlanarGraphPlot[data2D, trival]
DiagramPlotのデフォルトは，点群のボロノイ図のプロットである．
Wolfram Language code: DiagramPlot[data2D]
ボロノイ点の別の集合である．
Wolfram Language code: diagvert = ReplacePart[vorvert, {-6., 0.}, {27, 2}];
別のボロノイ点の隣接リストである．
Wolfram Language code: diagval = Join[Drop[vorval, -8], {{9, {1, 6, 8, 3}}, {10, {2, 6, 1, 24, 27}}}, Drop[vorval, 10]];
diagvertとdiagvalによって与えられたdata2Dの図をプロットする．
Wolfram Language code: DiagramPlot[data2D, diagvert, diagval]
data2Dと同じ x-y 座標を持つ3次元の点群の集合である．
Wolfram Language code: data3D = (Append[#, Sqrt[64 - (#[[1]] - 8)^2 - (#[[2]] - 8)^2]]&) /@ data2D;
TriangularSurfacePlotのデフォルトは，x-y 座標のドロネー三角形分割によって確立された接続性に従った z 座標のプロットである．
Wolfram Language code: TriangularSurfacePlot[data3D]
これは三角形分割trivalによって確立された接続性に従った z 座標のプロットである．
Wolfram Language code: TriangularSurfacePlot[data3D, trival]
デフォルトのListPlot3Dの動作と比較する．
Wolfram Language code: ListPlot3D[data3D, Axes -> False]
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)個を削除したボロノイ図をプロットする

計算幾何学関数のオプション

凸包を定義するのに必要な点群の最小集合を与える．
Wolfram Language code: ConvexHull[{{0, 0}, {1, 0}, {0, 0}, {2, 0}, {1, 1}}, AllPoints -> False]
以下はドロネー三角形分割と凸包の両方を返す．
Wolfram Language code: Shallow[DelaunayTriangulation[data2D, Hull -> True]]
以下は×上に一様に分布した乱数の集合である．
Wolfram Language code: random = Table[{Random[], Random[]}, {40}];
randomのボロノイ図を計算する，
Wolfram Language code: {randvert, randval} = VoronoiDiagram[random];
以下のボロノイ図のプロットでは，外れ値の頂点が著しく目立つ．
Wolfram Language code: DiagramPlot[random, randvert, randval, LabelPoints -> False]
TrimPoints->2とは，最も外側の半直線と最も外側のボロノイ点がそれぞれ1つずつ削除されるように図をプロットすることである．
Wolfram Language code: DiagramPlot[random, randvert, randval, LabelPoints -> False, TrimPoints -> 2]
TrimPointsオプションは，randomの点群がプロット全体に現れるまで，図を拡大するために使うことができる．
Wolfram Language code: DiagramPlot[random, randvert, randval, LabelPoints -> False, TrimPoints -> 6]
DelaunayTriangulationQ[{{x1,y1},{x2,y2},…},trival]
頂点の隣接リスト trival が点群のドロネー三角形分割を表すならTrueを， 表さないならFalseを返す

ドロネー三角形分割のテスト

delvalはドロネー三角形分割なので，以下はTrueを返す．
Wolfram Language code: DelaunayTriangulationQ[data2D, delval]
trivalはドロネー三角形分割ではないので，以下はFalseを返す．
Wolfram Language code: DelaunayTriangulationQ[data2D, trival]
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の標本が抽出された長方形領域の座標である．
Wolfram Language code: b1 = {{0, 1}, {14, 1}, {14, 16}, {0, 16}};
有界図の頂点のリストをdiagvert1に，有界図の頂点の隣接リストをdiagval1に割り当てる．
Wolfram Language code: {diagvert1, diagval1} = BoundedDiagram[b1, data2D, delval, convexhull];
以下はdiagvert1とdiagval1によって与えられたdata2Dの有界図のプロットである．
Wolfram Language code: DiagramPlot[data2D, diagvert1, diagval1]
TileAreas[{{x1,y1},{x2,y2},…},{{q1, q2,…},val}]
頂点の隣接リスト val によって規定されるように，中心が{xi,yi}}で頂点が qj であるタイルの面積を求める

タイル面積の計算

空間相互作用モデルの構築に，ボロノイ図を利用することもできる．単に各タイルの影響範囲を計算することもできる．

非有界のボロノイ図では，無限領域を持つタイルもある．
Wolfram Language code: TileAreas[data2D, diagvert, diagval]
有界のボロノイ図では，すべてのタイルが有限領域を持つ．
Wolfram Language code: areas = TileAreas[data2D, diagvert1, diagval1]
以下は標本が抽出された長方形の面積によりスケールされたタイル面積である．
Wolfram Language code: (areas/14 15)