ComputationalGeometry

THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.

Documentation Mathematicaアドオンとリンク標準パッケージ DiscreteMath

DiscreteMath`ComputationalGeometry`

計算幾何学とは，幾何問題を解くための効率的なアルゴリズムの研究のことである．Nearest Neighbor問題には，ある距離の測量方法に従って点群の中から問合せ点に最も近い1点を見付けるというものがある．Nearest Neighborhood問題には，点群のどの点への距離よりも問合せ点への距離の方が短い点すべての位置を見付けるというものがある．このパッケージではこれらの問題と，平面点およびユークリッド(Euclidean)距離の場合にこれと関連した問題を解くための関数を提供している．

計算幾何学関数

集合の凸包とは，を含む最小集合の境界線のことである．のボロノイ図(Voronoi diagram)とは，の各点についての最近傍領域の集合体である．平面上の点群では，このような近傍領域は多角形となる．のドローネ三角形分割(Delaunay Triangulation)とは，三角形がその外接円にの点を含まないようなの点群の三角分割のことである．これは，近接する多角形が辺を共有するかどうかに従っての点群を接続することと等しい．

パッケージをロードする．

In[1]:= <<DiscreteMath`ComputationalGeometry`

平面状の点群のリストである．

In[2]:= 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}};

凸包にある点群の指標を左回りで与える．

In[3]:= convexhull = ConvexHull[data2D]

Out[3]=

重複する点は無視される．

In[4]:= ConvexHull[{{0,0}, {1,0}, {0,0}, {2,0},
{1,1}}]

Out[4]=

以下は，ドローネ三角形の各頂点に隣接する頂点を左回りに与たリストである．例えば，{1, {4, 3, 2}}という要素は，data2Dの最初の点が左回りに4番目，3番目，2番目の点と接続されることを示す．

In[5]:= (delval =
DelaunayTriangulation[data2D]) // Shallow[#, {5, 6}]&

Out[5]//Shallow=

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

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

vorvertに母点のリストを，vorvalにボロノイ点のリストを割り当てる．

In[6]:= {vorvert, vorval} = VoronoiDiagram[data2D];

vorvertの最初の母点は座標{-0.0158537, 8.44146}の有限点である．vorvertの最後の点は無限点である．この点は原点{10.5172, 3.46115}で{13.95, 0.2}を含むRayオブジェクトによって表される．

In[7]:= {First[vorvert], Last[vorvert]}

Out[7]=

vorvalの各要素はdata2Dで点の指標を与え，その次にその点についてのボロノイ領域を構成するボロノイ点を左回り順のリストで与える．

In[8]:= vorval // Short

Out[8]//Short=

以下はdata2Dの最初の点に対するボロノイ点のリストである．

In[9]:= vorval[[1,2]]

Out[9]=

次ではvorvertからボロノイ点の座標を選ぶ．初めの2つの頂点は頭部Listを持つが，最後の2つは頭部Rayを持つ．従って，data2Dの最初の点についてのボロノイ領域は開いており，1つの線分と2つの射線によって定義されている．

In[10]:= vorvert[[%]]

Out[10]=

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

ドローネ三角形分割の頂点の隣接リストを利用することにより，data2Dのボロノイ図をより効率的に計算する．

In[11]:= VoronoiDiagram[data2D, delval];

ここで，ボロノイ図はドローネ三角形分割と凸包の両方を使って計算される．

In[12]:= VoronoiDiagram[data2D, delval,
convexhull];

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

PlanarGraphPlotのデフォルトは，点群のドローネ三角形分割のプロットである．

In[13]:= PlanarGraphPlot[data2D,
TextStyle -> {"FontSize" -> 8}]

Out[13]=

以下は点群の凸包のプロットである．

In[14]:= PlanarGraphPlot[data2D, convexhull]

Out[14]=

以下は別の三角形分割法である．

In[15]:= trival = Insert[Insert[Delete[delval,
{{12, 2, 4}, {16, 2, 2}}], 15, {11, 2, 2}],
11, {15, 2, 3}];

下のプロットは，trivalによって与えられたdata2Dの三角形分割である．

In[16]:= PlanarGraphPlot[data2D, trival,
TextStyle -> {"FontSize" -> 8}]

Out[16]=

DiagramPlotのデフォルトは，点群のボロノイ図のプロットである．

In[17]:= DiagramPlot[data2D]

Out[17]=

別の母点の集合である．

In[18]:= diagvert = ReplacePart[vorvert,
{-6., 0.}, {27, 2}];

別のボロノイ点のリストである．

In[19]:= diagval = Join[Drop[vorval, -8],
{{9, {1, 6, 8, 3}}, {10, {2, 6, 1,
24, 27}}},
Drop[vorval, 10]];

diagvertとdiagvalによって与えられたdata2Dの図をプロットする．

In[20]:= DiagramPlot[data2D, diagvert, diagval]

Out[20]=

data2Dと同じ座標を持つ3次元の点群の集合である．

