凸包计算
将点集排序(x优先,y优先)
点去重
新建两个点集,分别对应上下边
遍历数据,将上下点集中最后两个点与数据中的点组合
将倒数第二个点分别于遍历出的点和最后一个点连线
通过连线的空间关系取舍点
以上界为例,设倒数第二个点为p,倒数第一个点为a,遍历出的点为b
若bp在ap的顺时针方向,则保留点a,反之则删除点a
将上边界倒序
移除上下点集最后一个点
将上下点集拼接
Last updated
Was this helpful?
将点集排序(x优先,y优先)
点去重
新建两个点集,分别对应上下边
遍历数据,将上下点集中最后两个点与数据中的点组合
将倒数第二个点分别于遍历出的点和最后一个点连线
通过连线的空间关系取舍点
以上界为例,设倒数第二个点为p,倒数第一个点为a,遍历出的点为b
若bp在ap的顺时针方向,则保留点a,反之则删除点a
将上边界倒序
移除上下点集最后一个点
将上下点集拼接
Last updated
Was this helpful?