# Voronoi图：基础构造

> IB 数学：应用与解释 HL · IB DP AI HL
> 来源: https://www.owlsprep.com/zh/study/ib-math-ai-hl-u3-voronoi-diagrams-basic-construction/

本子主题介绍Voronoi图的核心结构，讲解利用垂直平分线手动构造Voronoi图的方法，并说明如何识别最近邻区域。我们重点讲解考试中常考的最多含4个站点的构造问题。

**先修:** [线段的垂直平分线](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u3-perpendicular-bisectors/); [二维坐标几何中的距离公式](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u1-distance-formula-coordinate-geometry/)

## 学习目标

- 回忆Voronoi图的定义和核心性质
- 手动构造最多含4个站点的Voronoi图
- 识别最近邻区域和边界点
- 利用垂直平分线求Voronoi边的方程

## 核心定义与基本性质

**Voronoi图** — 将二维平面按照到一组离散输入点（称为站点）的距离划分为多个区域的图。每个区域包含所有到自身对应站点距离比到平面上其他任何站点更近的点。

*例:* 医院分布图中，每个区域表示所有该医院是最近急救机构的位置

在IB考试中，所有Voronoi图都必须满足三条规则：
1. 每条边都是两个相邻站点之间垂直平分线的一段
2. 每个顶点都是三条垂直平分线的交点，且到三个站点的距离相等
3. Voronoi单元内所有点到该单元对应站点的距离都严格小于到其他任何站点的距离

> **info**
>
> IB AI HL考试仅要求手动构造2至4个站点的Voronoi图，更多站点的问题均使用数字化方法求解，这部分内容会在另一个子主题讲解。

**例题:** 三个站点分别位于$A(1,1)$、$B(5,1)$和$C(3,5)$。验证点$(2,2)$位于A对应的Voronoi单元内。

1. 要确定一个点属于哪个Voronoi单元，计算该点到每个站点的距离平方即可（这样可以避免开根号，简化计算）：
2. 到A的距离平方：
3. $$(2-1)^2 + (2-1)^2 = 1 + 1 = 2$$
4. 到B的距离平方：
5. $$(2-5)^2 + (2-1)^2 = 9 + 1 = 10$$
6. 到C的距离平方：
7. $$(2-3)^2 + (2-5)^2 = 1 + 9 = 10$$
8. 由于$d_A^2 < d_B^2$且$d_A^2 < d_C^2$，$(2,2)$到A的距离比到其他任何站点更近，因此它属于A的Voronoi单元。

## 2个和3个站点的手动构造

对于两个站点，构造很简单：唯一的Voronoi边就是连接两个站点线段的整条无限长垂直平分线，它将平面分为两个无限区域。对于三个不共线的站点，你需要构造三条垂直平分线（每对站点一条），它们会交于一个Voronoi顶点。Voronoi边就是垂直平分线从顶点延伸到无穷远的线段。

**例题:** 为位于$P(0,2)$和$Q(4,0)$的两个站点构造Voronoi图，求Voronoi边的方程。

1. 步骤1：计算线段PQ的中点：
2. $$M = \left(\frac{0+4}{2}, \frac{2+0}{2}\right) = (2, 1)$$
3. 步骤2：计算PQ的斜率，再求垂直平分线的斜率：
4. $$m_{PQ} = \frac{0-2}{4-0} = -\frac{1}{2} \implies m_{\perp} = 2$$
5. 步骤3：使用点斜式求直线方程：
6. $$y - 1 = 2(x - 2) \implies y = 2x - 3$$
7. 步骤4：结论：整条直线就是Voronoi边，将平面分为两个区域（分别对应P和Q）。

> **考试提示:** 务必按照题目要求的形式写出Voronoi边的方程（通常是$y=mx+c$或$ax+by+c=0$）。反复检查垂直斜率的计算，这是阅卷中最常见的错误点。

## 4个站点的手动构造

对于四个站点，构造过程遵循相同的核心规则：每条边都是相邻站点之间垂直平分线的一段。你首先在每对相邻站点之间画出垂直平分线，找到它们的交点得到Voronoi顶点，然后只保留构成区域边界的线段即可。

