Ahead

10.6.2018
新的章节，从凸包到几何求交

定义

在一组几何物体中找到公共部分
问题主要分4类

1. 判断问题（Determine） 即判定是否有交
2. 计数问题（Count） 计算有多少交点
3. 枚举问题（Enumerate） 枚举交点是那些(在哪里)

4. 构造问题（Construct） 几何物体的公共交本身构造出新的几何物体

   Element Uniqueness （EU）

   元素唯一性判定检测
   排序判定（nlogn）

   Min-Gap问题

   最小空隙问题
   同样可以O（nlogn） 排序求解

   IEU

   元素类型一定是整数

   求交算法

   判定问题
   Interval Intersection Detection（IID）
   以线段为例
   
   朴素：对于所有区间搜索判定O（n^2）

   改进

• 染色
  对于所有的线段，左端点标1，右端点标2
• 排序
  左端点第一关键字，右端点第二关键字

• 扫描
  依次检查相邻的端点，检查他们的Patterns
  结论:如果无交，那么他们的Patterns 一定是1 2 相间 反之不然
  所以时间复杂度降为O（nlogn）
  Segment Intersection Detection （SID）
  朴素枚举 O（n^2）
  关于判断
  ToLeft Text
  4次判断，如果对于两条线段每次的两个结果都为在异侧则相交

  更优的算法（BO算法）

  先了解几个结论

  Separebility

  如果线段在垂直方向上可分开，那么一定不可能相交
  
  所以我们尝试在筛选完后，进行比对
  更近一步，如果两条线段是相交的，当且仅当他们与某一条垂直线相交
  
  所以我们可以采用类似扫描线的想法，我们当前考虑的仅仅是与当前线相交的
  需要注意的是显然我们不可能让扫描线都扫过全部的数，事实上，我们只用处理很少的位置，即只处理端点处和与线段有交点的时刻。
  
  如图，当扫描线处于t时刻是，我们仅仅考虑图中的蓝线，同时，我们可以按高度对他们依次遍历。对于高度，我们定义交点高度越高，那么线段越高。
  很显然的是，这几个点的序列是动态的 ，所以我们需要考虑如何去更新
  而这样的变化仅仅发生在三种状况下

1. 左端点处增加
2. 右端点处减少
3. 交点处高度变化
   
   如图，在L,X,R位置时，序列会发生变化 ，对此将这三种情况统称为事件。

【学习笔记：计算几何基础4】 Geometric Intersection

原文：https://www.cnblogs.com/PiCaHor/p/9748597.html