convex hull 凸包-video25&video26
凸包算法剖析https://cyw3.github.io/YalesonChan/2016/ConvexHull.html
https://blog.csdn.net/bone_ace/article/details/46239187
有一题是关于convex hull的--寻找凸包
https://leetcode.com/problems/erect-the-fence/description/
cross product的资料：
line-segment intersection （video28）
naive algo
O(n^2) 直接取任意两个点，两两判断是否intersect
sweep-line algorithm 扫描线算法
维护一个数组：order of lines
如果order（次序）变化了，那么会有三种情况：
- ending end point (points end)
- starting end point (points just start)
-
intersect
binary search tree -- 这个data structure用来保存所有sweep line的order，是一个dynamic set。total running time：O(nlogn)
因为这里的data structure需要是：1. sorted list 2. 插入和删除节点的running time 代价小。
如果implement on well-organized binary search tree, such as red black tree, AVL tree. 所有操作，包括insert
image.png
问题：怎么判断两条线段（2 segment）是intersect的？
How to check if two given line segments intersect?
https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
首先，解决概念不清楚的问题
3 orientations of points:
counterclockwise, clockwise and colinear.
叉积（cross product）
计算几何学(Computational Geometry)http://mindlee.com/2011/11/27/computational-geometry/
NP
NP-hard\complete 概念理清楚
