Graham按极角排序但不用距离作为第二关键字会错的原因
查看原帖
Graham按极角排序但不用距离作为第二关键字会错的原因
324632
Skeleton_Huo楼主2023/8/24 09:25

根据你用来维护凸壳的单调栈的出栈条件,如果是叉积>=0出栈,不按距离排序就很可能将最远点给出栈了,但它是有可能在凸包上的。如果是叉积>0出栈,不按距离排序就会导致所求图形的边可能有重叠(在同一条直线上来回折返)。

2023/8/24 09:25
加载中...