安全两方线段求交协议及其在保护隐私凸包交集中的应用

研究了现有安全多方计算几何协议,提出了安全多方计算几何的模型和框架,从数学模型、安全模型和通信模型3个维度展开描述。针对现有安全两方线段关系判定协议都忽略求解交点坐标的问题,在半诚实模型下基于Paillier同态加密技术提出了安全两方线段求交协议,使用Goldreich证明法进行了理论安全性分析,并在恶意模型下进行了推广。分析结果表明,该半诚实模型下的算法在效率上优于现有算法。作为安全两方线段求交协议的应用,结合O’Rourke算法提出了保护隐私的凸包求交集协议,弥补了安全计算几何领域仅实现了凸包并集算法的缺陷。

关于优化n条线段求交算法的研究

首先分析了n条线段相交算法的不足,然后系统地阐述利用扫视法缩小求交线段的范围、利用点位判别法高效判断两线段是否相交的理论,从而提出了一套较为优化的n条线段求交算法。本文对其算法给出详细的分析和讨论,最后指出此算法的适用范围。

任意曲面离散求交的投影算法及其实现

提出一种任意曲面离散求交的投影算法。曲面首先被离散为一系列三角形平面子面片 ,然后将这些平面三角形面元分别投影到正投影面和水平投影面上 ,再将得到的两个投影映射到二维空间。在二维空间 ,求出两相交三角形的交线段 ,其集合就是两曲面交线的逼近。在详细描述算法原理后 。

对一道IMO试题的探索

第38届IMO试题第2题: 设∠A是△ABC中最小的内角,点B和C将这个三角形的外接圆分成两段弧,U是落在不含A的那段弧上且不等于B与C的一个点,线段AB和AC的垂直平分线分别交线段AU于V和W,直线BV和CW相交于T.证明AU=TB+TC.

基于顶点编码的多边形窗口线裁剪高效算法

从多边形窗口线裁剪的本质特征出发 ,首次提出窗口顶点编码的新概念 .以被裁剪直线为参照系 ,将多边形窗口划分为正区、负区和近零区三类区域 ,从而快速完成多边形窗口顶点编码 .通过窗口顶点编码与传统的线段编码相结合 ,无须求交即可快速排除大部分窗外线段 ;进一步可以直接得到与直线相交的窗口边 ,加快了求交进程 .更有意义的是 ,通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况 :裁剪直线通过多边形的顶点、裁剪直线通过多边形的边 .实验结果表明 ,新算法提高了裁剪效率并具有很好的稳定性 .

一种等值线图的任意复杂多边形窗口裁剪算法

给出了一种新的海量等值线图任意多边形窗口的快速裁剪算法。计算裁剪多边形的外包围盒并创建网格结构,利用网格结构对等值线进行快速预裁剪,通过链式结构对等值线进行细节裁剪得到最终裁剪结果。通过建立行链式结构可以实现以行扫描的方式快速判断点的内外属性,而且还能减少线段求交运算次数,基本能确定实际相交的线段时才进行求交运算。经过大量的实验,证明该算法非常高效且稳定。另外,新算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。该算法程序实现简单且符合工程需求。

大规模等值线图任意多边形裁剪算法

给出一种大规模等值线图任意多边形窗口的快速裁剪算法。首先进行传统算法的外包围盒裁剪,然后针对外包围盒创建一种约束网格结构,然后利用网格对等值线进行快速预裁剪,最后通过行扫描算法对等值线进行定位并进行局部细节裁剪得到最终裁剪结果。通过约束网格可以实现以行扫描的方式快速判断点的内外属性,而且基本能确定实际相交的线段时才进行求交运算,减少了大量的求交运算。另外,算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。经过大量的实验,证明本文算法非常高效且稳定。

基于扫描线的多面体隐藏线消除算法

在多面体隐藏线消除算法中计算投影后二维线段的交点时,通常采用的是传统的线段求交算法.本文从提高其速度入手,将计算几何领域中新的研究成果即扫描线算法应用到线段求交算法中,代替传统的线段求交算法,并通过建立线段在空间位置上的连续关系,达到快速消除隐藏线的目的.

大规模等值线图的任意简单多边形窗口裁剪算法

针对大规模等值线图裁剪算法面临的两个主要问题,如何减少线段求交次数和判别保留部分的起止点,提出一种针对大规模等值线图的任意多边形裁剪算法.该算法首先使用等网格分割方法,在等值线线段与裁剪多边形边之间建立网格索引,减少线段求交次数;同时,在网格数据结构基础上,采用局部射线法,很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题,使得算法可以快速判断出需要保留(剔除)的等值线部分.本文算法的优点是能够在求出交点的基础上快速获得需要保留(剔除)部分的起止点;同时,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.本文算法易于实现且高效.

基于拓扑分析的多层通道布线算法

本文提出了一种基于拓扑分析的多层通道布线算法。算法把整个布线过程分成拓扑分层和物理布线两个部分。拓扑分层利用线段交叠图及模拟退火算法解决线段分层及通孔最少化问题,物理布线过程引入虚拟走线道解决交叉问题,再利用轮廓线跟踪的方法来决定最终确定各线段的布线位置。算法还解决了多层布线分层的管脚约束问题和相邻约束问题。实验结果表明,这是一种有效的方法。

扫视法的引进及应用

我们引入扫视法的思想,在某种程度上降低了线段求交问题的复杂度.其基本思想是:设想有一纵坐标轴(y)自左向右扫过所有线段,当y处于某一位置时,所有与y接触线段可按此时y值的大小建立一全序关系,若当y轴移近某两相交线段的交点时,这两线段在全序关系中一定相邻.因此只需检查全序关系中相邻两线段是否相交即可.我们可假定线段的左端点为靠近交点的已知点,扫视线在任一状态所接触线段的全序关系可按这些线段的左端点y值的大小来建立.应该注意到:当某线段与其他线段有两交点时,相交线段的左端点就不是最靠近第二个交点的已知点了,而是第一个交点,因此当出现相交后需要重新调整全序集的位置关系.

基于自适应天牛须算法的航空发动机管路布局优化

针对航空发动机外部管路系统设计过程中布局效率和空间利用率较低的问题,提出一种基于自适应天牛须搜索算法的管路自动布局方法。该方法在原算法的基础上加入自适应变步长机制,使其在具有高效性的同时能搜索到更优的解。在描述复杂空间障碍物时,采用将附件和管路分开建模的方式,一方面建立机匣附件的轴向包围盒,并在包围盒内部构建小范围的附件栅格信息矩阵;另一方面,对已布局管路分段处理后采用线段求交的方式做出干涉性判断,在此基础上根据某种度量选择本条管路的避障策略,以达到充分利用敷设空间的目的。建立管路布局问题的数学模型,并以管路长度和压力损失作为优化目标完成路径的规划过程。最后,通过仿真实例证明所提方法的可行性。