駆け足で読む計算幾何学入門 第2章 交差

  • 2線分の交差をどう判定するか
  • n本の線分の交差
    • 2線分の組合せが多くなる:取り扱いの工夫が必要
      • 2分探索木を用いた対処
        • 水平・垂直線分の場合
        • 任意方向線分への拡張
  • 応用(2次元表示(グラフィクスが中心))
    • 隠面除去
    • 線形分離・凸多角形の交差
    • 長方形交差