Libx Awesomeリスト

    このページの内容

    Awesome Computational Geometry

    Computational Geometryを扱う資料や関連プロジェクトをまとめたAwesomeリストです。

    目次

    アルゴリズムの可視化

    • Convex Hull - 形状を含む最小の凸集合である凸包。
    • Convex Hull Algorithms - gift wrapping、Graham’s scan、quickhull、分割統治法、monotone chain、Chan’s algorithmなど、多数の凸包アルゴリズムを可視化するウェブサイト。
    • Chan’s Algorithm - 2次元または3次元の点集合の凸包を計算する、出力サイズに応じて最適なアルゴリズム。
    • Kirkpatrick’s Point location - 三角形分割を用い、O(n)空間とO(log n)クエリ時間で点位置を求めるデータ構造と手法。
    • Voronoi Diagrams - 平面を、与えられた点集合に近い領域へ分割したもの。
    • Fortune’s Algorithm - O(n log n)時間、O(n)空間でボロノイ図を生成する走査線アルゴリズム。
    • k-d tree - 最近傍探索などの検索を効率的に行うための、k次元空間の分割方法。
    • Configuration Space - ロボットのような物体が取り得る構成の空間。
    • CGViz: Computational Geometry Interactive Visualizations (GitHub) - 探索、教育、出力可能な視覚表現の作成を目的に設計された、多数のアルゴリズムを段階的に可視化するFOSSウェブアプリ。

    書籍

    • Computational Geometry: Algorithms and Applications - Mark de Berg、Otfried Cheong、Marc van Kreveld、Mark Overmarsによる教科書（2008年）。
    • Computational Geometry in C - Joseph O’Rourkeによる、コンピュータグラフィックス、ロボティクス、工学設計などで生じる幾何アルゴリズムの設計と実装への、広く読まれている入門書（1998年）。
    • Computational Geometry: An Introduction - Franco P. PreparataとMichael I. Shamosによる入門教科書（1993年）。
    • Algorithmic Geometry - Jean-Daniel Boissonnat、Mariette Yvinec、Herve Bronnimanによる教科書（1998年）。
    • Discrete and Computational Geometry - 純粋数学の比較的新しい発展である離散幾何学と、応用主導のコンピュータサイエンスで新興の分野である計算幾何学の交わりを、包括的かつ親しみやすく紹介するSatyan L. DevadossとJoseph O’Rourkeの書籍（2011年）。
    • Interactive Computational Geometry - A taxonomic approach - Jim Arlowによる、Mathematicaを使った計算幾何学の基本アルゴリズムの対話的入門（2014年）。

    ノート

    ライブラリ

    • CGAL - 効率的で信頼性の高い幾何アルゴリズムへC++ライブラリの形で容易にアクセスできるソフトウェアプロジェクト。このウェブサイトにはこれらのアルゴリズムの多くに関する解説もある。
    • Wykobi - 非常に効率的で堅牢、かつ使いやすいC++の2D/3D指向計算幾何学ライブラリ。
    • geometry3Sharp - 幾何計算のためのオープンソース、BoostライセンスのC#ライブラリ。
    • Computational Geometry Software Libraries - Jeff Ericksonによる、UIUCの大規模な幾何ソフトウェアのコレクションとライブラリ。
    • The Stony Brook Algorithm Repository - The Algorithm Design Manualに基づくアルゴリズムのリポジトリ。
    • Geometric Tools - 数学、グラフィックス、画像解析、物理学の分野で計算するためのソースコードのライブラリ。いくつかの計算幾何学アルゴリズムを含む。
    • GeoLib - C++、C#、Javaで利用できる高速かつ効率的な計算幾何学ライブラリ。
    • hull.js - 点集合の凸包を構築するJavaScriptライブラリ。
    • S2 Geometry Library - 幾何形状を操作するパッケージ。多くの幾何ライブラリとは異なり、S2は主に、平面の2D地図ではなく球面上に描かれた形状、すなわち球面幾何学を扱うよう設計されている。このため地理データの処理に特に適している。
    • Computational Geometry Unity Library - Unity向けの計算幾何学アルゴリズムのライブラリ。

    会議

    純粋な計算幾何学

    より広範な分野

    ジャーナル

    • arXiv - 計算幾何学に関するarXivの最近の投稿。
    • Elsevier - 計算幾何学の理論的・応用的側面に関する研究の場。
    • Journal of Computational Geometry - 計算幾何学のあらゆる側面における最高品質の独創的研究の出版に専念する国際オープンアクセスジャーナル。

    競技プログラミング

    • HackerEarth - 計算幾何学に関する記事集。
    • TopCoder - 計算幾何学に関する記事集。
    • HackerRank - 計算幾何学を用いるプログラミング問題集。
    • GeeksforGeeks - 幾何アルゴリズムでよく問われる多数の問題と一般的なトピックの実装・解説。

    コース

    公開コース

    • MIT OCW - Nicholas PatrikalakisとTakashi Maekawaが2013年に教えたコース。
    • Udemy - C++で計算幾何学アルゴリズムを実装するコース。
    • edX - 計算幾何学のコース。
    • Brilliant - 計算幾何学の基本概念を扱う練習問題。

    大学コース

    その他

    • The Open Problems Project - 計算幾何学および関連分野における重要な未解決問題を記録することを目的とするプロジェクト。
    • Wolfram - Wolfram言語に実装された計算幾何学アルゴリズムのドキュメント。
    • Matlab - Matlabに実装された計算幾何学アルゴリズムのドキュメント。

    コントリビュート

    貢献を歓迎します。コントリビューションガイドラインを参照してください。