线段相交与点在多边形区域内的经典问题

1、背景

我们在做GIS开发的时候，经常会遇到一些数学的计算，最常见的莫过于判断线段相交以及是否在多边形区域内了，实际场景举个例子：

比如我在地图上画出一个区域（多边形封闭区域），然后产品想让你实现当点击到该区域的时候，能够弹出框来表征该区域的一些信息。这个就是刚才说的多边形区域的点判断。

至于线段是否相交的场景，就更多了，比如路上有根停止线，车子有自己的轨迹，这个时候就可以通过线段相交判断车子往前走是否会穿过停止线？

2、线段相交

2.1、数学原理

2.1.1、数学基础 - 向量叉乘的定义

在二维空间中，我们可以用叉乘（也称为外积）来确定两个向量之间的相对方向。对于二维向量 $\vec{U}$ 和 $\vec{V}$，叉乘是一个标量，而不是向量。具体来说，叉乘定义如下：

$$\vec{U} \times \vec{V} = U_x V_y - U_y V_x$$

这个标量结果表示两个向量的相对方向和面积意义上的“有向面积”。

理解这段话的关键在于以下几点：

1. 叉乘为正：

   • 当 $\vec{U} \times \vec{V} > 0$ 时，$\vec{V}$ 相对于 $\vec{U}$ 是逆时针方向。换句话说，如果我们从 $\vec{U}$ 开始逆时针旋转到 $\vec{V}$，旋转角度是最小的正角。这时，$\vec{V}$ 在 $\vec{U}$ 的左边。

2. 叉乘为负：

   • 当 $\vec{U} \times \vec{V} < 0$ 时，$\vec{V}$ 相对于 $\vec{U}$ 是顺时针方向。如果我们从 $\vec{U}$ 开始顺时针旋转到 $\vec{V}$，旋转角度是最小的负角。这时，$\vec{V}$ 在 $\vec{U}$ 的右边。

3. 叉乘为零：

   • 当 $\vec{U} \times \vec{V} = 0$ 时，$\vec{U}$ 和 $\vec{V}$ 是共线的。这意味着 $\vec{V}$ 与 $\vec{U}$ 平行（可能方向相同也可能相反），但没有形成一个面积。这种情况下，两个向量的旋转角度为零。

举例说明

假设 $\vec{U} = (1, 0)$，表示沿着 $x$ 轴的单位向量。

• 如果 $\vec{V} = (0, 1)$，那么：

  $$\vec{U} \times \vec{V} = 1 \cdot 1 - 0 \cdot 0 = 1$$

  $\vec{V}$ 在 $\vec{U}$ 的左边，需要逆时针旋转 $90^\circ$ 才能从 $\vec{U}$ 旋转到 $\vec{V}$。

• 如果 $\vec{V} = (0, -1)$，那么：

  $$\vec{U} \times \vec{V} = 1 \cdot (-1) - 0 \cdot 0 = -1$$

  $\vec{V}$ 在 $\vec{U}$ 的右边，需要顺时针旋转 $90^\circ$ 才能从 $\vec{U}$ 旋转到 $\vec{V}$。

• 如果 $\vec{V} = (2, 0)$，那么：

  $$\vec{U} \times \vec{V} = 1 \cdot 0 - 0 \cdot 2 = 0$$

  $\vec{U}$ 和 $\vec{V}$ 是共线的，且方向相同。

2.1.2、原理介绍

判断两条线段是否相交可以通过几何和代数的方法来实现。最常用的方法之一是通过计算两条线段的端点位置关系，使用所谓的向量叉乘技术来判断。以下是一个基本的步骤说明：

1. 定义线段和坐标：首先，需要定义每条线段的端点。假设有两条线段 AB 和 CD，其中 A、B、C 和 D 是这些线段的端点。

2. 向量表示：用向量表示这些线段，例如向量 $\overrightarrow{AB}$ ，向量 $\overrightarrow{CD}$ 。

