G. Convex Polygon Intersection Detection
数学大学
G. Convex Polygon Inters
计算几何 · 02. Geometric Intersection
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
G. Convex Polygon Inters
计算几何 · 02. Geometric Intersection
Problem Specification
凸多边形相交检测的问题规范：判定两个凸多边形是否相交（含边界接触）。
输入
两个按序给出的凸多边形顶点序列
输出
是否相交的布尔判定
Monotone Partitioning
单调划分：两个凸多边形都可按某方向切成单调链，便于同步扫描。
单调链
沿链一个坐标单调变化的顶点序列
作用
把二维相交判定降为链上的同步推进
Criterion
不相交判据：存在一条分离线使两多边形分居两侧——投影区间不重叠。
分离轴
任一边的法向作为候选分离轴
判定
某轴上投影区间不重叠即不相交
Decrease-And-Conquer
减治式检测：每步排除一条边或一个顶点，逐步缩小待查范围。
推进
按极角或 y 序轮换推进两多边形的指针
终止
发现分离轴或找到交点即停
Example Cases
典型情形：分离、边界接触、一个包含另一个、交错相交四种形态。
分离与接触
仅边界相触也算相交（按规范约定）
包含情形
一个多边形完全在另一个内部，无交点但仍相交
Complexity
复杂度：两多边形边数 m、n 时，同步推进检测为 O(m+n)。
线性
指针各走一圈即判定完毕
对比
优于逐边两两测试的 O(mn)
本节要点
- ✓凸多边形相交检测可 O(m+n)
- ✓分离轴判据：投影不重叠即分离
- ✓四种形态：分离、接触、包含、交错
延伸主题：实现线性相交检测构造包含与接触用例测试
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么凸性让相交检测能降到线性？
参考答案凸多边形的边界方向单调变化，两条边界的相对位置关系不会反复穿越——双指针同步推进时每个指针至多走一圈。凹多边形则可能反复进入退出，线性推进失效。
2同步推进法中两个指针的「步进条件」如何设计？
参考答案比较当前两边的位置关系（如 y 坐标大小）：较低的那条边的指针前移一步。每步都保持「已处理部分不可能产生相交」的不变式，直到发现相交或某指针走完。
3包含情形（一个多边形在另一个内部）为什么对分离轴判定是难点？
参考答案包含时两多边形的所有边都不相交，边测试全部通过「不相交」，容易误判为分离。必须额外检查一个多边形的任一顶点是否落在另一个内部，才能区分「分离」与「包含」。