常数工作空间点三角化算法：边可见性线性时间检查实现疑问

核心结论：不用遍历所有三角形，靠几何性质+遍历逻辑搞定 #

这个算法的设计天生适配常数内存限制，可见性检查完全不需要遍历已添加的所有三角形，仅通过叉积运算和gift wrapping march的遍历规则，就能在线性时间内完成，且不占用额外工作空间。

具体实现逻辑 #

所有已处理点的x坐标都≤当前点q_i的x坐标，因此q_i在所有已处理点的右侧。针对gift wrapping过程中遍历到的边e=(a, b)：

• 计算叉积 cross(b - a, q_i - a)：
  • 若结果为正（标准笛卡尔坐标系，y轴向上），说明q_i在边e的左侧（凸壳外侧），此时这条边对q_i完全可见——因为所有已处理点都在e的右侧，不可能存在遮挡。
  • 若结果为负或零，说明q_i在e的右侧或边上，这条边不可见，直接终止遍历。
• gift wrapping的行进逻辑：从前一个点u出发，沿当前凸壳逆时针方向遍历，每一步通过叉积找到下一个点v（确保所有已处理点在u-v右侧），这个过程本身不需要额外存储任何结构。

为什么不用遍历所有三角形？ #

算法的处理顺序（x非降序）和gift wrapping的特性保证了：

1. 所有可能遮挡q_i视线的边，会在gift wrapping遍历中被优先遇到；
2. 一旦碰到第一条不可见边，后续所有边都会被它遮挡，因此可以立即停止检查，无需继续。

整个过程的每一步计算都是O(1)，gift wrapping遍历的总时间是线性的（每个点最多被访问常数次），完全符合常数工作空间+二次总时间的要求。

内容的提问来源于stack exchange，提问作者Koy