3. 叉乘判断：利用向量的叉乘来判断两个向量的相对方向。叉乘的结果如果是正数，则表示两个向量呈顺时针方向；如果是负数，则表示逆时针；如果为零，则两向量共线。

   • 计算向量 $\overrightarrow{AB}$ × $\overrightarrow{AC}$ ，即检查点 C 相对于线段 AB 的位置。
   • 计算向量 $\overrightarrow{AB}$ × $\overrightarrow{AD}$ ，即检查点 D 相对于线段 AB 的位置。
   • 计算向量 $\overrightarrow{CD}$ × $\overrightarrow{CA}$ ，即检查点 A 相对于线段 CD 的位置。
   • 计算向量 $\overrightarrow{CD}$ × $\overrightarrow{CB}$ ，即检查点 B 相对于线段 CD 的位置。

4. 相交判断：如果点 C 和点 D 在线段 AB 的两侧（即前两个叉乘的结果异号），同时点 A 和点 B 也在线段 CD 的两侧（即后两个叉乘的结果异号），则两线段相交。

这种方法能有效地判断出两条线段是否仅在端点接触或者实际相交。

2.2、js实现

下面是一个使用JavaScript实现的函数，用于判断两条线段是否相交。这个实现基于向量叉乘方法：

1copyfunction crossProduct(px, py, qx, qy) {
2    return px * qy - py * qx;
3}
4
5function isIntersect(A, B, C, D) {
6    // A, B, C, D are points represented as objects with x and y properties
7    const ABx = B.x - A.x;
8    const ABy = B.y - A.y;
9    const ACx = C.x - A.x;
10    const ACy = C.y - A.y;
11    const ADx = D.x - A.x;
12    const ADy = D.y - A.y;
13
14    const CDx = D.x - C.x;
15    const CDy = D.y - C.y;
16    const CAx = A.x - C.x;
17    const CAy = A.y - C.y;
18    const CBx = B.x - C.x;
19    const CBy = B.y - C.y;
20
21    // Calculate the cross products
22    const cross1 = crossProduct(ABx, ABy, ACx, ACy);
23    const cross2 = crossProduct(ABx, ABy, ADx, ADy);
24    const cross3 = crossProduct(CDx, CDy, CAx, CAy);
25    const cross4 = crossProduct(CDx, CDy, CBx, CBy);
26
27    // Check if the points are on opposite sides of the other line
28    if ((cross1 * cross2 < 0) && (cross3 * cross4 < 0)) {
29        return true; // The line segments intersect
30    }
31
32    // Special case: when any cross product equals zero indicating collinear points
33    if (cross1 === 0 && onSegment(A, C, B)) return true;
34    if (cross2 === 0 && onSegment(A, D, B)) return true;
35    if (cross3 === 0 && onSegment(C, A, D)) return true;
36    if (cross4 === 0 && onSegment(C, B, D)) return true;
37
38    return false; // No intersection
39}
40
41function onSegment(p, q, r) {
42    // Check if point q lies on line segment 'pr'
43    if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) &&
44        q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y)) {
45        return true;
46    }
47    return false;
48}
49
50// Example usage:
51const pointA = {x: 1, y: 1};
52const pointB = {x: 4, y: 4};
53const pointC = {x: 1, y: 4};
54const pointD = {x: 4, y: 1};
55
56console.log(isIntersect(pointA, pointB, pointC, pointD)); // Output: true

3、判断点是否在封闭的多边形区域内

判断一个点是否在一个多边形内部可以通过几种不同的方法进行。这里介绍常用的方法：射线法（Ray-Casting Algorithm）。

3.1、射线法（Ray-Casting Algorithm）

射线法基于拓扑学和几何学的概念。其核心思想是从待判断点向任意方向发射一条射线，并统计这条射线与多边形的边相交的次数。根据相交次数的奇偶性来判断点是否在多边形内部：

• 如果射线与多边形的边相交次数为奇数，则点在多边形内部。
• 如果射线与多边形的边相交次数为偶数，则点在多边形外部。

该算法的核心在于奇偶数判断，而不是相交点的判断

3.1.1、数学推导

假设待判断点为 $( P )$，多边形的顶点顺序为 $( V_1, V_2, \ldots, V_n )$。具体步骤如下：

1. 选择射线方向： 一般选择水平向右的射线，即平行于 x 轴正方向。

