凸Polygon和相交定义
本节只讨论凸Polygon的问题，不涉及凹Polygon.
相交包含了边相交和完全包含。
凸Polygon相交的两个问题
Detection(检测)
判断两个凸Polygon是否相交，至于相交部分是什么不关心.
Construction(构造)
求出两个凸Polygon具体相交部分(包含了检测是否相交)
凸Polygon 相交检测(Detection)
dobkin and kirkpatrick's algorithm 算法
Monotone Partitioning(单调划分)
任意一个多边形都可以分解为两条多边形链
单调划分链下判断两个Polygon是否相交的条件描述
Decrease-And-Conquer
总体上利用BinarySearch的思路对构成多边形的两条划分链求解.
1. 如果两条划分链最大边数 < 2, 则直接求两条划分链是否相交
2. 不满足1以后则求出两条划分链的中间边(median edge)-ep和eq
根据ep和eq的情况分情况(很多情况，下面举例经典情况)讨论结果:
[1]相交
[2]进一步递归求解
算法复杂度
本质上是BinarySeach，遵循O(logn). 涉及到两个多边形，假设边数量分别为N和M. 算法复杂度在O(log(N + M))
凸Polygon 相交Construction(构造)
EdgeChasing边追赶算法(O'Rourke's algorithm)
算法案例流程
决定e, f边的具体迭代(追赶)策略
PlaneSweeping(平面扫描)
SweepLineStatus
观察可知任意一条直线与两个凸多变形最多四个交点，SLS不需要用到平衡二叉树来表示，是普通数组就行。
EventQueue
P和Q的最左边点是事件的开始, 由于多边形线段是相连的, 上一条线段退出意味着下一条线段开始。每次最多判断四条边相交。
算法复杂度: O(log(N + M))， 和EdgeChasing边追赶算法复杂度一样.
没有边界的凸多变形相交构造(unbounding convex plygon 相交construction)
后续有待补充
参考资料
[1]清华计算几何 P83 - P95
