什么是凸包？

  • 假设一个二维平面上有一堆点，把这些点围起来的多边形就是凸包。

image.png

怎么找凸包？

  • Andrew’s Monotone Chain【O(n*logn)】
  • Graham Scan【O(n*logn)】
  • Chan’s algorithm
  • Quick hull
  • 分治法
  • ……

    Andrew’s Monotone Chain

  1. 先按照横坐标排序image.png
  2. 维护一个stack，存放目前认为是凸包的点image.png
  3. 依次将点放入stack，并检查是否为凸包image.png
  4. 如果破坏了凸包，就把最后一个点拿掉，再试试看image.png

  5. 要分成上凸包和下凸包，下凸包要重复上凸包的做法

    Graham Scan

  6. 先选一个凸包内或者凸包上的点

  7. 其他点按照斜率顺时钟排序image.png
  8. 维护一个stack，存放目前认为是凸包的点image.png
  9. 依次将点放入stack，并检查是否为凸包image.png
  10. 如果破坏了凸包，就把最后一个点拿掉，再试试看image.png
  11. 不用分上下凸包，一次即可完成~image.png

    如何判断凸包？

  • 试用叉积判断三点的连线是顺时针/逆时针旋转

  • 把三个点带入函数

    1. struct point{
    2.   int x,y;
    3. };
    4. int cross(point a, point b, point c){
    5.   return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
    6. }
    • 返回负值表示顺时针
    • 返回正值表示逆时针
    • 返回0表示三点共线