2. 判断相交： 判断射线与多边形每条边是否相交。考虑多边形的一条边 $( (V_i, V_{i+1}) )$，这里 $( V_{n+1} = V_1 )$：

   • 边的两个端点坐标分别为 $( (x_i, y_i) )$ 和 $( (x_{i+1}, y_{i+1}) )$。
   • 判断条件为：
     • 射线在 $( y_i )$ 和 $( y_{i+1} )$ 之间，即 $( y_i < y_P \le y_{i+1} )$ 或 $( y_{i+1} < y_P \le y_i )$。
     • 射线的 x 坐标 $( x_P )$ 要小于交点的 x 坐标，交点的 x 坐标通过线性插值得到： $$[ x_{\text{交点}} = x_i + \frac{(y_P - y_i) \cdot (x_{i+1} - x_i)}{(y_{i+1} - y_i)} ]$$
     • 判断 $( x_P \le x_{\text{交点}} )$。

3. 统计交点： 对所有边进行上述判断，统计射线与多边形边的相交次数 $( count )$。

4. 判断内部或外部：

   • 如果 $( count )$ 为奇数，点 $( P )$ 在多边形内部。
   • 如果 $( count )$ 为偶数，点 $( P )$ 在多边形外部。

3.1.2、特殊情况处理

• 射线通过顶点：如果射线恰好通过多边形的一个顶点，则该顶点属于相邻的两条边之一，避免重复计数。
• 射线与边平行：如果射线平行并且重合于边，则应当排除这种边，不算作相交。

3.1.3、线性插值

假设我们有一个多边形边的两个端点 $( V_i )$ 和 $( V_{i+1} )$，其坐标分别为 $( (x_i, y_i) )$ 和 $( (x_{i+1}, y_{i+1}) )$。我们需要判断水平射线从点 $( P = (x_P, y_P) )$ 向右延伸时是否与该边相交，并求出相交点的横坐标 $( x_{\text{交点}} )$。

3.1.3.1、线性插值公式推导

假设边 $( (V_i, V_{i+1}) )$ 上的任意一点 $( (x, y) )$ 可以表示为 $( y )$ 对应的 $( x )$ 值，根据线性插值原理：

$$\frac{y - y_i}{y_{i+1} - y_i} = \frac{x - x_i}{x_{i+1} - x_i}$$

这个公式的意义在于，当 $( y )$ 在 $( y_i )$ 和 $( y_{i+1} )$ 之间变化时，$( x )$ 在 $( x_i )$ 和 $( x_{i+1} )$ 之间按同样的比例变化。我们需要求的是射线与边的交点，这意味着 $( y = y_P )$，因为向右水平射线，说明Y轴的值恒定，将 $( y_P )$ 代入公式，可以得到：

$$\frac{y_P - y_i}{y_{i+1} - y_i} = \frac{x_{\text{交点}} - x_i}{x_{i+1} - x_i}$$

从而求出 $( x_{\text{交点}} )$：

$$x_{\text{交点}} = x_i + \frac{(y_P - y_i) \cdot (x_{i+1} - x_i)}{y_{i+1} - y_i}$$

3.2、js实现

下面是一个基于射线法的简单实现，使用水平向右的射线，以JavaScript编写：

1function isPointInPolygon(point, polygon) {
2    let x = point.x, y = point.y;
3    let inside = false;
4    for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
5        let xi = polygon[i].x, yi = polygon[i].y;
6        let xj = polygon[j].x, yj = polygon[j].y;
7
8        let intersect = ((yi > y) != (yj > y))
9            && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
10        if (intersect) inside = !inside;
11    }
12    return inside;
13}
14
15// Example usage:
16const point = {x: 3, y: 4};
17const polygon = [{x: 1, y: 1}, {x: 5, y: 1}, {x: 5, y: 5}, {x: 1, y: 5}];
18console.log(isPointInPolygon(point, polygon)); // Output: true

这段代码会遍历多边形的每条边，并利用算术运算来判断水平射线是否与边相交。每次发现一个有效的交点，它就反转inside的布尔值。如果射线从多边形内部发射，每次穿过边界都会改变其在内部还是外部的状态。

awesome-js同步实现了一份基于经纬度的判断，其原理也是上述说的，只是有普通坐标变成了经纬度坐标，有用到GIS的可以参考一下。