通用线坐标的理论与数学基础

### 通用线坐标的理论与数学基础 在数据可视化和分析领域，通用线坐标（GLC）是一种重要的工具，它能够将高维数据以二维或三维图形的形式呈现出来，帮助我们更直观地理解数据之间的关系。下面将深入探讨GLC的理论和数学基础，包括相关概念的定义、算法介绍以及一些重要性质的证明。 #### 1. 通用线坐标中的图形 在向量代数的框架下，通用线坐标有其独特的定义和表示方式。 - **坐标类型** - **世界坐标**：$W_1, W_2, \cdots, W_n$ 是给定任务的 $n$ 维坐标，代表 $n$ 维对象的各种属性，如质量、长度等。 - **视口坐标**：是二维屏幕窗口内的坐标，用 $U_1, U_2$ 表示。每个坐标 $W_i$ 由其值的区间 $[o, e]$ 定义，其中 $o$ 是原点值，$e$ 是终点值。 - **归一化坐标**：$X = [0, 1]$ 是坐标 $W = [o, e]$ 的归一化形式，其中 $o$ 映射到 $x = 0$，$e$ 映射到 $x = 1$。 - **反转归一化坐标**：是坐标 $X$ 的一种特殊形式，其中 $e$ 映射到 $x = 0$，原点 $o$ 映射到 $x = 1$。 - **否定归一化坐标**：$\neg X$ 是坐标 $X$ 的否定形式，其中 $x \in X$ 映射到 $1 - x$，但不改变原点 $o$ 和终点 $e$ 的位置。 - **定位坐标**：是位于视口坐标 $(U_1, U_2)$ 中的坐标，原点和终点分别映射到二维点 $O = (o_1, o_2)$ 和 $E = (e_1, e_2)$。可以用三元组 $<O, E, L>$ 表示，其中 $L$ 是 $O$ 和 $E$ 之间的直线（直线段或曲线）。 - **定位向量**：对于标量值 $x$，在坐标 $(U_1, U_2)$ 中的定位向量 $x$ 是一个有序的二维点对 $q_1 = <q_{11}, q_{12}>$，$q_2 = <q_{21}, q_{22}>$，满足 $\|q_1 - q_2\| = |x|$。在算法 1 中，每个 $n$ 维点 $x = (x_1, x_2, \cdots, x_n)$ 被映射到 $n$ 个定位向量 $x_1, x_2, \cdots, x_n$。 - **坐标关系** - **并置坐标**：$X_i$ 和 $X_j$ 满足 $<O_i, E_i, L_i> = <O_j, E_j, L_j>$。 - **水平并置坐标**：$X_i$ 和 $X_j$ 满足 $<O_i, E_i, L> = <O_j, E_j, L>$，且 $O_i = O_j = (o_{i1}, o_{i2})$，$E_i = E_j = (e_{i1}, o_{i2})$。 - **垂直并置坐标**：$X_i$ 和 $X_j$ 满足 $<O_i, E_i, L> = <O_j, E_j, L>$，且 $O_i = O_j = (o_{i1}, o_{i2})$，$E_i = E_j = (o_{i1}, e_{i2})$。 - **径向坐标**：$X_i$ 和 $X_j$ 满足 $O_i = O_j$ 且 $E_i \neq E_j$。 - **图构建算法**：有多种将 $n$ 维点 $x = (x_1, x_2, \cdots, x_n)$ 映射到二维定位坐标集 $\{X_i\}$ 的算法，这些算法被称为图构建算法。 - **算法 1（GLC - B）**：在二维或三维中构建图 $x^*$，将其作为有向边（箭头、向量）的集合。每个边位于相应的坐标 $X_i$ 上，从该坐标的原点开始，到 $X_i$ 上的点 $x_i$ 结束。该算法构建的图的边可能是不相连的。 - **算法 2（GLC - PC）**：通过连接 $X_i$ 上的 $x_i$ 位置和 $X_{i + 1}$ 上的 $x_{i + 1}$ 位置来构建图 $x^*$，从 $i = 1$ 开始，到 $i = n$ 结束。这是对平行坐标中算法的推广。 - **算法 3（GLC - SC1）**：将每个向量 $x_{i + 1}$ 的起点移动到向量 $x_i$ 的终点。这是对星坐标中算法的推广。 - **算法 4（GLC - CC1）**：在每对坐标 $(X_1, X_2)$，$(X_3, X_4)$，$(X_5, X_6)$ 等中创建点 $P_1, P_2, P_3$ 等，并连接这些点形成有向图。这是对 CPC 算法的推广。 - **算法 5（GLC - CC2）**：结合了正交并置配对坐标算法和算法 3 的思想，将下一个向量移动到前一个向量的终点。 - **算法 6（GLC - SC2）**：将向量 $x_2$ 的终点移动到向量 $x_1$ 的终点，并将每个其他向量 $x_{i + 1}$ 的起点移动到向量 $x_i$ 的终点。这是对星坐标中算法的修改。 这些算法在无损表示 $n$ 维点 $x$ 时所需的点数和边数不同，具体如下表所示： | 算法 | 点数 | 边数 | | ---- | ---- | ---- | | 算法 1 | 12 | 6 | | 算法 2 | 6 | 5 | | 算法 3 和 6 | 7 | 6 | | 算法 4 和 5 | 3 | 2 | 从表中可以看出，算法 4（GLC - CC1）所需的点数和边数大约是算法 1 - 3 的一半，这从人类认知的角度来看是一个重要的优势，因为它简化了肉眼发现模式的过程。 #### 2. 图构建算法的步骤和性质 下面详细介绍部分图构建算法的步骤和相关性质。 - **算法 1（GLC - B）** 1. 在二维坐标 $(U_1, U_2)$ 中创建 $n$ 个定位线性坐标。 2. 选择一个 $n$ 维点，例如 $(7, 5, 6, 5, 6, 2)$。 3. 对于每个 $i$（$i = 1:n$），在坐标 $X_i$ 中定位值 $x_i$，并定义从 $X_i$ 的原点 $O_i$ 出发、长度为 $x_i$ 的 $n$ 个向量 $x_i$。 - **算法 2（GLC - PC）** 1. 应用基本算法 GLC - B 为给定的 $n$ 维点 $x$ 构建 $n$ 个定位线性坐标和向量 $x_1, x_2, \cdots, x_n$。 2. 赋值 $P_1 = O_1 + x_1$，$P_2 = O_2 + x_2$，$\cdots$，$P_n = O_n + x_n$。 3. 连接点 $P_i$ 形成图：$P_1 \to P_2 \to \cdots \to P_{i - 1} \to P_i \cdots \to P_n$。 **性质 1**：如果所有坐标 $X_i$ 不重叠，那么 GLC - PC 算法提供任何 $n$ 维点 $x$ 到二维有向图 $x^*$ 的双射 1:1 映射。 **证明**：不重叠确保为每个 $n$ 维点 $x$ 获得 $n$ 个唯一的二维点 $x_1, x_2, \cdots, x_n$。接下来，GLC - PC 通过图 $x^*$ 中的有向边重现值 $(x_1, x_2, \cdots, x_n)$ 的顺序，这使得在有二维向量 $x_1, x_2, \cdots, x_