计算机科学论坛--[原创]"基于正四面体中心投影的凸多面体的精确Minkowski和算法"[讨论]

目前正在研究一个:"基于正四面体中心投影的凸多面体的精确Minkowski和算法"
具体内容如下:
也可以下载附件:基于正四面体中心投影的凸多面体的精确Minkowski和算法.doc

<转帖者请注名:来源于计算机科学论坛>

1   基于正四面体中心投影的凸多面体的精确Minkowski和算法
1.1   正四面体中心投影
为得到凸多面体的倾斜图,我们引入单位球面,其球面半径为1.凸多面体的每个面对应一条单位法向量,使所有面的单位法向量的起始点处在一个公共原点,即处在单位球面的球心,由于单位法向量的长度均为1,故其末端点均处在单位球面上,则凸多面体的每个面被映射为单位球面上的点,在这里我们称这些映射点为面点[4].凸多面体的边e映射为单位球面上的弧,即测地线段,该弧为单位球面上大圆的劣弧,它连接着单位球面上的两个面点,这些面点分别为边e的两个邻接面所对应的映射点,在这里我们称这些弧为边弧[4],它的长度为边e的两个邻接面所构成的两面角补角的大小.凸多面体的顶点v映射为单位球面上的域,该域的边界为顶点v的邻边所对应的边弧,该域的边界顶点为顶点v的邻面所对应的面点,在这里我们称这些域为点域[4].按照上述映射规则,我们能够得到凸多面体的倾斜图,即单位球面映射.
1.1.1   正四面体中心投影
定义1[7]. u为单位球面S2上的点,起始点位于单位球面球心o处的射线ou与单位球面的支撑超平面的交点为点u的中心投影,记为u.
在给出凸多面体的正四面体中心投影之前,我们可以做一个影子实验,取一个透明的球面并在其表面画几条大圆的弧,然后在球面的中心处放一光源,那么我们能够看到球面上大圆的弧在墙壁上所形成的阴影,所有这些阴影都是直线段.同理,我们取单位球面的外切正四面体,此时单位球面的球心与外切正四面体的中心重合,按照定义1,我们得到单位球面上的面点在正四面体表面的中心投影,边弧在正四面体表面的投影为一条或多条连接的直线段,点域在正四面体表面的投影为在一个面或多个相邻面上的凸多边形.依照上述规则,我们可以得到凸多面体的正四面体中心投影.如图1所示,四面体的正四面体中心投影及正四面体中心投影的展开图.
对于正四面体中心投影,许多需要特殊处理的退化情况都可以归结为一般情况,例如,凸多面体某个面f映射为顶点v,点v处于正四面体的棱上,或正四面体的某一顶点位置,在求和过程中,顶点v如同其它的内部顶点一样能够得到有效地处理.一个凸多面体的两个邻接面分别平行于另外一个凸多面体的两个邻接面,在正四面体中心投影上表现为两条线段的重叠,对于这种退化情况,本文给出的算法也能够有效地处理.

