文档介绍：计算机位图的快速凸包算法
l訇似
计算机位图的快速凸包算法
Researchonthequickconvexhullalgorithmofthecomputerbitmap
陈辉
CHENHui
(廊坊师范学院国有资产管理处,廊坊065000)
摘要:凸包问题不仅是实际应用的中心问题之一,人们对此做出了很多的工作,从理论上证明了凸包
算法的最低复杂度是O(nlogn),,
因为它的横坐标和纵坐标都是整数,对于这种特点的点集,本文采用一种特殊的快速凸包算
法,使得此类问题的复杂度下降到了0(n)的程度,从而极大的加快了计算机位图凸包算法的
复杂度.
关键词:凸包问题;计算机位图;凸包加速算法
中田分类号:TP312文献标识码:A文章编号:1009—0134(2012)Ol(I-)一0102一O3 Doi:.1009-(E).32
1凸包问题广泛的应用背景
凸包问题不仅是实际应用的中心问题之一,
而且也是求解计算几何中提出的许多表面上不相

模式识别u】,图像处理f2】,图形学口和人工智能以
及材料切割和分配等方面的许多实际问题都可以
,点集凸包,尤其是关于平面点集凸包的研究引起了有关学者研究的主要对象之一.
2凸包的研究现状简介
关于凸包的研究,从凸包的问题提出到现在一
几何的基本问题之一,人们对此做出了很多的工作,从理论上证明了凸包算法的最低复杂度是 O(nlogn)】,并且提出了很多好的算法,这些算法都达到了理论上的复杂度下限O(nlogn)】.如后面提到的Graham算法,和北大的教授周培德先生提出的Z,.算法和Z3_2[8] 和最坏情况下的性能相同,即都是O(nlogn). 3本文中的定义
定义1设P是平面上任意一点, 的横坐标,.
定义2设S={P(1),P(2),…,P(n))是平面
上n个点的集合,S的一个凸包是平面上包含S的最小凸域的边界.
定义3计算机的图形是以点阵的方式实现的,我们称其中的一个点为一个像素.
定义4对于像素的数量有限的点集,其最大可能的横坐标定义为max(x),最大可能的纵坐标定义为max(y),最小横坐标位min(x),最小纵坐标为min(y).
定义5对于所有的点集中的点,采用某种算法挑出来的可能是凸包的点称为中间点.
说明:1)基于以上假设,计算机中当显示
精度为640X480的时候,min(x)=1,min(y)=1,
max(x)=640,max(y)=480. 2)对于计算机的显示来说,计算机显示的每 ,. 4基本方法概述
对于所有的计算机图形中的点,因为它的横坐标和纵坐标都是整数,而且一般来说计算机的现实精度限制了计算机图