1 概念与定义
1.1 网格与坐标系
网格点是在规则网格上由坐标确定的节点。所谓规则网格，通常由固定方向上的等间距线构成：在二维可理解为由水平与竖直等距直线形成的方格；在三维则由相互垂直的等距平面形成的立方格。坐标系用于把每个节点唯一对应到一个点的位置，从而将几何位置转化为可计算的离散数据。
1.2 网格点的表示方式
网格点常以“整数坐标”或“固定间距坐标”形式表示。若网格间距取为 1，则点可用整数向量 \((x_1,x_2,\dots,x_d)\) 表示；若网格间距为 \(\Delta\)，则可写为 \((i_1\Delta,i_2\Delta,\dots,i_d\Delta)\)，其中 \(i_k\) 为整数。这样可以在不丢失几何含义的情况下，方便开展计数与算法操作。
1.2.1 一维、二维与三维情形
一维网格点形如 \(x=i\Delta\)。 二维网格点形如 \((x,y)=(i\Delta,j\Delta)\)，常见记号为 \((i,j)\) 表示网格索引。 三维网格点形如 \((x,y,z)=(i\Delta,j\Delta,k\Delta)\)，对应立方晶格中的格点。
1.2.2 一般维度的记号
在一般维度 \(d\) 中，网格点可写为 \[ (x_1,x_2,\dots,x_d)=(i_1\Delta,i_2\Delta,\dots,i_d\Delta), \] 其中 \(i_1,\dots,i_d\) 为整数。常见做法是先讨论“单位间距”的格点（\(\Delta=1\)），再通过缩放恢复到任意间距。
1.3 网格间距与缩放
改变网格间距等同于对坐标进行统一比例变换。若将 \(\Delta\) 从 \(\Delta_0\) 替换为 \(\Delta_1\)，则所有网格点的位置会整体缩放。对于仅涉及相对位置、拓扑邻接等性质的问题，缩放通常不改变本质结构；而对于距离度量、面积/体积与计数几何量，则需要把缩放带来的因子纳入计算。
1.4 常见相关术语（格点、节点等）
- 格点：常与“网格点”同义，强调“点在格（lattice）上”的离散位置。
- 节点：在图论中表示图的顶点；若一个图的顶点取自网格点，则“节点”与“网格点”可对应。
- 整点：在单位间距下的整数坐标点，常用来强调坐标取值来自整数集合。
- 邻域：指在度量或规则连边下与某一点“相近或相连”的网格点集合。
2 几何刻画
2.1 网格点的邻域结构
邻域结构决定了“从一个网格点到另一个网格点”在模型中是否允许一步移动。不同邻域相当于采用了不同的离散几何规则，直接影响连通性、路径可行性与最短路形状。
2.1.1 4邻域/8邻域（二维）
在二维方格上，4邻域通常把与当前点共享边的点视为相邻（上、下、左、右）。8邻域则在此基础上还包括对角相邻的四个点。二者区别在于：8邻域允许对角“斜走”，会减少路径步数但改变可达模式。
2.1.2 6邻域/18/26邻域（三维）
在三维立方格中，常用的 6邻域把共享面相邻的六个点作为相邻；18邻域加入共享边的相邻点；26邻域进一步把共享顶点的相邻点也纳入。邻域越大，模型的可达性越强，但对“距离近似”的意义也会随之改变。
2.2 距离与度量
在离散空间中，距离度量用于比较网格点间“远近”，并常与最短路径问题绑定。不同度量对应不同的“步行规则”。
2.2.1 曼哈顿距离
曼哈顿距离定义为坐标差绝对值之和：在 \(\mathbb{Z}^d\) 中， \[
| D_1(\mathbf{x},\mathbf{y})=\sum_{k=1}^{d} | x_k-y_k | . |
|---|
\] 它对应“只沿网格轴方向移动”的直观情形，因此与 4邻域（二维轴向走）等模型天然贴合。
2.2.2 欧氏距离
欧氏距离为 \[ D_2(\mathbf{x},\mathbf{y})=\sqrt{\sum_{k=1}^{d}(x_k-y_k)^2}. \] 它更接近连续几何中的直线长度，但在网格步进模型里往往需要把“距离”与“允许的走法”分开理解：欧氏距离可用于评估“空间几何远近”，而邻域规则决定“走法是否合法”。
2.2.3 切比雪夫距离
切比雪夫距离定义为 \[
| D_\infty(\mathbf{x},\mathbf{y})=\max_k | x_k-y_k | . |
|---|
\] 它对应“在所有坐标方向上允许同时推进到某个最大差值”的思想，在某些 8邻域或 26邻域风格模型中具有良好匹配性。
2.3 线段、射线与整数点
网格点与线性几何对象的交集是离散几何的重要主题。线段、射线的离散交点可以看作连续对象在格上的采样结果。
2.3.1 整点共线与可数性直观
两点确定一条直线。若该直线上含有更多网格点，通常意味着方向向量在整数坐标意义下具有“整除结构”，从而使得沿直线的步进会落回整数格点。这样的现象可作为“共线点可数性”的直观来源：并非所有连续方向都会反复穿过格点，只有满足特定整系数条件的方向更可能出现多点共存。
2.3.2 直线经过网格点的条件（概念层面）
在概念层面，判断一条直线是否经过网格点可转化为：直线方程与整数坐标集合的交是否非空。若把直线参数化为起点加倍数的方向向量，则需要该参数使得每个坐标分量都成为整数（或落在给定间距上）。在多数计数问题中，进一步的关键在于交点的“数量结构”而不仅是“是否存在”。
3 组合与计数问题
3.1 区域内的网格点计数
核心问题是：给定某个几何区域（多边形、圆/球的近似、盒形区域等），有多少网格点落在其中。此类问题把几何形状转化为离散计数任务。
3.1.1 多边形/多面体的离散化视角
多边形或多面体可以看作由若干线段或面片围成的集合。研究其中的网格点数量，通常从“边界附近的复杂性”与“内部点的规则性”入手：边界可能穿过格点，导致计数产生不规则项；而内部区域在适当条件下更容易用容斥、递推或体积近似来分析。
3.1.2 边界点与内部点的区分
计数常把网格点分为内部点与边界点两类。内部点指严格位于区域内部的格点；边界点指位于区域边界（线段或面片）上的格点。区分它们能避免把“落在边界上但可能被多次考虑”的情况混进总数，是多种离散几何公式的基础处理方式。
3.2 格点多边形的典型计数对象
常见计数对象包括：
- 仅统计内部格点的数量；
- 统计边界格点的数量；
- 同时统计边界与内部（总格点数）；
- 统计多边形上的格点连线结构（如边上点的分布）。
这些对象在组合几何中常用于描述形状“复杂度”的离散版本。
3.3 相关计数方法的概念分类
3.3.1 递推与容斥的思路
递推常用于把大区域拆成若干较小、形状相近的部分，再利用边界重叠的校正逐步累加。 容斥用于处理“多个条件同时满足”的计数：例如点落入多个半平面或多个子区域的情况。关键是把重叠部分以减法和加法依次剔除或补回，避免重复计算。
3.3.2 面积—点数联系的概念背景
在二维中，一个直观背景是：当网格足够细（或区域尺度足够大）时，区域面积与格点数常呈近似比例关系。更精细的分析会把误差项与边界形状、方向分布联系起来，从而解释为什么边界越“复杂”，计数偏差越明显。
3.4 极值与优化中的网格点
网格点不仅用于计数，也用于离散优化与“最优布局”。
3.4.1 最大/最小距离配置
例如在固定网格内选择若干点，使它们之间的最小距离尽量大（“均匀铺开”）或最大距离尽量小（“聚集成团”）。由于可选点集合离散，这类问题常在搜索空间中出现组合爆炸，因而需要用对称性、度量性质或图模型剪枝。
3.4.2 覆盖与填充的离散模型
覆盖问题常把“覆盖半径”离散化：用距离度量确定某个中心点能够覆盖哪些格点，目标是用尽可能少的中心点覆盖给定区域。填充模型则关心如何在网格中放置对象以满足局部约束（例如避免冲突或保持间距），最终在全局达到可行或最优。
4 图论模型中的网格点
4.1 由网格点构造图
把网格点视为图的顶点，是把几何问题转化为图算法的常见桥梁。
4.1.1 顶点、边与邻接规则
图 \(G=(V,E)\) 的顶点集合 \(V\) 可取为某个区域内的全部网格点。边集合 \(E\) 的生成取决于邻接规则：例如在二维使用 4邻域则连到上下左右；使用 8邻域则再连对角。边可以是无权或带权（权重可取距离、步数代价等）。
4.1.2 有向/无向图的常见建模
无向图适用于对称走法（从 A 到 B 的代价等于从 B 到 A）。有向图则用于表达方向性约束，例如单向通道、风向偏好、代价随方向变化等。即使基础几何是网格点，有向性也会显著改变最短路与可达性分析。
4.2 路径与连通性
在网格图中，路径对应一串相邻网格点的序列。连通性刻画是否存在从起点到终点的可行序列。
4.2.1 最短路径与度量对应
若图的边权与所选度量一致，例如使用曼哈顿风格的代价模型，则最短路径长度与相应距离往往存在直接对应或近似关系。若边权与欧氏距离或其他代价函数一致，则最短路形状也会随之变化。
4.2.2 连通分量与障碍建模
障碍建模常把某些网格点移出顶点集合，或把某些边禁止加入，从而形成障碍物。连通分量由“仍能互相到达”的格点子集组成。通过标记障碍并分析连通分量，可以解决诸如“可到达区域多大”“是否存在通路”等问题。
4.3 网格迷宫与“走格子”问题（轻度梗文化）
在许多趣味题与编程训练中，网格迷宫被反复用作入门：从起点出发，一步步走到终点，看似只是“走格子”，实则训练了路径搜索与贪心策略的边界。
4.3.1 规则差异对解空间的影响
当允许 4邻域时，路线通常更“折线化”；允许 8邻域或更大邻域时，对角移动会显著改变路径数目与最短步数。换句话说，同一迷宫格局，解空间会随着规则变化而重构。
4.3.2 “贪心走法”为何可能翻车（直观讨论）
直观上，贪心策略常选择“看起来更接近终点”的一步。但由于障碍的局部结构，短期看似更优的选择可能把路径封死在死胡同里。贪心会忽略全局可行性，因此在带障碍或需要绕行的场景中容易失败；这类反例是学习最短路与搜索算法（如 BFS、Dijkstra 思想）的常见动机。
5 代数与数论联系（离散视角）
5.1 整数坐标与同余结构
网格点的坐标属于整数格集合时，常可引入同余与余类的视角，把“坐标落在哪类”转为离散分类问题。
5.1.1 网格点的模运算分类（概念层面）
对某个模数 \(m\)，可以把网格点按坐标分量模 \(m\) 的结果分成若干类。例如在二维中，点 \((x,y)\) 可映射到 \((x \bmod m, y \bmod m)\)。这种分类常用于识别周期性结构、简化对称计数或构造约束图。
5.2 生成与格的观点
5.2.1 格点集合的代数描述
在不少场景中，允许的网格点集合可以被描述为若干向量的整数线性组合，即“由生成元生成”。这样可以把几何可达性转化为代数可生成性问题，并用于判断某些点是否能由规则移动得到。
5.2.2 晶格与子格（概念铺垫）
“晶格”通常指在向量空间中由整数线性组合形成的离散点阵。子格对应晶格的子结构，可理解为某种更细或更稀的离散网。子格的指数或余类结构常用于解释计数差异与对称性变化。
5.3 典型不变量的使用方式
5.3.1 可达性/对称性对计数的影响
当网格规则具有平移、旋转或翻转等对称性时，许多计数问题可以按对称类合并计算，减少重复工作。可达性不变量（例如某些模约束下的可达类不变性）能判定某些点永远无法到达，从而把“搜索”变成“分类”。
6 计算与应用
6.1 离散化与采样
把连续空间转换为网格点集合，属于离散化过程。离散化的目标通常是近似几何或物理对象，使其能够用整数坐标进行存储与计算。采样密度（网格间距）越小，精度通常越高，但计算代价也会增加。
6.2 图像/数字几何中的网格点
数字图像可被看作像素网格，像素位置本质上与规则网格上的点索引相对应。许多图像处理操作（连通性分析、边界提取、形状估计）可在网格点模型下理解为对邻域关系与局部结构的处理。
6.3 计算几何中的整数点操作
计算几何中常需要判断线段与网格的交、枚举区域内的整数点、或进行点集与凸包/多边形的离散运算。由于网格点坐标为整数，许多步骤可以避免浮点误差，增强鲁棒性。典型操作包括：检查点是否在边界上、用栅格方式逼近区域、以及按扫描线枚举候选点等。
6.4 数值算法中的网格表示（概念层面）
在数值计算中，网格既用于表示未知量所在的位置，也用于近似导数或积分算子。网格点的排列决定了离散方程的结构稀疏性、误差传播方式以及迭代算法的收敛表现。即便不直接讨论复杂理论，至少在工程层面，“网格如何选、如何编号、邻域如何定义”都与算法效果紧密相关。
7 例题与常见练习框架
7.1 统计某区域内的网格点数量
练习常给定一个简单区域（如矩形、三角形、带斜边的多边形或其缩放版本），要求统计内部点或边界点。解题框架通常包括：确定包含关系、处理边界重合的格点、必要时采用分割或递推。
7.2 判断若干点是否为同一“整数几何关系”
此类题常把几何关系离散化，例如“几点是否共线”“它们是否落在同一直线族的整数参数形式中”等。训练重点是把“几何条件”转化为“整数可检验条件”，并注意边界情形与退化情形（如重复点、垂直/水平特殊情况）。
7.3 在网格图上求最短路/可达性
常见练习给出起点、终点与障碍，用 BFS 或加权最短路思路寻找可行路径或最少步数。框架通常包括：建图（确定顶点范围与邻接规则）、状态转移、以及对不可达情况的识别。
7.4 变体题：不同邻域与不同度量
最后的变体训练要求把规则从 4邻域切换到 8邻域，或在三维从 6邻域切换到更大邻域；同时把代价从按步数计算改为按某种距离度量计算。通过这些对比，学习者能直观看到邻域与度量如何改变最短路与可达结构。