計算幾何学パッケージ
計算幾何学とは，幾何問題を解くための効率的なアルゴリズムの研究のことである．最近傍点問題は，ある距離の計測方法に従って点群の中から問合せ点に最も近い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 の点群を接続することと等しい．
DelaunayTriangulationでは点群間の接続を指定するだけでよいが，VoronoiDiagramではボロノイ点（多角形の各頂点）の集合だけでなくボロノイ点間の接続も指定しなければならない．この2つの関数のもうひとつの違いとして，三角形分割は線分で構成されているのに対して，ボロノイ図は線分と半直線の両方で構成されているということがある．例えば，ボロノイ図の場合，凸包の内部の母点のボロノイ領域（最近傍の多角形）は閉多角形となるが，凸包上の母点のボロノイ領域は開多角形となる．
このような事実により，VoronoiDiagramの出力はDelaunayTriangulationの出力よりも複雑なものとなる．ボロノイ図は，最初にボロノイ点のリスト，それに続きボロノイ点の隣接リストとして与えられる．頂点リストの中には，図の有限の点が最初にリストされる．無限の点には頭部Rayが付き，最後にリストされる．
| VoronoiDiagram[{{x1,y1},{x2,y2},…},delval] | |
| ドロネー三角形分割の頂点の隣接リスト delval を使って，ボロノイ図を計算する | |
| VoronoiDiagram[{{x1,y1},{x2,y2},…},delval,convexhull] | |
| ドロネー三角形分割の頂点の隣接リスト 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 によって描かれる三角形分割に従って表面をプロットする | |
| 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)個を削除したボロノイ図をプロットする | |
| DelaunayTriangulationQ[{{x1,y1},{x2,y2},…},trival] | |
| 頂点の隣接リスト trival が点群のドロネー三角形分割を表すならTrueを， 表さないならFalseを返す | |
| 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には非有界のボロノイ図が必要なので，ドロネー三角形分割の頂点隣接リストおよび凸包等の付加的な引数を与えることによりより，有界のボロノイ図の計算を効率的に作成することができる．
| TileAreas[{{x1,y1},{x2,y2},…},{{q1, q2,…},val}] | |
| 頂点の隣接リスト val によって規定されるように，中心が{xi,yi}}で頂点が qj であるタイルの面積を求める | |
空間相互作用モデルの構築に，ボロノイ図を利用することもできる．単に各タイルの影響範囲を計算することもできる．