船体剖面剪流计算中闭室搜索算法.docx

1、船体剖面剪流计算中闭室搜索算法孟凡冲(中国船级社技术研发中心，j踪100007)摘要：本文主要提出了船体剖面剪流计算中闭室单元的一种快速搜索算法.算法是以计算几何图形扫描法为基础，提出了基于行业特征的改进型快速算法.同时结合实际算例，给出了算法在剪流计算闭室搜索过程中的应用过程，并计算出算法的时间复杂度，总结了算法的实用性、快速性.为各大剖面计算软件提出了一种闭室单元搜索的解决方案。关键词：剪流计算；闭室搜索；平面扫描法；二维困形中图分类号：TP31,U661文献标识码：ADOI:10.l4141/j.31-1981.2015.05.014SearchingClosedCellAlgorith

2、mofHullSectionShearFlowCalculationMengFan-chong(ChinaClassificationSocietyTechnologyR&DCenter,Beijing100007,China)Abstract:Thepapermainlypresentsafastsearchalgorithmforcalculatingclosedcellofhullsectionshearflow.Thealgorithmisbasedonthegeometricsweepingmethod,proposingtheimprovedfastalgorithmbas

3、edonthecharacteristicsoftheindustry.Combinedwithapracticalcase,thealgorithmisgiventocalculatetheapplicationprocessofsearchingclosedcellprocessofashearflow,andthenitanalyzesthetimecomplexityofthealgorithm,whilesummarizingthecharacteristicsofpracticalandfasten.Thesoftwarepresentsasolutionofaclosedcell

4、searchformajorsectioncalculationsoftware.Keywords:shearflow;closedcellsearch;planesweepalgorithm：2Dgraph0引盲剪流计算是确定船剖面剪力分配的T*重要步骤中国船级社钢质海船入级规范和IACS的HCSR规范对船舶剖面的剪流计算都有明确定义和要求，同时提供了具体的计算方法和公式。在计算当中，假设横剖面图形巳寻皮划分成多个封闭的区域，然后根公式计算这些封闭区域的剪流强度七因此闭室搜索是剪流计算中最关键的-现在很地白计重欠醇计算剪枷新国室手逐信息、，向了计敬率。1扫描法原理在的闭算法中，我佃蜩计算几何

5、中最重要的一类算法：平面扫描算法(PlaneSweepAlgorithm)o平面扫描算法使用T直线1作为扫描线，与扫描线相交的所有线段构成林合，称为扫描线的状态。随着自上向下推进扫描这些线段,扫描绷勺好不断球。不过,球并不爨卖的。只有拶靛的典拒描进行更新。我碱这些位M为平面扫描算法的事件点。当所有的事件点扫才苗完毕后则算法完成计算给出结果。可以看出，算法的运行时间效率为0()，为作者简介：孟凡冲(1980-),男，硕士研究生，工程师，研究方向：计算机图形图像第端点蟾叫螂睇画具有线段不魅5,搜索结为闭的元，理出婀。方法是从上向下扫描所有节点单元，当扫描至I节点蹄牛点时，查找呻钢围啪I瞭单元。如果

6、有该单元存在，将该单元记录到结果中，然后缪卖的节屐件。假设当前说个节点P(OKO,同时这些节点构殳为叫妇0加。算法首钢这些节点进行排序。排序规则是根据节点坐标从上到下,如果上下坐标一致则从左到抻冽。排序完成后，从最左上角的V节点开始扫才苗事件。当扫描®Jv节点时，查找该节点所在的线段下f节点V,并找到V节点所在的最右边的线段的另点V”。设V”端点为V,重复这个过程，直到节点驾垸毕或者找5IJ重复节点。如果查找结果为闭合单元，贝购该闭合单元保存吉果表作为结果输出，并从P列表和L列珈余朝过的节点2船体制面计算过程以单舷侧船体剖面为算例，一次性计算该剖面的闭合单元、公共边界等信息。图3中以

7、黑色填充圆圈标示的节点坐标在表1中给出。隔，姬余节点的最显角的节点为破节圈2遍历一次结果节点解Y坐标(m)Z够示(m)00.000.0015.800.00211.700.00314.420.00416.131.72516.136.11611.701.6875.801.68g0.001.68916.1314.151016.1319.60117.502025127.5019.63表2剖面的稣枷节点i节点、k101212323434545656767878959109101110111211121312914261517表1横割面的节点坐标图2为遍历一次跪程。(a)为廊窗J面，第一次蹒会输中奖挪分母

8、苗峡离后对所有节点使用快速排序法进行排序。排曜果为：1110-*!2958一7-*6>4J1->23进行第一次闭合单元遍历，其实v点为11，与V相邻的线段对应的V，点为12。在V，处相邻的最右线段为，其对应的v”点为9,。在9处对应的最右线K为。对应的线段R有，对应的V，点为11。点11已经被遍历过，因此此轮勃瓠瓠、构瞬合单元，跛至蜡翻11表。在第二;欠闭合单元遍历中，以9点为v点。最终查询到V，点5时发现形不成闭合单元,点5前节湖滁。第三次闭合单元遍历，查找到闭合单元、Q、。、。第四次闭合单元遍历，查找到闭合单元、Q、。至此完成所有遍历功能，同时线段在遍历过程中被标注弓I用的次数

9、如果大于1次，贝!J记录为公共边界。此图共边界为、。融毁SW蹒，得到翻吉果和实际情况一样。图4示例程序算;要就两个地方：节点排序和闭合单元遍历。排序受排序算法限制，目前睇龄S非序时间复型为THXnloglo闭合单元遍历T(g四。所以算法总的时间复杂度为T(n)=0(nlogzH-n)o3结论SO白规范计鼬剪流计算中，闭合单元扫描算合单元、节点断十算，炳公共边界的查找，可以快速提高计算工作的复杂度，极大提高工作效率，同时也就提高了计算软件的用户体验。在科技作为核心竞争力、制造业信息化的&下，只有不断自拙皱才能使自知测蚌不败汕。参考文献：1 杨松林，张正满.高性能舰船M.国防工业出版社.2

10、000:1-31.2 IACS,CommonStructuralRulesforBulkCarriersandOilTankersS.2014(5):355-362.3 周永青,陈德林秦皇岛15万DWr级FPSO船体中剖面设计J.船舶.2001.4 周培德.计算几何算法分析与设计M.清华大学出版社.2000.5 EP.PreparataandM.I.Shamos.ComputationalGeometry,AnIntnxluction,Springer-VerlagfM.NewYork,1985.6 A.V.Aho,J.E.HopcroftandJ.D.Ullman.TheDesignandAnalysisofComputerAlgorithms.Addison-Wesley,Reading,MAM,1974.7 MichaelV.Leonov,AlexeyGNikitin.AClosedSetofAlgorithmsfbrPerforming