1.減而治之(Decrease and Conquer)

插入排序

典型的減而治之算法就是插入排序方法

插入排序法:?在未排序中選擇一個元素，插入到已經排序號的序列中

將凸包也采用減而治之的方法

2.In-Convex-Polygon Test

怎么判斷引入的極點存在于多邊形里面還是外面？

也就是需要區分出6,7,9 和 8。

判斷上述的核心就是判斷引入的點在凸包里面還是在外面

上述過程，先排序，再做二分算法，最后做In-Triangle test。

上述算法的問題：凸包并不是靜態、一層不變的

如果采用插入排序法算法復雜度并不會降低，因為如果采用vector來存在，會存在失效的情況。實際情況復雜度還是n*n

還是采用樸素元素的方法

進而采用 to-left test 判斷一個點是在內部還是外部，算法的復雜度是n*n

3.Support Line

如何將極點增加到現有的凸包上面去？

確定support line

st這一段就是Support Line/tangent

怎么確定s和t定點

4.Pattern Of Turns

s的特征：所有頂點都在它的左側

t的特征：所有點點都在它的右側

5.Exterior/Interior

6. Selection Sort與凸包

采用選擇排序的方法，可以避免已經sorted的部分被打亂掉，但是需要知道根據什么規則來進行排序

采用類似于選擇排序算法的方式，用在凸包尋找極點，縮小查找的范圍

如何在當前已有的極邊查找下一個極點？

可以通過角度來確定下一個極點，但是這種做法并不明智。采用 to-left-test 更加機智

起始點如何確定？

lowest-then-leftmost。 高度最低，然后最左邊的點

實現

確認起點

output Sensitivity

h代表在凸包上需要行駛的步數