凸包计算

  • 将点集排序(x优先,y优先)

  • 点去重

  • 新建两个点集,分别对应上下边

  • 遍历数据,将上下点集中最后两个点与数据中的点组合

  • 将倒数第二个点分别于遍历出的点和最后一个点连线

  • 通过连线的空间关系取舍点

    以上界为例,设倒数第二个点为p,倒数第一个点为a,遍历出的点为b

    若bp在ap的顺时针方向,则保留点a,反之则删除点a

  • 将上边界倒序

  • 移除上下点集最后一个点

  • 将上下点集拼接

Last updated

Was this helpful?