一种基于三维增量凸壳法的彩色设备色域确定方法

摘要

本发明公开了一种基于三维增量凸壳法的彩色设备色域确定方法，步骤是：在集合S中任意找出四个不共面的点构成四面体；初始化当前凸包的点集C；任取其余各点的一个随机排列，对冲突列表图G初始化；取一个未访问的点pr，并将其插入点集C中；求出点Pr的冲突集合的边界即为地平线；然后把地平线里的每一条边加入该有序表L；对于每一条边e∈L，生成新的三角面f′，如果f′和边e的邻接面f″在同一个平面就把两个面合并，则转末步骤；如果f′和邻接面f″不共面，把面f1和面f2各自的冲突集合求并得到P(e)；对每一个P'∈P(e)都检查f′与P'的冲突关系，可见则加入到图G；删除图G中的相关内容，返回点集C。本发明的方法，步骤简练，结果准确。

主权项

一种基于三维增量凸壳法的彩色设备色域确定方法，其特征在于，按照以下步骤实施：步骤1、在集合S中任意找出四个不共面的点p1、p2、p3、p4，构成一个四面体；步骤2、定义当前凸包的点集C<‑‑CH({p1、p2、p3、p4})，初始化点集C；步骤3、任取其余各点的一个随机排列，即点p5、p6、……、pn，并对冲突列表初始化，令q＝{(pt，f)|f为点集C上的小平面，t>4}，冲突列表简称图G，具体过程是：对于当前凸包CH(Pr)的每一张小的平面f，都要维护第一个子集该第一个子集是由与平面f可见的那些点组成的；反过来，对于每一个点pt(t>r)，也要维护第二个子集Fconflict(pt)，该第二个子集是由CH(Pr)中所有与点pt可见的小平面组成；点p∈Pconflict(f)与平面f发生冲突，这是因为，点p和平面f不可能在凸包中“和平”相处，即一旦有一个点p∈Pconflict(f)加入到凸包中，平面f就必须被删除，因此将Pconflict(f)和Fconflict(pt)称作冲突列表；步骤4、按顺序取p5、p6、……、pn中一个未访问的点pr(r←5to n)，并将其插入点集C中；步骤5、如果点Pr的冲突集合Fconflict(Pr)非空，则从点集C中把Fconflict(Pr)的所有的面都删掉，求出点Pr的冲突集合的边界，即为地平线；初始化有序表L为空，然后把地平线里的每一条边加入该有序表L；步骤6、对于每一条边e∈L，生成从点Pr到e的新的三角面f′；如果f′和边e的邻接面f”在同一个平面，就把两个面合并起来，且冲突列表和邻接面f”一致，则转步骤8；步骤7、如果f′和邻接面f”不共面，定义未加入点Pr之前的凸包的e的两个邻接的面分别为面f1和面f2，把面f1和面f2各自的冲突集合Pconflict(f1)和Pconflict(f2)求并，形成f′的备选冲突集合P(e)＝Pconflict(f1)∪Pconflict(f2)；P'表示相对于f′的点集中的任意一点，对每一个P'∈P(e)，都检查f′与P'的冲突关系，可见则把(P'，f)加入到图G＝G∪(P'，f)，则转步骤8；步骤8、删除图G中的如下内容：1)删除Fconflict(Pr)中所有的平面相对应的结点；2)删除代表点Pr的结点，因为Pr己经在凸包上了；3)删除点Pr和Fconflict(Pr)之间的所有连线；4)更新点集C，得到所需的点集和面集信息，再确定彩色设备的色域。