射线投射算法原理解析

射线的形成原理

射线在这个算法中是隐式的,并不是显式画出来的。理解射线如何形成是关键:

射线定义:

起点: 要检测的点 (x, y)
方向: 向右 → (正 x 轴方向)
长度: 无限长 (从点的 x 坐标延伸到 +∞)

数学表达:

射线上的所有点: (x', y) 其中 x' ≥ x
即: 从 (x, y) 向右无限延伸,y 坐标始终保持不变

可视化:

射线的形成过程:

第1步: 标记要检测的点
            ●────────> 射线方向(向右)
            (x, y)

第2步: 从点向右射出一条无限长的射线
                     边1
                      │
    ●─────────────────┼──────────> 射线
    (x,y)            │交点1

第3步: 与多边形边界相交
           边2  边1  边3
            │   │    │
    ●───────┼───┼────┼──────────> 射线
    (x,y)  │  交点1 交点2交点3

结果: 射线穿过3次 = 奇数 = 点在内部 ✅

算法原理

从点向右射出一条射线
    ↓
数一下射线穿过多边形边界的次数
    ↓
奇数次 = 点在多边形内
偶数次 = 点在多边形外

直观示例

情况1: 点在多边形内
        ╱────╲
       ╱      ╲
      │    ●→→→│→→ 射线穿过1次(奇数) = 在内部 ✅
      │        │
       ╲      ╱
        ╲────╱

情况2: 点在多边形外
   ●→→→│    │
      ╱────╲
     ╱      ╲
    │        │ 射线穿过0次(偶数) = 在外部 ❌
     ╲      ╱
      ╲────╱

代码逐行解释

// 核心逻辑:遍历多边形的每条边
for (let i = 0, j = polygonPoints.length - 1; i < polygonPoints.length; j = i++) {
  // j 是前一个点的索引，i 是当前点的索引
  // 这样可以获取多边形的每条边 (j→i)

  const xi = polygonPoints[i].longitude  // 当前点的经度
  const yi = polygonPoints[i].latitude   // 当前点的纬度
  const xj = polygonPoints[j].longitude  // 前一个点的经度
  const yj = polygonPoints[j].latitude   // 前一个点的纬度

  // 关键判断条件
  if (yi > y !== yj > y && x < ((xj - xi) * (y - yi)) / (yj - yi) + xi) {
    inside = !inside  // 切换点的内外状态
  }
}

条件拆解

① yi > y !== yj > y

检查边是否跨越射线的 y 坐标:

yj ────────────  (第 j 个点)
    ╲
     ╲  ← 边跨越了 y 坐标
      ╲
y ─────●─────── (我们要检测的点)
        ╲
         ╲
yi ───────●── (第 i 个点)

yi > y !== yj > y 为 true ✅

作用: 只检查与射线高度相关的边,跳过不相交的边

② x < ((xj - xi) * (y - yi)) / (yj - yi) + xi

计算边与射线的交点 x 坐标,检查是否在点的右侧:

数学推导:
边的直线方程: (y - yi) / (yj - yi) = (x - xi) / (xj - xi)

解出 x:
x = xi + (xj - xi) * (y - yi) / (yj - yi)

判断: 点的 x 坐标 < 交点的 x 坐标
即: x < 交点x坐标

直观理解:

从点向右射线:
             交点
              │
              ↓
  ●────────────┼────→ (射线)
  ^            │
  │            │
  点的x        边与射线的交点x

点的 x < 交点x ✅ 说明射线确实穿过了这条边

完整流程示例

点: (10, 15)
多边形: [(5,10), (15,10), (15,20), (5,20)]

遍历边:
1. 边 (5,20)→(5,10): 不满足 yi > y !== yj > y (都 ≤ y) → 跳过
2. 边 (5,10)→(15,10): 不满足 yi > y !== yj > y (都 < y) → 跳过
3. 边 (15,10)→(15,20): ✅ 满足条件
   - 计算交点x ≈ 15
   - 10 < 15 → inside = true ✅
4. 边 (15,20)→(5,20): 不满足条件 → 跳过

结果: inside = true (点在多边形内)

登录到 YUJIMAKA