几何 · 平面里的那些「判定」
计算几何里最常见的几类判定 —— 一个点是否在某个图形内?平面上最近的两点是哪一对?两点之间如何连出一条平滑的曲线?本系列把它们逐个拆解,每页都能拖点、调参、单步观察算法的执行过程。各页主题:判断点是否在多边形内(ray casting)、平面最近点对(分治 O(n log n))、若干矩形的两两重叠检测(sweep and prune,broad-phase 碰撞)、两点间的贝塞尔曲线(如何确定控制点)、Canvas / SVG 圆弧的两套参数(中心参数与端点参数互转)、两个区间之间的 13 种关系(Allen 区间代数,一维上的定性位置关系)、有序三点的顺 / 逆时针判定(叉积符号,orientation test)、用面积最小的(可旋转)矩形框住一堆点(最小外接矩形,rotating calipers)。后续会继续补充:点到线段距离、线段相交、多边形面积等。
阅读本系列需要向量、坐标系等基础。sweep and prune 与 Allen 区间代数 都用到「区间重叠」这一概念,二者从不同角度处理同一件事,可对照阅读。
一个点在不在多边形里？(ray casting)
从 P 朝右发一条射线，数它穿过多边形边界几次——奇数次在内部，偶数次在外部。拖动 P 实时看射线、被穿过的边与交点计数，单步逐边看交点是如何数出的；再用自交的五角星对比 even-odd vs nonzero 两套 fill-rule，并拆解擦过顶点 / 点落在边上的边界情形。
平面里最近的两个点怎么找？
两两比较是 O(n²)；分治法 O(n log n) 的关键在一个几何观察：按 x 中线把点二分、左右各自递归求最近 d，跨越中线的更近对只可能落在宽 2d 的带状区里，且带内每点只需和 y 方向邻近的常数个点比较。拖点实时看最近对，再分五步看中线、半区、带状区与跨界候选，右下角对比分治 vs 暴力的比较次数。
若干矩形里，哪些两两重叠？
游戏物理引擎每帧都要粗筛「哪些物体可能碰撞」。两两测试是 O(n²);sweep and prune 先按左边界排序，扫描线从左往右扫描——某矩形的 left 一旦越过当前矩形的 right，凭排序的传递性可知后面的矩形都不可能相交，整批 break 剪枝。拖动矩形看重叠对实时更新，再单步看扫描线、break 在哪一刻剪掉一批，右下角对比 sweep vs 暴力的测试次数；末尾讲清单轴只是 broad-phase（x 接近 ≠ 真正碰撞）以及在时间相干性下用插入排序维护有序端点这一关键技巧。
两点之间，怎么连一条「好看」的曲线？（贝塞尔与控制点）
难点不在"画曲线"（SVG Q/C 一行即可），而在控制点放在何处。拖动 t 滑块看 de Casteljau 用逐层线性插值描出曲线，那条移动的切线正是控制点所"控制"的对象；再切换两种自动确定控制点的策略——中垂线法向偏移得到对称弧(C = M + k·|AB|·n)，端点水平引出得到节点编辑器里那根 S 形连接线（三次贝塞尔）。
彻底理解 Canvas / SVG 的圆弧（同一段弧，两套参数）
一条弧本质是椭圆的一段。Canvas 的 ellipse() 走中心参数（圆心 + 半径 + 起止角 + anticlockwise），圆心已知、好算；SVG 的 <path A> 走端点参数（只给两端点 + 半径朝向 + large-arc-flag / sweep-flag），圆心要反解。切两种模式拖点调参，看过两点的两个候选椭圆被切成四段弧、两个 flag 各切一刀选出一段；下方实时互转出另一套参数，并演示半径太小时的等比放大。这正是 ECharts 双引擎渲染同一段弧的底层。
两个时间段之间，一共有几种「关系」？
数轴上摆两条线段 A、B，它俩的相对位置恰好有 13 种——这是 Allen 区间代数。拖动整条平移、拖端点改长度，实时报出当前落在哪一种，并点亮 13 关系图谱里对应那格；再点「交换 A↔B」看关系如何翻成它的转置 (converse)。讲清 13 = 6 对转置 + 1 个自反，以及它的内核只是四个端点 A^- A^+ B^- B^+ 的相对大小 (point algebra)，没有几何、纯比较——这套关系正是定性时序推理、日程排程、时态数据库的底层。
圆上有序三点，是顺时针还是逆时针？
把 P₁→P₂→P₃ 连起来这一圈是顺 (CW) 还是逆 (CCW)？整个判定浓缩成一个数：从 P₁ 引出的两向量的叉积符号——它等于三角形有向面积的两倍，正负即方向、0 即共线。拖动圆上三点实时看 cross = vₓw_y - v_yw_x 怎么算出、怎么定向；再切换坐标系，澄清一个常见误区：屏幕的 y 轴向下，叉积变号、规则也变号，看到的顺逆却不变。末尾讲它在凸包、线段相交、多边形朝向、背面剔除里的位置。
怎么用「最小的矩形」框住一堆点？（允许旋转的外接矩形）
检测算法圈出一个倾斜的物体，要用矩形框住它。取 x/y 极值得到的轴对齐包围盒 (AABB) 会多框进大片空白；允许矩形旋转则能贴合物体，得到最小外接矩形 (OBB)——cv2.minAreaRect 算的正是它。靠一条定理（最小矩形必有一边贴着凸包）把无穷朝向收敛成有限候选：让矩形一条边依次贴着每条凸包边、各取一次旋转包围盒，比出面积最小者。拖点实时对比 AABB 与 OBB、单步看面积随朝向变化，右下角报出省下多少空白；末尾讲 rotating calipers 如何把 O(h²) 降到 O(h)，以及它在 OCR 旋转框、物体检测、排样下料、GIS 里的位置。
🔗 相关链接
- Point in polygon · Wikipedia ray casting 与 winding number 两类算法的总览,含擦过顶点等退化情形的处理。
- PNPOLY · W. Randolph Franklin · wrfranklin.org 那段被广泛引用的「7 行 C」point-in-polygon 经典实现,作者本人讲清了半开区间技巧为何能正确处理边界。
-
fill-rule (nonzero / evenodd)
· MDN
对应「点在多边形内」页 even-odd vs nonzero 一节的规范侧:SVG / CSS 如何用
fill-rule在两套「内部」定义之间选择,自交路径填充差异的来源。 - Jordan curve theorem · Wikipedia 「一条简单闭曲线把平面分成内外两块」的拓扑定理 —— 奇偶规则之所以成立的理论根基。
-
Closest pair of points
· Wikipedia
对应「最近点对」页:分治
O(n log n)算法、带状区内「每点 ≤7 邻居」的证明,与随机化线性期望解法。 - Sweep and prune · leanrada.com 「sweep and prune」页出处:从两两暴力逐步推导到 sort & sweep,讲清「排好序后,一个不等式就能整批剪枝」的直觉,并配有可交互的小球碰撞可视化。
- Sweep and prune · Wikipedia 对应「sweep and prune」页:SAP 作为物理引擎 broad-phase 的标准做法、时间相干性 (insertion sort 维护有序端点) 与多轴投影取交。
- JS 实现两点之间的连接曲线 · 张鑫旭 「贝塞尔曲线」页的出处:从连接两个可拖拽 DOM 元素出发,讲解如何用贝塞尔控制点把连线绘制得平滑,含坐标换算与拖动重绘。
- A Primer on Bézier Curves · pomax 对应「贝塞尔曲线」页的交互式参考:de Casteljau、切线、等分、求交、拟合,每个性质都有可拖动的可视化。
- 彻底理解 Canvas/SVG 圆弧算法 · 羡辙 / 知乎 「Canvas / SVG 圆弧」页的出处:对比 Canvas 的 arc / ellipse 与 SVG 的 A 命令,讲清 anticlockwise、large-arc-flag、sweep-flag 各自选哪段弧,以及在 ECharts 双引擎渲染里为何要懂这两套参数的互转。
- SVG arc implementation notes (F.6) · W3C 对应「Canvas / SVG 圆弧」页第三节:端点参数 ↔ 中心参数的完整换算公式 (F.6.5)、半径修正 (F.6.6) 与退化情形,本页画布的换算读数照此实现。
- Allen's interval algebra · Wikipedia 对应「Allen 区间代数」页:13 种区间关系的定义、转置、组合表 (composition table) 与作为约束满足问题的可处理子类。
- Minimum bounding box · Wikipedia 对应「最小外接矩形」页:轴对齐 (AABB) 与任意朝向 (OBB) 的区别,及二维最小面积矩形「必有一边与凸包共线」的定理来历。
-
Rotating calipers
· Wikipedia
「最小外接矩形」页第三节的优化:一对垂直卡尺绕凸包旋转,把逐边重投影的
O(h²)降到O(h),并能顺带求直径 / 宽度。 -
Contour features · minAreaRect
· OpenCV
「最小外接矩形」页的工程出处:
cv2.minAreaRect返回 (中心, 宽高, 角度) 的旋转矩形,OCR / 检测里把斜框摆正的标准一步。