几何 · 平面里的那些「判定」

计算几何里最常见的几类判定 —— 一个点是否在某个图形内?平面上最近的两点是哪一对?两点之间如何连出一条平滑的曲线?本系列把它们逐个拆解,每页都能拖点、调参、单步观察算法的执行过程。各页主题:判断点是否在多边形内(ray casting)、平面最近点对(分治 O(n log n))、若干矩形的两两重叠检测(sweep and prune,broad-phase 碰撞)、两点间的贝塞尔曲线(如何确定控制点)、Canvas / SVG 圆弧的两套参数(中心参数与端点参数互转)、两个区间之间的 13 种关系(Allen 区间代数,一维上的定性位置关系)、有序三点的顺 / 逆时针判定(叉积符号,orientation test)、用面积最小的(可旋转)矩形框住一堆点(最小外接矩形,rotating calipers)。后续会继续补充:点到线段距离、线段相交、多边形面积等。

阅读本系列需要向量、坐标系等基础。sweep and prune 与 Allen 区间代数 都用到「区间重叠」这一概念,二者从不同角度处理同一件事,可对照阅读。

concept · point in polygon

一个点在不在多边形里？(ray casting)

从待判点朝右发一条射线，数它穿过多边形边界的次数：奇数在内、偶数在外。再对比 even-odd 与 nonzero 两套填充规则。

concept · closest pair

平面里最近的两个点怎么找？

分治求平面最近点对：按 x 切半、递归求解，再只检查中缝带内的常数个邻居，总时间 O(n log n)。

concept · sweep and prune

若干矩形里，哪些两两重叠？

按左边界排序后扫描，某矩形的左边界一旦越过当前矩形的右边界，其后全部不可能相交，整批剪枝。单轴扫描只是 broad-phase。

concept · bézier curve

两点之间，怎么连一条「好看」的曲线？（贝塞尔与控制点）

de Casteljau 的逐层线性插值给出贝塞尔曲线，倒数第二层给出切线方向；再看只给两端点时控制点如何自动生成。

concept · elliptical arc

彻底理解 Canvas / SVG 的圆弧（同一段弧，两套参数）

同一段椭圆弧的两套参数：Canvas 给圆心与起止角，SVG 给两个端点加两个 flag。两套之间的换算与三类退化情形。

concept · Allen's interval algebra

两个时间段之间，一共有几种「关系」？

两个区间的相对位置恰好有 13 种：6 对互为转置，加上 equals 自反。四个端点的比较即可定出是哪一种。

concept · orientation test

圆上有序三点，是顺时针还是逆时针？

二维叉积的符号决定三点是顺时针、逆时针还是共线。屏幕坐标 y 向下会把这个符号整体翻过来，是最常见的坑。

concept · minimum-area enclosing rectangle

怎么用「最小的矩形」框住一堆点？（允许旋转的外接矩形）

允许旋转的最小外接矩形必有一边贴着凸包，于是无穷朝向收敛成有限候选：让矩形依次贴每条凸包边，比出面积最小者。

🔗 相关链接

• 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 / 检测里把斜框摆正的标准一步。