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的资料：

image.png
image.png

https://cloud.tencent.com/developer/article/1085866

line-segment intersection （video28）

naive algo

O(n^2) 直接取任意两个点，两两判断是否intersect

sweep-line algorithm 扫描线算法

维护一个数组：order of lines
如果order（次序）变化了，那么会有三种情况：

1. ending end point (points end)
2. starting end point (points just start)

3. 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.

image.png
image.png
image.png
image.png

叉积（cross product）

计算几何学(Computational Geometry)http://mindlee.com/2011/11/27/computational-geometry/

NP

NP-hard\complete 概念理清楚

image.png

Range queries

https://blog.csdn.net/liuqiyao_01/article/details/8478719