1.1.2   坐标系的选取
正四面体中心投影的每个面由三个顶点和三条边进行初始化,这些顶点和边构成了一个正三角形.为了有效地得到凸多面体Minkowski和的精确值,我们必须恰当地选取坐标系,把三维空间的问题转换到二维空间进行解决.我们取正四面体的中心为3维坐标系oxyz的原点o,取正四面体的任一顶点v与原点o的连线为z轴方向,其正向指向顶点v, xoy面平行于与顶点v相对的面,在这里我们称该面为正四面体的底面,其余的三个面为正四面体的侧面,x轴与底面的一边平行,x轴、y轴、 z轴满足右手定则,如图2所示.我们取任一侧面的中心为与该面相对应的3维坐标系oxyz的原点o,取该面的任一顶点与中心的连线为y轴方向,其正向指向该顶点,取y轴的右侧为x轴正向,x轴、y轴、z轴满足右手定则,按照上述规则,我们为每个侧面定义了相应的3维坐标系oxyz.为了统一我们取分别与三个侧面相对应的坐标系oxyz中y轴的正向同3维坐标系oxyz中z轴的正向趋向相同,取正四面体的底面中心为相应的3维坐标系oxyz的原点o,其中x轴、y轴分别与3维坐标系oxyz的x轴、y轴平行,并且x轴与x轴方向相反, x轴、y轴、z轴满足右手定则,如图2所示.我们把与z轴垂直的xoy面看作为2维坐标系oxy所确定的面,即取z= 0.通过空间坐标变换,我们能够得到正四面体各面上的点在3维坐标系oxyz下的3维坐标与2维坐标系oxy下的2维坐标之间的转换关系.
设p为侧面ACD上的点,p在3维坐标系oxyz下的坐标为(x,y,z),在与面ACD相对应的新坐标系oxyz下的坐标为(x,y,z),则这两个坐标之间的对应关系为:
; ;
这里取z= 0, (x,y)为点p在面ACD上2维坐标.
同理,设p为侧面ABC上的点,p在3维坐标系oxyz下的坐标为(x,y,z),在相应的新坐标系oxyz下的坐标为(x,y,z),则这两个坐标之间的对应关系为:
; ;
取z= 0, (x,y)为点p在面ABC上2维坐标.
设p为侧面ABD上的点,p在3维坐标系oxyz下的坐标为(x,y,z),在相应的新坐标系oxyz下的坐标为(x,y,z),则这两个坐标之间的对应关系为:
; ;
取z= 0, (x,y)为点p在面ABD上2维坐标.
设p为底面BCD上的点,p在3维坐标系oxyz下的坐标为(x,y,z),在相应的新坐标系oxyz下的坐标为(x,y,z),其中坐标x,y与坐标x,y之间的关系为:
;
通过上文给出的坐标之间的对应关系,我们可以把三维空间的问题转换到二维空间进行解决.
双重连接边表 [7]数据结构是一种基于边的表示方法,但是顶点和面的信息也包含在内,每条无向边都由两条相对方向的半边表示,每条半边都与它左边的面相关联.这种表示方法有三个记录,分别是顶点记录、半边记录、面记录,其中我们取顶点的记录为:顶点的坐标、以该顶点为源点的任一关联半边;取半边的记录为:半边的源点、半边的孪生半边、半边的后继半边;取面的记录为:该面的任一边界半边.通过采用DCEL,我们可以得到正四面体中心投影各个三角形面内顶点、半边、面(点域在正四面体表面的投影)之间的关联关系.
正四面体中心投影的四个三角形面均为平面凸剖分.各平面剖分中的顶点、半边、面都存储着一些附加信息,对于求和过程这些附加信息是十分必要的,其中我们取顶点的附加信息为:(1)该顶点是否为真实元素(即是否存在凸多面体的小面映射为该顶点),(2)该顶点是否处于正四面体的顶点位置、或正四面体的棱上或正四面体的三角形面内;半边的附加信息为:该半边是否为真实元素(即是否存在凸多面体的棱映射为该半边);面的附加信息为:映射为该面的凸多面体顶点的坐标.
本文取0、1、2、3四个ID号标识正四面体的各个三角形面,并取0、1、2三个ID号标识每个三角形面的三个角顶点,在每个三角形面内取y轴正向所指顶点的ID号为0, x轴正向所指顶点的ID号为1, x轴负向所指顶点的ID号为2.对一个给定顶点的关联面进行遍历时,若该顶点处于三角形面内,可以直接通过DCEL提供的关联关系顺时针遍历该顶点的关联面,若该顶点为边界顶点(映射点恰好处于正四面体的某一顶点位置上),则可以通过表1中给出的循环表顺时针遍历该顶点的关联面.
Table 1  Cyclic table of corner vertices in triangle facets
表1  三角形面内角顶点的循环表
各面ID号与3维坐标系oxyz中坐标的关系每个面的角顶点ID号
0 1 2
ID号 3维坐标各面ID号角顶点ID号各面ID号角顶点ID号各面ID号角顶点ID号
0 z 0 1 1 2 1 3 1
1 x 0 3 0 2 2 0 2
2 x 0 1 0 3 2 0 0
3 y 0 2 0 1 2 0 1
1.2   基于正四面体中心投影的凸多面体的Minkowski和算法
两个凸多面体P和Q倾斜图的覆盖确定了P和Q上具有平行支撑平面的一对表征(凸多面体的顶点、边、面),在单位球面上占有相同区域的表征具有相互平行的支撑平面,Minkowski和凸多面体顶点m的坐标为凸多面体P的顶点v和Q的顶点w坐标的矢量和,其中顶点v、w具有平行的支撑平面,即顶点v、w的点域在同一个单位球面上占有相同区域,同样的道理适用于凸多面体的正四面体中心投影,据此我们可以得到Minkowski和凸多面体的所有顶点坐标,并把该坐标赋值给新平面剖分中相应面的附加信息.
从给定的凸多面体表征以及它们之间的关联关系得到四个平面凸剖分等同于把两两分离的线段插入到正四面体的三角形面内,求凸多面体P1和P2的Minkowski和等同于求P1和P2的四对平面剖分的覆盖,每对平面剖分的覆盖为新的平面剖分,通过计算平面剖分中各面的附加信息,我们能够得到新多面体的正四面体中心投影,最后求逆映射,得到我们所要求的Minkowski和多面体,下文给出基于正四面体中心投影的凸多面体的Minkowski和算法.
该算法的输入为凸多面体P1和P2的正四面体中心投影,正四面体中心投影各平面剖分中的顶点、半边、面之间的关联关系由DCEL得到.输出为凸多面体P的正四面体中心投影,其中P  P1P2.
步骤1. P赋值为P1;
步骤2. For i  0 to 3 //这里i为正四面体的各三角形面的ID号
{ 设置边的访问标志数组和顶点的访问标志数组;
设置辅助队列Q为空,取P2的平面剖分中最左端的顶点作为起始点入队列Q;
while(队列不为空时)do {
队头元素出队列,记为v;
把顶点v加入到P的平面剖分中,设置顶点v已被访问;
取与顶点v相关联的边;
If(关联边未被访问)then {
插入到P的平面剖分中;
根据边的交叉情况,设置或更改顶点、半边的DCEL;
记录半边来源于哪个多面体,并设置这些关联边已被访问;
};
取顶点v的邻接顶点;
If(邻接顶点未被访问)then 邻接顶点入队列;
}; ii1;
           };
