论文部分内容阅读
摘要：为了绘制一幅图像，激光表演器需要的时间依赖于在该图像中线段绘制的顺序和方向。通过重新排列线段方向和顺序，可以大幅降低绘制时间。由于不同等级的激光表演器所标称的每秒绘制点数有所不同，通过降低绘制时间，可以令不同的激光表演器均可有效、完整地展现图像内容。
关键词：激光表演器；四叉树；最近邻点算法
中图分类号：TP391.41 文献标识码：A文章编号：1007-9599 (2011) 20-0000-01
Using Quadtree to Solve Optimization Problems of Laser System Distribution
Yin Changqing,Xu Shaobin
(School of Software Engineering,Tongji University,Shanghai200092,China)
Abstract:In order to draw a picture,laser show devices depends on the time required to segment the image drawn in the order and direction.Direction and by rearranging the order of line segments,can significantly reduce the rendering time.Due to different levels of the nominal laser show devices are different points drawn per second,by reducing the rendering time,you can make different laser show devices can be effective,a complete display of the image content. Keywords:Laser show device;Quadtree;Nearest-neighbor algorithm
一、概述
在激光表演系統中，传递给激光器的每帧图像均为一个点集。每一个点的信息包括了该点的坐标以及在该点处激光器的开、断笔状态：当激光器处于开笔状态时，就会在按照先后顺序传入的两个点之间绘制出一条线段。而将激光从一个点移动至另一个点的动作是由激光器内部的偏振片实现的[1]。我们发现从集合S中找到最高效的路径实际上等价于旅行商问题（Traveling Salesman Problem）。这是一个NPC问题，因此想要在多项式时间内找到最有效的路径是不可行的，然而我们可以采用一些多项式时间的近似方法来得到一条相对高效的路径。本文将介绍一种在大多数情况下都能提高效率的方法，该方法的总处理时间与处理的线段数呈现一种线性的关系。
二、文献综述
与旅行商问题的相似性提示我们可以借鉴它的一些多项式时间的近似解法，两个广为人知的算法是[2]：（1）最近邻点算法：在该算法中，为了构建路径R，我们总是选取最近的未访问点。在最坏情况下，这种方法有可能导致选择的路径长度与最短的路径长度比值随着线段数的增加而快速增大。（2）最小生成树算法：生成一棵最小生成树的时间复杂度是多项式时间级的。通过最小生成树得到的路径长度被证明将不会超过最小路径长度的3/2倍[3]。然而我们希望能为最近邻点算法提供一个在常数时间内找到最近邻的方法，那么在最坏情况下，我们也能够得到一个关于线段数的线性运行时间。
三、四叉树
我们采用四叉树来在常数时间内找到最近邻：一个四叉树对应于将一个屏幕矩形域迭代地进行几何划分，每一个结点最多被分成四个分支。从图像上来说就是将屏幕平均分成四份，每一份为四叉树中的一个结点，对于这一份再进行平均分割，成为子结点，以此类推。
四、具体算法
在描述如何选择最近领点之前，我们首先需要了解如何对四叉树进行插入结点、删除结点的操作，然后我们将展示三种不同的选择最近邻点的方法。
插入算法：当插入线段P1-P2时，点P1、P2分别插入树中，指向P1所有单点结点的指针被加到P2中记录另一端点信息的数组，反之亦然。在插入过程中我们需要考察要插入结点的情况，来确定是仅增加一个单点结点还是扩展四叉树的深度，并将该点和原先已经存在的单点结点插入对应的位置。
删除算法：为了删除线段P1-P2，我们首先从P1中记录另一端点信息的数组中删除指向P2的指针，反之亦然。如果两个数组中的任意一个在删除之后为空，意味着我们接下来必须删除对应的单点结点。若待删除的单点结点只有一个兄弟结点，那么其父结点不再是一个合理的多点结点，我们需要将其替换成待删除结点的兄弟结点，如此依次向上进行操作。
（一）严格最近邻点算法。我们接受一个点P作为参数，返回一个指向距离点P最近的单点结点的指针。给定一个矩形区域后我们可以很轻松地计算该矩形与该点之间的最大距离和最小距离。我们从四叉树的根结点开始向下查找，到达树的每一层级时，我们建立一个在该层很可能含有最近点的多点结点数组。我们同时维护一个指针，它指向当前层级或者更高层级中找到的最近端点。如果该指针为空，那么当且仅当一个矩形到点P的最小距离小于与它在同一层级的多点结点所代表的矩形到点P的最大距离时，我们才将其认为是一个“可能”的候选矩形。如果该指针不为空，那么当且仅当一个矩形到点P的最小距离小于指针所指向的结点到点P的距离时，我们认为它是一个“可能”的候选矩形。为了在层级i+1上确定SP和候选矩形数组，我们只需要考虑层级i上的候选矩形的子结点。（二）近似最近邻点算法。从根结点开始，我们沿着包含点P的矩形所在的分支向下搜索。当这条分支以一个单点结点结束时，我们就把它当作近似的结果；如果这条分支以空指针结尾，我们就往上回溯一层，以该多点结点作为起始进行搜索，找到任意的一个单点结点作为近似结果。（三）混合最近邻点算法。类似于近似最近邻点算法，我们从根结点开始，沿着包含点P的矩形所在的分支向下搜索，如果该分支以一个单点结点结束，那么我们就返回该点指针。如果以空指针结束，我们就从它的父结点开始搜索。与近似最近邻点算法不同，我们不是找到任意在该父结点下的单点结点并将其作为结果，而是将此结点作为根结点，应用严格最近邻点算法。
五、结论
经过实验我们可以得到以下结论，严格最近邻点的速度最慢，但是效率最高；而近似邻点算法速度最快，但是效率值最低。在实际使用当中，我们可以使用混合最近邻点算法搭配上最多共享端点的方法，达到最接近于严格最近邻点的效率值以及近似邻点的速度。
参考文献：
[1]吴毅.激光演示系统软件部分的设计与实现[M].北京邮电大学,2009
[2]Garey,M.R.and Johnson,D.S.Computer and Intractability.W.H.Freeman and Co.,San Francisco,1979.
[3]Dasgupta S.,Papadimitriou C.and Vazirani U.Algorithms.McGraw-Hill Science.2006.
关键词：激光表演器；四叉树；最近邻点算法
中图分类号：TP391.41 文献标识码：A文章编号：1007-9599 (2011) 20-0000-01
Using Quadtree to Solve Optimization Problems of Laser System Distribution
Yin Changqing,Xu Shaobin
(School of Software Engineering,Tongji University,Shanghai200092,China)
Abstract:In order to draw a picture,laser show devices depends on the time required to segment the image drawn in the order and direction.Direction and by rearranging the order of line segments,can significantly reduce the rendering time.Due to different levels of the nominal laser show devices are different points drawn per second,by reducing the rendering time,you can make different laser show devices can be effective,a complete display of the image content. Keywords:Laser show device;Quadtree;Nearest-neighbor algorithm
一、概述
在激光表演系統中，传递给激光器的每帧图像均为一个点集。每一个点的信息包括了该点的坐标以及在该点处激光器的开、断笔状态：当激光器处于开笔状态时，就会在按照先后顺序传入的两个点之间绘制出一条线段。而将激光从一个点移动至另一个点的动作是由激光器内部的偏振片实现的[1]。我们发现从集合S中找到最高效的路径实际上等价于旅行商问题（Traveling Salesman Problem）。这是一个NPC问题，因此想要在多项式时间内找到最有效的路径是不可行的，然而我们可以采用一些多项式时间的近似方法来得到一条相对高效的路径。本文将介绍一种在大多数情况下都能提高效率的方法，该方法的总处理时间与处理的线段数呈现一种线性的关系。
二、文献综述
与旅行商问题的相似性提示我们可以借鉴它的一些多项式时间的近似解法，两个广为人知的算法是[2]：（1）最近邻点算法：在该算法中，为了构建路径R，我们总是选取最近的未访问点。在最坏情况下，这种方法有可能导致选择的路径长度与最短的路径长度比值随着线段数的增加而快速增大。（2）最小生成树算法：生成一棵最小生成树的时间复杂度是多项式时间级的。通过最小生成树得到的路径长度被证明将不会超过最小路径长度的3/2倍[3]。然而我们希望能为最近邻点算法提供一个在常数时间内找到最近邻的方法，那么在最坏情况下，我们也能够得到一个关于线段数的线性运行时间。
三、四叉树
我们采用四叉树来在常数时间内找到最近邻：一个四叉树对应于将一个屏幕矩形域迭代地进行几何划分，每一个结点最多被分成四个分支。从图像上来说就是将屏幕平均分成四份，每一份为四叉树中的一个结点，对于这一份再进行平均分割，成为子结点，以此类推。
四、具体算法
在描述如何选择最近领点之前，我们首先需要了解如何对四叉树进行插入结点、删除结点的操作，然后我们将展示三种不同的选择最近邻点的方法。
插入算法：当插入线段P1-P2时，点P1、P2分别插入树中，指向P1所有单点结点的指针被加到P2中记录另一端点信息的数组，反之亦然。在插入过程中我们需要考察要插入结点的情况，来确定是仅增加一个单点结点还是扩展四叉树的深度，并将该点和原先已经存在的单点结点插入对应的位置。
删除算法：为了删除线段P1-P2，我们首先从P1中记录另一端点信息的数组中删除指向P2的指针，反之亦然。如果两个数组中的任意一个在删除之后为空，意味着我们接下来必须删除对应的单点结点。若待删除的单点结点只有一个兄弟结点，那么其父结点不再是一个合理的多点结点，我们需要将其替换成待删除结点的兄弟结点，如此依次向上进行操作。
（一）严格最近邻点算法。我们接受一个点P作为参数，返回一个指向距离点P最近的单点结点的指针。给定一个矩形区域后我们可以很轻松地计算该矩形与该点之间的最大距离和最小距离。我们从四叉树的根结点开始向下查找，到达树的每一层级时，我们建立一个在该层很可能含有最近点的多点结点数组。我们同时维护一个指针，它指向当前层级或者更高层级中找到的最近端点。如果该指针为空，那么当且仅当一个矩形到点P的最小距离小于与它在同一层级的多点结点所代表的矩形到点P的最大距离时，我们才将其认为是一个“可能”的候选矩形。如果该指针不为空，那么当且仅当一个矩形到点P的最小距离小于指针所指向的结点到点P的距离时，我们认为它是一个“可能”的候选矩形。为了在层级i+1上确定SP和候选矩形数组，我们只需要考虑层级i上的候选矩形的子结点。（二）近似最近邻点算法。从根结点开始，我们沿着包含点P的矩形所在的分支向下搜索。当这条分支以一个单点结点结束时，我们就把它当作近似的结果；如果这条分支以空指针结尾，我们就往上回溯一层，以该多点结点作为起始进行搜索，找到任意的一个单点结点作为近似结果。（三）混合最近邻点算法。类似于近似最近邻点算法，我们从根结点开始，沿着包含点P的矩形所在的分支向下搜索，如果该分支以一个单点结点结束，那么我们就返回该点指针。如果以空指针结束，我们就从它的父结点开始搜索。与近似最近邻点算法不同，我们不是找到任意在该父结点下的单点结点并将其作为结果，而是将此结点作为根结点，应用严格最近邻点算法。
五、结论
经过实验我们可以得到以下结论，严格最近邻点的速度最慢，但是效率最高；而近似邻点算法速度最快，但是效率值最低。在实际使用当中，我们可以使用混合最近邻点算法搭配上最多共享端点的方法，达到最接近于严格最近邻点的效率值以及近似邻点的速度。
参考文献：
[1]吴毅.激光演示系统软件部分的设计与实现[M].北京邮电大学,2009
[2]Garey,M.R.and Johnson,D.S.Computer and Intractability.W.H.Freeman and Co.,San Francisco,1979.
[3]Dasgupta S.,Papadimitriou C.and Vazirani U.Algorithms.McGraw-Hill Science.2006.