一种平缓变化的RGB三原色遍历算法.pdfVIP

一种平缓变化的 RGB 三原色遍历算法 摘 要 本文借助图论中 Hamilton 圈的概念，实现了一个遍历全体RGB 三原色的算法。该算法具有如下特征： 1）在一个遍历循环中，经过所有的可能的三原色，并且变化的过程是平缓的，不会让人感觉到颜色的明显跳跃； 2 ）算法程序代码比较容易实现，且比较简洁。 关键词 彩色空间 RGB 三原色 Hamilton 圈 遍历 中图法分类号：TP391 A Smoothly Changing Algorithm of Traversing RGB Three Primary Colors WANG Chao （College of Software, Nankai University, Tianjin 300071 ） Abstract By the help of Hamilton cycle in graph theory, we propose a traversal algorithm of RGB three primary colors in this paper 。This algorithm has the following characteristics: 1) all colors will be meeted in one traversal loop. And the changing is so smooth that human can’t see the obvious jump of colors; 2) The code of the algorithm is easy to implemented and is relatively brief. Keywords color space, RGB three primary colors, Hamilton cycle, traversal 1 引言 在计算机图形学中[1～3] ，经常涉及到各种颜色的平缓变化。比如Media Player 的可视化效果显示 中，音乐播放的同时背景图中颜色会平缓的变化，这种颜色的平缓变化不会产生让人感觉晃眼或者 察觉颜色的明显跳动。在三维动画设计中，有时也要用到很多颜色之间的渐变。因此如何产生不会 大幅度跳跃的RGB三原色遍历算法，就成为一个很有意义的问题。 实际上，平缓变化的RGB三原色遍历相当于一个256×256×256个顶点的立方体方格图的遍历问 题。借助图论的术语，其实可以看作是在一个立方体方格中寻找一个Hamilton圈的问题。我们将从 理论上证明，这个问题是肯定有解的。但是考虑到计算机实现，不能使用表述过分复杂的算法，以 避免代码过分冗长的问题，因此如何找到尽可能容易描述的Hamilton圈构造算法，还是一个值得关 注的问题。 2 Hamilton 圈问题 对于平面上的m ×n方格，我们可以将其所有的交叉点视为简单图的顶点，连接两个交叉点之间 的短线看作是这两个顶点之间的边，这样我们就将平面上的m ×n方格看作是一个具有m ×n个顶点的 简单图，我们称之为m ×n 的方格图。如果一个简单图存在一个由边组成的圈包含了图中的所有顶点， 则此圈就是这个图的Hamilton 圈。如果一个简单图存在一个由边组成的路包含了图中的所有顶点， 则这条路就是这个图的Hamilton路。关于这些术语的详细介绍，可参见[4,5]。Hamilton 圈问题是指 确定一个简单图是否含有Hamilton 圈的问题。我们遍历m ×n方格图中的每一个顶点就对应于寻找m ×n方格图中Hamilton 圈的问题。可以证明如下定理： 定理1：设A 是m ×n 的方格图，则A 中有Hamilton圈当且仅当m, n 中至少有一个是偶数。[6] 证明：先证明必要性。使用反证法，假设m, n全是奇数，那么A 就有mn奇数个顶点。根据定理假设A 含有一个Hamilton 圈，不妨假定这个Hamilton 圈从(0,0)处出发，很容易看出Hamlton 圈的每一步都是 从一个顶点走到与它相邻的一个顶点，后者的坐标之和与前一个顶点相比必然恰好相差1，那么当沿 着Hamilton 圈回到终点时，可以得出最终的终点坐标之和与起点坐标之和应该相差mn个1或者－1之 和，这显然是一个奇数，与起点和终点都是(0,0)矛盾，所以A 不含Hami