1. 题目背景

我们以一道LeetCode1036.逃离大迷宫来引入。

这道题目给定一个 1000000 x 1000000 （1e6 x 1e6）的网格，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

示例 1：

1
2
3
4
5
6

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [1,3]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

示例 2：

1
2
3
4

输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。

提示：

• 0 <= blocked.length <= 200
• blocked[i].length == 2
• 0 <= xi, yi < 106
• source.length == target.length == 2
• 0 <= sx, sy, tx, ty < 106
• source != target
• 题目数据保证 source 和 target 不在封锁列表内

2. 解题思路

这道题本身并不难，但是其中的思想值得深挖和泛化。

2.1 常规思路：离散化

首先注意到这道题的迷宫地图给的非常大，如果使用uint8哈希表来存储网格的可达性，那么至少需要大约931GB的内存空间，不太现实。然后我注意到题给条件0 <= blocked.length <= 200，这表明封锁列表的长度非常有限（200个元素），因此这一个个的封锁点，相对于整张地图的尺度来说一定是非常稀疏的。

所以我最后采取了 离散化BFS 的方法来解题，在大大缩小了网格尺度的情况下，保证了元素之间偏序关系的稳定，进而保证原来的可达性不被破坏。最后的时间、空间复杂度均为 $O(N^2)$。

2.2 他山之石：交点数奇偶性判定法

2.2.1 方法概述

“交点数判定”的核心思想是：如果两个点（source 和 target）可以在一个包含有限数量障碍的大网格中相互可达，那么任意一条连接这两个点的路径（允许穿越障碍）与每个“包围圈”形成的交点数必须是偶数。这里的“包围圈”指的是由障碍构成的、内部不含其他障碍的区域。

2.2.2 理论基础

• 包围圈：“包围圈”是由障碍物自然形成的区域，区域内部不含其他障碍物。
• 交点数：对于任意一条从 source 到 target 的路径，每遇到一个包围圈，路径要么进入包围圈，要么离开包围圈。这种进入或离开的动作，会留下一个“交点”。

2.2.3 实现步骤简述

由于具体的实现细节比较复杂，这里简要介绍一下实现步骤。

我们需要事先使用并查集来维护障碍物之间的连通性，即哪些障碍物属于同一个包围圈。同时也需要使用并查集维护与障碍物相邻的非障碍物之间的连通性。准备工作做完之后，必须要选择一条从 source 到 target 的简单路径，当然最直观的选择是从 source 水平移动至与 target 同一列，然后垂直移动至 target。之后就可以遍历选定的路径，每当路径上的非障碍物与上一个非障碍物不连通时，表示路径穿过了一个包围圈，记录这样的交点数。如果对于所有包围圈，路径与之的交点数总和都是偶数，那么 source 和 target 之间是可到达的。

2.2.4 优缺点分析

• 优点：此方法的时间复杂度非常优越，为 $O(N)$，无论网格的大小如何，只要障碍物数量固定，算法运行时间基本上是稳定不变的。
• 缺点：实现细节较为复杂，且edge cases飘忽不定，代码很难在短时间内写出来。

3. “射线法”的底层原理

射线法（Ray-casting Algorithm） 是一种在二维平面上进行路径规划的算法。从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在多边形内部，如果有偶数个交点，则在其外部。

需要注意，对于一些特殊的edge cases，射线法得出的结果可能是不对的。比如射线恰好经过某个顶点，那么该点的奇偶性无法确定。

4. 实际工程中的应用：浏览器渲染引擎

网易云音乐的前端技术团队基于canvas自研了一套排版引擎，文章链接：动手打造一款 canvas 排版引擎

这款渲染引擎开源于 GitHub，仓库地址：https://github.com/Gitjinfeiyang/easy-canvas

DEMO地址：https://gitjinfeiyang.github.io/easy-canvas/example

他们开发这款canvas排版引擎的初衷是为了应对业务中频繁遇到的分享活动图片、分享海报图等需求，比如下面这张↓↓↓：

为了实现这类海报图的生成，原有的解决方案要么过于复杂，需要大量的硬编码来手动计算布局和文字换行等问题，在需求频繁变更时难以维护；要么依赖于服务端资源（后端fork nodeJS进程，使用head-less浏览器进行服务端渲染，再将渲染结果传给前端）导致后端CPU、网络带宽压力大；或者是使用现有的前端页面截图框架（如html2canvas），但在兼容性方面存在不足，无法确保客户端不同环境下生成图片的一致性。

基于这些需求，他们计划开发一个canvas排版引擎，能够在不牺牲灵活性和控制力的前提下，能够像在HTML中编写网页一样在canvas环境中高效创建布局。该引擎的设计目标比较完善，可以支持文档流布局、提供声明式的API、实现跨平台兼容（适用于Web和小程序等），并且支持用户交互（响应用户输入事件）。

在开发事件处理器时，遇到了一个问题：如何判定事件点是否发生在元素内？他们寻找了很多种方法，最后决定采用射线法。以被测点（事件发生点） Q 为端点，向任意方向作射线（一般水平向右作射线），统计该射线与多边形的交点数。如果为奇数，Q 在多边形内；如果为偶数，Q 在多边形外。