In[21]:= data3D = Map[Append[#,
Sqrt[64-(#[[1]]-8)^2-(#[[2]]-8)^2]]&,
data2D];

TriangularSurfacePlotのデフォルトは，座標のドローネ三角形分割によって確立された接続に従った座標のプロットである．

In[22]:= TriangularSurfacePlot[data3D]

Out[22]=

これは三角形分割trivalによって確立された接続性に従った座標のプロットである．

In[23]:= TriangularSurfacePlot[data3D, trival]

Out[23]=

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

凸包を定義するのに必要な点群の最小集合を与える．

In[24]:= ConvexHull[{{0,0}, {1,0}, {0,0}, {2,0},
{1,1}}, AllPoints -> False]

Out[24]=

以下はドローネ三角形分割と凸包の両方を返す．

In[25]:= DelaunayTriangulation[data2D,
Hull -> True] // Shallow

Out[25]//Shallow=

以下は[0, 1][0, 1]上に一様に分布した乱数の集合である．

In[26]:= random = Table[{Random[], Random[]}, {40}];

randomのボロノイ図を計算する，

In[27]:= {randvert, randval} =
VoronoiDiagram[random];

以下のボロノイ図のプロットでは，外れ値が著しく目立つ．

In[28]:= DiagramPlot[random, randvert, randval,
LabelPoints -> False]

Out[28]=

TrimPoints -> 2とは，最も外側の射線と最も外側のボロノイ点が1つずつ削除されるように図をプロットすることである．

In[29]:= DiagramPlot[random, randvert, randval,
LabelPoints -> False, TrimPoints -> 2]

Out[29]=

TrimPointsオプションは，randomの点群がプロット全体に現れるまで，図を拡大するために使うことができる．

In[30]:= DiagramPlot[random, randvert, randval,
LabelPoints -> False, TrimPoints -> 6]

Out[30]=

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

delvalはドローネ三角形分割なので，以下はTrueを返す．

In[31]:= DelaunayTriangulationQ[data2D, delval]

Out[31]=

trivalはドローネ三角形分割ではないので，以下はFalseを返す．

In[32]:= DelaunayTriangulationQ[data2D, trival]

Out[32]=

最近傍点の計算

{7.92, 8.92}に最も近いdata2Dの点を求める．

In[33]:= neighbor = NearestNeighbor[{7.92, 8.92},
data2D]

Out[33]=

ボロノイ図が分かっているなら，より高速のNearestNeighborの計算のために，点のリストを母点のリストとボロノイ点のリストで置き換えることができる．

In[34]:= NearestNeighbor[{7.92, 8.92},
vorvert, vorval]

Out[34]=

{7.92, 8.92}を含むボロノイ多角形の座標を与える．

In[35]:= vorvert[[vorval[[neighbor, 2]]]]

Out[35]=

data2Dの点群のそれぞれについて，data2D内での最近傍の点はその点自体である．

In[36]:= NearestNeighbor[data2D, vorvert, vorval]

Out[36]=

以下の点の最初の半分と後半は，それぞれ別の分布から派生していることが分かる．

In[37]:= known = Join[{{5.84, 1.2}, {5.94, 10.99},
{5.1, 2.82}, {5.8, 1.67}, {5.63, 10.}},
{{0.31, 5.11}, {7.73, 5.38},
{10.42, 5.89}, {6.1, 5.1}, {6.92, 5.63}}];

以下の各点は，上の2つの分布のどちらかから派生していると考えられる．

In[38]:= unknown = {{5.56, 7.48}, {5.1, 1.67},
{5.17, 4.89}, {0.3, 5.27},
{6.74, 5.73}, {5.09, 9.07}};

以下はknownの最近傍点の分類に従ってunknownの点を分類している．

In[39]:= If[# > 5, 2, 1]& /@
NearestNeighbor[unknown, known]

Out[39]=

有界のボロノイ図の計算

空間データが平面の有限領域内で収集された場合は，非有界のボロノイ図は各点が影響を与える領域を正しく描かない可能性がある．図の周囲のタイルは開いており，影響の無限領域を示している．これは実際には，開いたタイルは単に空間標本の程度が限られているために過ぎない．データの非有界のボロノイ図を，データが収集された凸領域の境界と交差させるのが役に立つこともある．データの各点は閉じたタイルあるいは影響の有限領域と関連付けることができる．

BoundedDiagramは非有界のボロノイ図を見付けることから始まる．その後，多角形の境界となる点を図に統合し，境界の外側に位置するボロノイ点を削除しながら，境界を時計と反対回りに動く．ボロノイ図の開いたタイルを統合することにより，データの収集が平面上の一部に限られていなかった場合に得られたと思われる真の潜在的な閉じたタイルに近似できる．

有界図は頂点の座標のリストおよび頂点の隣接リストとして表すことができる．元の非有界図の各点について1つ項目があり，時計と反対回りの順で関連した有界多角形の頂点を示す．

data2Dの標本が抽出された長方形領域の座標である．

In[40]:= b1 = {{0, 1}, {14, 1}, {14, 16}, {0, 16}};

有界図の頂点のリストをdiagvert1に，有界図の頂点の隣接リストをdiagval1.に割り当てる．

In[41]:= {diagvert1, diagval1} = BoundedDiagram[b1, data2D, delval, convexhull];

以下はdiagvert1とdiagval1.によって与えられたdata2Dの有界図のプロットである．

In[42]:= DiagramPlot[data2D, diagvert1, diagval1]