**例题:** 四个站点分别位于$A(1,1)$、$B(5,1)$、$C(1,5)$、$D(5,5)$。构造Voronoi图并求出所有边的方程。

1. 步骤1：求出左右、上下站点对之间的垂直平分线：
2. AB（左右对）的中点是$(3,1)$，AB是水平线，因此垂直平分线是竖直线$x=3$。AC（上下对）的中点是$(1,3)$，AC是竖直线，因此垂直平分线是水平线$y=3$。
3. 步骤2：确认剩余站点对的垂直平分线：所有其他站点对的垂直平分线也都是$x=3$或$y=3$。
4. 步骤3：找到Voronoi顶点：$x=3$和$y=3$交于$(3,3)$，该点到四个站点的距离相等。
5. 步骤4：最终边：Voronoi边是$x=3$上$y>3$和$y<3$的两条射线，以及$y=3$上$x<3$和$x>3$的两条射线，将平面分为四个区域（每个站点对应一个）。所有边的方程为$x=3$和$y=3$。

**概念自测**

测试你的理解：

1. 三站点Voronoi图中，三条垂直平分线的交点叫什么？

   - A. Voronoi站点
   - B. Voronoi单元
   - C. Voronoi顶点
   - D. 垂直交点

   *解析:* 正确。Voronoi顶点到三个站点的距离始终相等。站点是原始输入点，单元是区域。

## 常见错误

- **错误做法:** 求垂直平分线斜率时，只用了原斜率的负数，而不是负倒数。
  - 原因: 很多学生混淆了垂直斜率的规则，导致边的方程错误。
  - 正确做法: 如果原斜率为$m$，那么垂直斜率为$-\frac{1}{m}$。水平线的垂直平分线是竖直线，反之亦然。
- **错误做法:** 即使是3个及以上站点，也将整条无限长的垂直平分线作为边。
  - 原因: 只有构成区域边界的那段平分线才是Voronoi图的一部分。
  - 正确做法: 找到顶点后，去掉垂直平分线中位于Voronoi单元内部的所有部分。
- **错误做法:** 不用计算，而是用视觉估计来将点分配到对应单元。
  - 原因: 靠近边的点看起来经常会误以为离错误的站点更近，而且阅卷老师需要证明过程。
  - 正确做法: 始终要计算该点到每个站点的距离平方，确认它属于哪个单元。
- **错误做法:** 不必要地在非相邻站点之间画垂直平分线。
  - 原因: 这会产生多余的无关线条，导致混淆和顶点识别错误。
  - 正确做法: 先只在明显相邻的站点之间画平分线，再找交点。

## 速查表

| 组成部分 | 定义 | 核心性质 |
| --- | --- | --- |
| 站点 | 图的输入点 | 其单元内所有点到它的距离都比到其他站点更近 |
| Voronoi单元 | 分配给一个站点的区域 | 边界全部由垂直平分线线段构成 |
| Voronoi边 | 两个单元之间的边界 | 两个站点之间垂直平分线的线段 |
| Voronoi顶点 | 三条边的交点 | 到三个相邻站点的距离相等 |
| 两站点图 | 两个无限区域 | 整条垂直平分线是唯一的边 |
| 三站点图 | 三个无限区域 | 一个Voronoi顶点，三条边 |

## 下一步

基础构造是IB AI HL中所有Voronoi应用问题的基础。Voronoi图可用于解决各类实际问题，从新设施选址到地理和商业中的最近服务映射。接下来，你将学习如何求解最大空圆问题，该问题利用Voronoi顶点找到新设施的最优位置，使其离现有站点尽可能远。你还将学习如何在现有Voronoi图中添加新站点，这是考试中常见的拓展回答题。

- [Voronoi图：应用问题](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u3-voronoi-diagrams-application-problems/)
- [微积分](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u4-overview/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/ib-math-ai-hl-u3-voronoi-diagrams-basic-construction/