步骤3. 用符号f1,f2,…,fn表示P的平面剖分中的各个面,设面f1,f2,…,fn的附加信息中分别存储着凸多面体P的相应顶点坐标,记为m1,m2,…,mn,并且m1,m2,…,mn的初值均为0;
For j  1 to 2
{ For i  0 to 3
{ 取P的平面剖分中最左端的面(有边界的面)作为起始面,记为f;
设g为Pj中的面,并且gf;
面g的附加信息中存储着凸多面体Pj的相应顶点坐标v;
While(面f相对于Pj未被访问)do {
面f的附加信息中存储着凸多面体P的相应顶点坐标,记为m;
mmv,设置面f相对于Pj已被访问;
输出面f及其附加信息;
取面f的边界半边; //边界半边处于三角形面内
取边界半边的孪生半边的关联面,记为l1,l2,…,ls;
If(l1,l2,…,ls中存在相对于Pj未被访问的面,记为f )then {
If(与f 关联的半边he来自于Pj,其中半边he的孪生半边与面f关联)then {
在Pj中取半边he的关联面,记为g;
面g的附加信息中存储着凸多面体Pj的相应顶点的坐标,记为v; gg;
}
Else面g的附加信息中存储着凸多面体Pj的相应顶点的坐标,记为v
}
Else在面l1,l2,…,ls中任取一面,记为f ;
f  f ;
}; ii1;
}; jj1;
};
步骤4. 计算顶点、半边的附加信息; //得出所有真实元素
步骤5. 计算新平面剖分中真实顶点的相应面的方程; //Minkowski和凸多面体的小面映射为新平面剖分
//中的真实顶点

我觉得其中一个关键问题是:[U]解决如何得到正四面体的中心投影 ,怎么投影问题是个关键[/U]

先建立一个凸多面体的类，在类里定义一个投影的方法，而后创建两个类的实体，而后按照算法求和

但是两个凸多面体以什么形式输入呢?
是以顶点坐标的形式吗还是...?

还请大家帮忙分析以下,谢谢了!!!!!!

[此贴子已经被作者于2006-4-4 23:29:55编辑过]


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	93.018ms