[12_2]基于Voronoi图与蚁群算法的UCAV航路规划
![[12_2]基于Voronoi图与蚁群算法的UCAV航路规划](https://img.wendangku.net/imgde/06o6xx77eczcei862miy-e1.webp)
![[12_2]基于Voronoi图与蚁群算法的UCAV航路规划](https://img.wendangku.net/imgde/06o6xx77eczcei862miy-52.webp)
基于Voronoi 图与蚁群算法的UC AV 航路规划
何艳萍
1,2
, 张 安1, 刘海燕
2
(1.西北工业大学电子信息学院,西安 710072; 2.第二炮兵工程学院,西安 710025)
摘 要:提出一种基于Vor onoi 图和蚁群优化算法(AC O )的无人作战飞机航路规划的方法。首先根据已知威胁源建立威胁源的Vor onoi 图,并构建了起始点、目标点与威胁场的Vor onoi 图赋权有向图,从而建立了无人机搜索路径的集合,结合初始集合,然后给出无人作战飞机航路规划的具体实现过程,最后对UCAV 在多种威胁环境下的航路规划进行了仿真实验,仿真结果表明这种航路规划方法是可行和有效的。关键词:UC AV;航路规划;Vor onoi 图;蚁群优化算法(AC O )
中图分类号:V279 文献标志码:A 文章编号:1671-637X (2009)11-0022-03
Pa th Pl ann i n g for UCAV Ba sed on Vorono iD i a gram
and An t Colony O ptim i za ti on
HE Yanp ing 1,2
, Z HANG An 1
, L IU Haiyan
2
(1.College of Electr onics and I nfor mati on,North western Polytechnical University,Xi πan 710072;
2.The Second A rtillery Engineering College,Xi πan 710025,China )
Abstract:A method based on Vor onoi diagra m and ant col ony op ti m izati on was p r oposed for path p lanning
of Uninhabited Combat A ir Vehicle (UCAV ).First,the Vor onoi diagra m of threats was created according t o the known threat s ources,and the Vor onoi weighted directi on diagra m of start point,target point and threat field was created .Then,a set of UCAV searching paths was created,and the realizati on p r ocess of path p lanning for UCAV was given based on the initial set .Si m ulati ons were carried out on path p lanning of UCAV under vari ous threatening envir onment .Si m ulati on results show that the p r oposed method is effective and feasible .
Key words:UCAV;path p lanning;Vor onoi diagra m;Ant Col ony Op ti m izati on (ACO )
0 引言
无人作战飞机路径规划是要寻找从初始点到目标点满足某种性能指标最优的运动轨迹。所谓最优轨迹,就是在给定的战场区域中,能够最大限度地利用地形信息和敌情信息,综合考虑飞机的导航精度和机动能力的限制,使飞机飞行在安全概率最大的飞行航线上。因此,航路规划是UCAV 任务规划系统的关键组成部分[1-2]
。为了解决上述问题,出现了大量的无人
机的航路规划方法,目前存在的研究方法有:动态规划
算法
[3]
、遗传算法(G A )
[4]
、A 3
算法
[3]
、蚁群优化算法
收稿日期:2008-09-15 修回日期:2008-11-26
基金项目:高校博士点基金项目资助(20060699026);航空科学基础基金项目资助(20060553008)
作者简介:何艳萍(1979—),女,湖北随州人,硕士生,讲师,主要研究方向为复杂系统建模与仿真。E -mail:ping pinghe2000@yahoo .co https://www.wendangku.net/doc/db17186798.html,
(ACO )
[5-6]
等,这些算法各有其优缺点,算法的优劣主
要取决于算法的实时性和路径解的最优性。本文在研究已有算法的基础上,提出一种基于Vor onoi 图和蚁群优化算法的无人作战飞机航路规划的方法。
1 建立威胁场的Vorono i 图
Vor onoi 图是计算几何学中一种重要的几何结构,
其应用在航路规划中的最大特点是根据已知战场威胁源分布情况下生成由初始可选路径集,它是一组由连接两邻点直线的垂直平分线组成的连续多边形构成。通过V 图能够有效地将地理信息中的点、对象和区域以集合拓扑结构表示出来,并且能够通过这些拓扑关系表示自然语言中的定性关系和模糊地理信息,这种性质对于航线规划非常关键,尤其对于初始航线集或者航路区域的确定很重要。
要为UCAV 规划航路,就要考虑到威胁。所以,要
Vol .16 No .11
Nov .2009
第16卷 第11期2009年11月
电 光 与 控 制Electr onics Op tics &Contr ol
根据威胁的地理分布(威胁包括敌方的探测设备及地形障碍)计算威胁分布的Vor onoi图,确定航路的走向和航区。此处,将威胁点均简单表示为雷达点(把地形威胁视为雷达,用和雷达一样的方法来处理),且这些雷达点满足雷达方程(即表示目标反射的能量与目标距雷达距离的四次方成反比1/d4)。这里,假设雷达功率相同,其搜索范围是一个以雷达为圆心半径r
o
的圆,当UCAV飞到该范围内时,几乎百分之百的概率会被探测到和击毁,同时假设威胁点之间没有可以改变探测性能的信息交流,UCAV飞行高度保持不变,这样就把问题降到二维的协同航线规划问题。由Vor onoi图的特性可知,若UCAV沿Vor onoi图的边飞行,受到相邻两个威胁点的威胁最小。现在问题简化为在Vor onoi图上寻找UCAV 从起始点到目标点的最小代价航线,将无限搜索转化为有限搜索,大大降低了计算量[3,7]。
2 建立赋权有向图
在构造Vor onoi图时,起始点和目标点不在母点范围之内。为简化起见,将起始点和目标点分别与其几何距离最近的3个节点相连,这样使起始点和目标点与威胁场Vor onoi图形成一个从起点到目标点的有向图。
无人机路径规划就是要寻找飞行代价最小的路径,要满足无人机的生存概率和杀伤概率最大,这需要无人机具有规避威胁的能力,并满足其燃料足够安全返回基地。考虑两方面的代价:一是无人机的燃料限制,二是威胁场中各个雷达对无人机的威胁。第一方面可以假定无人机以恒定的速度飞行,燃料限制与路
径的几何长度相关,可简单表示为J
f,i =L
i
,L
i
是第l
i
条边的长度。第二方面,假设各个雷达是相同的,无人
机的雷达反射作用效果是无人机到雷达距离d的四次方分之一。因此无人机沿着某一边l
i
飞行,其所受的雷达威胁与无人机到雷达距离的四次方分之一成正比。更精确的威胁计算方法,可以将一条Vor onoi边分段计算、合并。为了简化计算,每条路径均匀地分成6等分,取其中的3个点来代替整条路径的代价,这3个
点分别是:1/6,1/2,5/6。其中L
i
为第i条路径的长
度,d
1/6
为距离该条路径最近的威胁点到该条路径1/6
处的距离,d
1/2
为距离该段路径最近的威胁点到该条路
径1/2处的距离,d
5/6
为距离该路径最近的威胁点到该
条路径5/6处的距离。如图1所示,在每条边的L
i
/6、
L
i
/2、L i5/6点处分别计算某一雷达对该边的威胁值。
对第l
i
条边,威胁代价计算公式为[3]
J t,i =L
i6
n
j=1
(
1
d41
6,i,j
+
1
d41
2,i,j
+
1
d45
6,i,j
)(1)
其中:n是威胁场中雷达的个数;d1
6,i,j
是第j个雷达距
第l
i
条边1/6处的距离。因此,综合考虑上面两方面
的代价,无人机沿Voronoi有向图的第l
i
条边飞行的最
终代价为
J
i
=kJ
t,i
+(1-k)J
f,i
(2)
这样Vor onoi有向图就变成赋权有向图,每条边的
代价就是J
i
,
从而建立了无人机搜索路径的集合。
图1 路径代价计算
Fig.1 Path cost calculati on
3 蚁群优化算法
蚁群算法(Ant A lgorithm)是一种新的概率搜索算
法,它利用生物信息激素作为蚂蚁选择后续行为的依
据。即每只蚂蚁会对一定范围内其他蚂蚁散布的生物
信息激素做出反应,依据生物信息激素的强度在每一
个道口对多条路径选择做出概率上的判断并执行该选
择,同时影响后续蚂蚁的行为。于是,寻优过程就通过
若干蚂蚁的协同搜索完成。受到蚂蚁这种觅食方式的
启发,M Dorigo等人在1991年首先提出了蚁群算
法[8],并将其应用于TSP问题,取得了一定成效。考虑
到TSP问题与航路规划问题具有一定的相似性,本文
将其引入航路规划领域。
3.1 算法的数学模型
通过模仿蚂蚁的觅食行为方式,在求解航路规划
问题时,将m个人工蚂蚁定位于起始点,每个蚂蚁使
用一定的状态转换规则从一个状态转到另一个状态
(即从一个节点转到另一个节点),直到最终到达目标
点,完成一条候选航路(航路规划问题的一个可行
解)。在所有m个蚂蚁都完成了各自的候选航路选择
后,再根据生物信息激素修改规则,利用当前m条候
选航路以及历史上得到的一条代价最小的候选航路信
息,修正网络图中各条边的生物信息激素强度,这一修
正过程模拟了蚂蚁释放生物信息激素以及生物信息激
素的自然挥发现象,生物信息激素的修改规则可以引
导蚂蚁搜索到问题的最优解[9-10]。
本文具体操作如下:首先,对Vor onoi图各边给出
初始信息素值,令蚂蚁从距离出发点最近的Vor onoi节
点开始搜索,根据状态转移规则选择行进的Vor onoi
32
第11期何艳萍等: 基于Vor onoi图与蚁群算法的UC AV航路规划
边,以距离目标点最近的Voronoi节点为终点结束搜索。当所有蚂蚁完成各自的候选航路选择后,按照信息素更新规则对Vor onoi图中各边的信息素进行更新,其中没有蚂蚁经过的边进行信息素蒸发,重复这一过程直至达到结束条件。
1)蚂蚁状态转换规则。一个人工蚂蚁选择新可行节点的概率是由两节点间边的代价以及生物信息激素的强度决定的,按式(3)计算蚂蚁k从当前节点r转换到可行节点s的概率为[5-6,11]
p k (r,s)=
τ(r,s)αη(r,s)β
6
s∈J k(r)
τ(r,s)αη(r,s)β
,s∈J k(r)
0,其他
(3)
式中:τ(r,s)为蚂蚁储存在边L(r,s)上的生物信息激素强度;η(r,s)为节点s相对于节点r的可见性,
η(r,s)=1/C
rs ,C
rs
为边L(r,s)的代价;J
k
(r)是第k个
蚂蚁由节点r可以到达所有可行节点的集合,这些节点均是节点r的相邻节点,而且它们比节点r更接近目标点;α为信息启发式因子,表示轨迹的相对重要性,反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用;β为期望启发式因子,表示能见度的相对重要性,反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度。蚂蚁从状态r转移到状态s 所选可行节点的概率会随着生物信息激素强度的增大而增大,随着通路代价的增大而减少。
2)生物信息激素修改规则。一旦所有蚂蚁完成了各自候选航路的选择过程(找到一条航路规划问题的可行解),就必须对各边上的生物信息激素作一次全面的修正,修正规则如下[5,11]:
τ(r,s)=(1-ρ)τ(r,s)+ρ[Δτ(r,s)+eΔτe(r,s)]
(4)其中:
Δτ(r,s)=6m k=1Δτk(r,s)(5)式中:m为蚂蚁的数量,0<ρ<1为信息挥发参数,用来蒸发储存在边上的生物信息激素,以减弱原有的信息;1-ρ为信息素残留因子;0 Δτk(r,s)= Q/W k ,边L(r,s)属于蚂蚁k的候选航路 0,其他 (6) Δτe(r,s)= Q/W e ,边L(r,s)属于当前最好的候选航路0,其他(7) 式中:Q值为一个常数,用来控制信息素的强度;W k 为蚂 蚁k选择的航路广义代价;W e 为当前最小的航路代价。 3.2 实现步骤 根据上述的原理和规则,基于Vor onoi图和蚁群优化算法的无人作战飞机航路规划问题的具体步骤如 下: 1)根据威胁源分布构造Vor onoi图,并计算 Vor onoi图中每条边的总代价;参数初始化,Vor onoi图 每条边赋初始信息素值; 2)将所有蚂蚁置于距离出发点最近的Vor onoi图 节点,并根据式(3)选择下一节点,直至所有蚂蚁完成 搜索过程; 3)根据式(2)计算出可行路径的代价,并更新所 找到的最优路径; 4)参照当前循环中最优路径更新所有Vor onoi边 信息素值,规则如式(4)、式(5); 5)若满足循环结束条件,则循环结束并输出计算 结果,否则跳转到2)。 4 仿真实验 图2描述了某UCAV的任务态势。敌方阵地大小为70km×70km,其中:“●”代表雷达、导弹等威胁 源;“■”代表UCAV出发点;“★”表示任务目标点,其 具体方位如表1、表2所示。进入敌方防御区域后, UCAV需要根据自身所处的威胁环境完成航路优化计 算。实验中参数设置为m=30,α=2,β=5,ρ=0.1, Q=100。图3在70km×70k m的空域内,我方UCAV 从坐标(10,0)处飞到(45,65),利用本文所提ACO算 法在Voronoi图中进行无人作战飞机航路搜索,图3给 出了UCAV进入威胁区域执行作战任务时的航路规划 结果,可行航路在图中用实线表示,仿真结果表明这种 航路规划方法是可行和有效的。 表1 起始点、目标点的坐标方位 Table1 The coord i n a tes of st art po i n t and t arget po i n t 起始点坐标目标点坐标 (10,0)(45,65) 表2 威胁点的坐标方位 Table2 The coord i n a tes of threa t po i n ts 威胁点编号及坐标 1(17,55)2(32,61.5)3(45,61)4(51.5,59) 5(61,53)6(57,40)7(51.5,26)8(48,16) 9(33.5,19)10(22,25)11(12,31)12(9,42) 13(25,47)14(20,40)15(46,35)16(24,37) 17(33.5,52)18(32,43.5)19(38,57.5)20(40.5,50) 21(37,45)22(40,30)23(46,52)24(53,50.5) 25(50,43)26(28,52)27(43,45)28(28,28) 29(37.5,25)30(40,41.75)31(44,22)32(36,35) 33(35,39)34(30,34) (下转第54页) 5 结束语 美国的双射程/双任务导弹历经近20年的探索和发展,目前已进入工程化发展阶段,通过对其进行较为深入的技术分析,可以更清楚地认识双射程/双任务导弹和相关的武器火控系统及其发展趋势。 参考文献 [1] Dual Range M issile A ir Superi ority M issile Technol ogy (AS MT )[Z/OL ][2009-09-01]htt p://www .fas .com. [2] 李佑义.美空军探索双射程空空导弹[J ].现代军事, 1998(4):29230.[3] 高劲松, 孙晓琳,赵东方.美国双射程双任务导弹的发 展[J ].国际航空,2009(2):46247. [4] 高劲松,杨慧.美国双射程双任务导弹评述[J ].国际 航空,2009(4):33235.[5] 高劲松,孙隆和.双射弹的擦肩发射原理研究[J ].电 光与控制,2006,13(6):24227.[6] 高劲松,田省民.以本机为中心的全向攻击的概念研 究[J ].电光与控制,2008,15(8):61263.[7] HE W S ON R .Jane πs air 2launched weapons[M ].Jane πs I n 2 f or mati on Gr oup L i m ited,2008.[8] 杰伊?米勒.“猛禽”F -22新一代主力战机[M ].杨晨 光,白堃,译.北京:科学普及出版社,2009.[9] 杨伟,陈林.JSF 联合攻击战斗机[M ].北京:航空工 业出版社,2006. [10] Un manned syste m r oad map 200722032[Z ].Office of the Secretary of Defense,W ashingt on DC,Oct 2007. (上接第24页)图2 UC AV 的任务态势Vor onoi 图 Fig .2 Situati on Vor onoi map of UC AV 图3 蚁群算法优化后的无人作战飞机可行航路图 Fig .3 The feasible path p lanning map of UCAV by using ant col ony op ti m izati on algorith m 5 结论 Vor onoi 图能够有效地将地理信息中的点、对象和 区域以集合拓扑结构表示出来,并且能够通过这些拓 扑关系表示自然语言中的定性关系和模糊地理信息,这种性质对于航线规划非常关键,尤其对于初始航线集或者航路区域的确定很重要。本文在传统Vor onoi 图的基础上,根据已知的威胁分布情况,采用Vor onoi 图对敌方区域进行划分,运用蚁群算法对无人机航路 进行规划,仿真结果表明ACO 算法在Voronoi 图中进行航路规划的可行性,可行航路保证UCAV 能够回避各种威胁,顺利地飞抵目标点。值得注意的一点是,在基于Vor onoi 图和蚁群优化算法的无人作战飞机航路规划以后,为了保证航迹的可飞性,必须满足一些限制的条件,例如最大过载及转弯半径限制,此时可以采用其他的方法对航迹进行光滑细化。 参考文献 [1] 韩志刚,贺建良,孙隆和,等.现代空对地攻击技术 [J ].电光与控制,1999,6(4):17222. [2] 孙彪,朱凡.采用粒子群优化算法的无人机实时航迹 规划[J ].电光与控制,2008,15(1):35238.[3] 田伟.无人作战飞机航路规划研究[D ].西安:西北工 业大学,2007.[4] 马云红,周德云.基于遗传算法的无人机航路规划 [J ].电光与控制,2005,12(5):24227.[5] 柳长安.无人机航路规划方法研究[D ].西安:西北工 业大学,2003.[6] 任波,于雷,韩李勋.自适应蚁群算法的无人机航迹规 划方法[J ].电光与控制,2007,14(6):38239.[7] 叶媛媛,闵春平.基于Vor onoi 图的无人机空域任务规 划方法研究[J ].系统仿真学报,2005(6):135321355.[8] ALBERT O C,DOR I G O M ,V I TT OR I O M ,et al .D is 2 tributed op ti m izati on by ant col onies[C ]//Pr oceedings of the 1st Eur opean Conference on A rtificial L ife,Paris,1991:1342142.[9] 段海滨,王道波,朱家强,等.蚁群算法理论及应用研 究的进展[J ].控制与决策,2004,19(12):132121326.[10] 段海滨.蚁群算法原理及其应用[M ].北京:科学出 版社,2005.[11] 彭斯俊,黄樟灿,刘道海,等.基于蚂蚁系统的TSP 问 题的新算法[J ].武汉汽车工业大学学报,1998,20(5):88292. 多边形的扫描转换 图形学中多边形有两种表示方法：多边形的顶点表示与点阵表示。顶点表示用多边形的顶点序列来刻画多边形；点阵表示则是用位于多边形内的像素的 集合来刻画多边形。 扫描转换多边形或多边形的填充：从多边形的顶点信息出发，求出位于其内部的各个像素，并将其颜色值写入帧缓存中相应单元的过程。 x-扫描线算法 基本思想：如下图所示，按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的所有像素。 图5-8 x-扫描线算法填充多边形 算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。 (2)从y=ymin到y=ymax，每次用一条扫描线进行填充。填充过程可分为四个步骤： a.求交：计算扫描线与多边形各边的交点； b.排序：把所有交点按照递增顺序进行排序； c.交点配对：交点两两配对，表示扫描线与多边形的一个相交区间； d.区间填色：将相交区间内的像素置成不同于背景色的填充色。 存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。如下图所示，在扫描线y=1，y=5和y=7时，扫描线过多边形的顶点，若不加以处理，交点配对时会发生错误。 图5-9 与多边形相交的交点的处理 解决方法：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。实际处理时，只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 改进的有效边表算法 由于x-扫描线算法在处理每条扫描线时，需要与多边形所有的边求交，效率很低，因此需要加以改进，形成改进的有效边表算法。 改进原理： (1)处理一条扫描线时，仅对有效边求交。 (2)利用扫描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似。 (3)利用多边形边的连贯性，即当某条边与当前扫描线相交时，它很可能也与下一条扫描线也相交：若边的直线斜率为k，这样边与两条相邻扫描线的交点有如下关系：xi+1=xi+1/k。 图5-10 与多边形边界相交的两条连续扫描线交点的相关性 有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点为： 正多边形的有关计算 一、素质教育目标 (一)知识教学点 使学生学会将正多边形的边长、半径、边心距和中心角、周长、面积等有关的计算问题转化为解直角三角形的问题． (二)能力训练点 1．通过定理的证明过程培养学生观察能力、推理能力、概括能力； 2．通过一定量的计算，培养学生正确迅速的运算能力； 3．通过用不同方法求正多边形的内角，培养学生的发散思维能力和选优意识； 4．从具体边数的正n边形得到一般正n边形的计算图培养学生化归、转化的数学思想． (三)德育渗透点 1．由具体边数的正多边形计算图过渡到一般计算图，渗透了“从特殊到一般，再由一般到特殊”的辩证唯物主义认识观； 2．正多边形计算图的得出渗透了化繁为简、化难为易二矛盾相互依存、相互转化的思想； 3．通过正多边形的有关计算，培养学生仔细认真、一丝不苟、严谨的科学态度； 4．通过正多边形有关计算公式的推导，培养学生不断探索科学奥秘的创新精神． 二、教学重点、难点、疑点及解决方法 1．重点：1．化正多边形的有关计算为解直角三角形问题定理．2．正多边形计算图及其应用． 2．难点：正确地将正多边形的有关计算问题转化为解直角三角形的问题解决、综合运用几何知识准确计算． 3．疑点及解决方法：学生对只画出正n边形的一部分图形的计算图生疏，用它分析、计算有疑虑．为此计算图的抽象应由具体边数的正多边形计算图逐步过渡． 三、教学步骤 (一)明确目标 前几课我们学习了正多边形的定义、概念、性质，今天我们来学习正多边形的有关计算． (二)整体感知 大家知道正多边形在生产和生活中有广泛的应用性，伴随而来的有关正多边形计算问题必然摆在大家的面前，如何解决正多边形的计算问题，正是本堂课研究的课题． (三)重点、难点的学习与目标完成过程 哪位同学回答，什么叫正多边形．(安排中下生回答：各边相等，各角相等的多边形．) 什么是正多形的边心距、半径？(安排中下生回答：正多边形内切圆的半径叫做边心距．正多边形外接圆的半径叫做正多边形的半径．) 正多边形的边有什么性质、角有什么性质？(安排中下生回答：边都相等，角都相等．) 什么叫正多边形的中心角？(安排中下生回答：正多边形的一边所对正多边形外接圆的圆心角．) 正n边形的中心角度数如何计算？(安排中下生回答：中心角的度数 正n边形的一个外角度数如何计算？(安排中下生回答：一个外角度 哪位同学有所发现？(安排举手学生：正n边形的中心角度数=正n边形的一个外角度数．) 计算几何课程设计报告 基于Voronoi图的简单多边形骨架提取 引言 骨架（Skeleton）又称中轴（Medial Axis），通常使用烧草模型和最大球（圆）模型来描述。骨架有着与原物体相同的拓扑和形状信息，是一种性能优良的几何特征，能够有效的描述物体，因此，在物体识别、路径规划、医学工程等领域多有应用。在物体识别等应用领域里，骨架提取的输入可以看作是空间内的点构成的多边形，对于多边形的骨架提取也成为了这些应用的基本技术，具有重要的应用意义。在此次课程设计中，我们实现了基于Voronoi 图的任意多边形的骨架提取，并提供了多边形骨架提取的演示界面。 多边形骨架 一个多边形的骨架，如上图所示，可以看作是由无数点对之间的骨架点组成的。两点间的骨架（skeleton）（等同于对中轴(medial axis)的求取）是到两点距离相等的点的轨迹，它是两点连线的垂直平分线，每一点所邻接的半平面是到其距离最小的点集相应地可扩展为离散点集的中轴定义。它是下列性质点的轨迹：其上任一点到最近两离散点距离相等，相应地也产生各点到其距离最小的点集；两线间的中轴是到两线距离相等的点的轨迹，它在两线相交时为角平分线——两线平行时为到两线距离——的平行线，每一线所邻接并以中轴为界的区域是到其距离最小的点集。一线和一点间的中轴是到该点(线距离相等的点的轨迹,它是以该点为焦点、该线为准线的抛物线。该点或线所邻接并以中轴为界的区域是到其距离最小的点集。 多边形骨架的几何算法 多边形骨架（中轴）的几何算法，是由多边形的某一点开始，找出参与中轴线计算的相应的线段与线段、点与线段、点与点，实质都转化为求某个特定点（中轴转折点）的问题， 多目标线性规划的若干解法及MATLAB 实现 一．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ， 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件：0 Ax b x ≤?? ≥? （3） 二．MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为： ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理：单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ） fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束 简单多边形裁剪算法 摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前 裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。 关键词：多边形裁剪；交点；前驱；后继；矢量数组 一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。 二、发展研究现状 近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。 以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。 三、新算法设计 1、算法的思想 本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。 2、主要数据结构 多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。裁剪多边形和被裁剪多边以下我们分别用S和C表示， Weiler－Atherton任意多边形裁剪 Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。 一、Weiler－Atherton任意多边形裁剪算法描述： 在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。 裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称： 1、被裁剪多边形为主多边形，记为A； 2、裁剪窗口为裁剪多边形，记为B。 主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域： 1、A∩B（交：属于A且属于B）； 2、A－B（差：属于A不属于B）； 3、B－A（差：属于B不属于A）； 4、A∪B(并：属于A或属于B，取反；即：不属于A且 不属于B)。 内裁剪即通常意义上的裁剪，取图元位于窗口之内的部 分，结果为A∩B。 外裁剪取图元位于窗口之外的部分，结果为A－B。 观察右图不难发现裁剪结果区域的边界由被裁剪多边形的 部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边 界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界， 或者反之。由于多边形构成一个封闭的区域，所以，如果被裁 剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类： 一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e； 一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。 二、Weiler－Atherton任意多边形裁剪算法思想： 基于变分网格的曲面简化高效算法? 金勇, 吴庆标+, 刘利刚 (浙江大学数学系,浙江杭州 310027) An Efficient Method for Surface Simplification Based On Variational Shape Approximation* JIN Yong, WU Qing-biao+, LIU Li-gang (Department of Mathematics, Zhejiang University, Hangzhou 310027, China) + Corresponding author: E-mail:qbwu@https://www.wendangku.net/doc/db17186798.html, Abstract:Providing fast and accurate simplification method for large polygon mesh is one of the most important research focuses in computer graphics. Approximating mesh model with a few polygons can improve the rendering speed, and reduce the storage of the model. The paper presents a local greedy algorithm to minimize the energy defined by variational shape approximation. The algorithm simplifies the mesh by controlling the number of the target polygons, while attempting to get ideal effect by adaptive seed triangles selection. The algorithm has intuitive geometric meaning. The method is efficient enough to be efficiently adopted in the geometric modeling system. Key words: Polygon mesh simplification; variational shape approximation; greedy algorithm; geometric modeling 摘要: 为大型的多边形网格模型提供快速、准确的简化算法是计算机图形学中的一个重要的研究方面.以较少的多边形逼近表示网格模型,能够提高模型的绘制速度,减小模型的存储空间.本文根据变分网格逼近表示所定义的全局误差能量,提出一种局部贪心优化算法,该算法通过控制目标网格分片数来简化网格,通过种子的自适应选取以达到理想的简化效果,具有直观的几何意义.本文方法计算量少,效率较高,能够有效应用于几何造型系统中. 关键词:多边形网格简化;变分网格逼近;贪心算法;几何造型 中图法分类号: TP391文献标识码: A 1 引言 三维多边形网格模型,包括三角形网格、四边形网格等,在计算机辅助几何设计、计算机动画、虚拟现实、计算机游戏和医学影像等领域有着大量的应用.随着三维扫描技术的发展,顶点数为数万的模型已经非常常见, ?Supported by the National Natural Science Foundation of China under Grant No.10871178, 60776799 (国家自然科学基金); Technology Department of Zhejiang Province Grant No. 2008C01048-3(浙江省重大科技创新项目) 作者简介: 金勇(1985－),男,上海人,博士研究生,主要研究领域为数字几何处理和计算机辅助几何设计;吴庆标(1963－),男, 浙江台州人,博士,教授,博士生导师,主要研究领域为图形与图像处理,数值计算方法,高性能并行计算和计算机模拟; 刘利刚(1975－),男,江西吉安人,博士,副教授,博士生导师,主要研究领域为数字几何处理,计算机辅助几何设计,计算机图形学和图像处理. 一种偏向目标型的RRT算法实现 摘要：本文针对基本快速扩展随机树(RRT)算法存在搜索过于平均、效率低下、用时较长的缺陷，提出了一种偏向目标型的改进型RRT算法。这种算法在生成随机点时以一定概率选择最终目标点作为局部目标点，使树的扩展有一个趋向于最终目标点的趋势，从而加快了算法的收敛速度，优化了规划路径。最后通过Matlab程序仿真，在二维平面上验证了改进型算法相对于基本算法的优越性。关键词：路径规划、RRT算法、偏向目标型 一.引言 机器人学是当今科学技术研究的热点问题，它汇聚了各个尖端学科最先进的研究成果。科学家们从上世纪40年代开始着手研制机器人到如今，机器人的发展主要经历了三次技术变革。从最简单的第一代机器人到现在的第三代智能机器人，机器人从只会机械的执行命令逐渐演变成利用各种先进的传感器自动的学习环境，适应环境，并完成人类下达的任务。 路径规划问题是机器人研究中的重要的组成部分，它的重点就是要使机器人自主并且安全的从起始位姿移动到目标位姿。机器人路径规划主要分为全局路径规划和局部路径规划两大方面。全局路径规划是一种利用环境全局信息的方法，它通常将周边环境信息存储在一张地图中，并且利用这张地图寻找可行路径。全局路径规划的优点是有利于找到全局可行解和最优解，但是它的运算时间长，不适用于快速变化的动态环境。常用的全局路径规划方法有栅格法、可视图法、拓扑法和自由空间法等。局部路径规划只考虑机器人当前能探测到的环境信息，运算速度快、反应迅速，非常适用于动态环境。但其缺点是算法可能无法收敛，不能保证机器人一定能够到达目标点，而且找到的可行路径可能会偏离最短路径。常用的局部路径规划算法有人工势场法、模糊逻辑法、神经网络法和遗传算法等等。 RRT算法是最近几年才发展起来的，并且应用比较普遍的一种路径规划算法。它在处理非完整约束的路径规划问题时具有相当大的优势，因为它可以将各种约束集成到算法本身之中，因此对环境要求较低。而且该算法概率完备，在理论上肯定能找到可行路径。但其缺点是搜索过于平均，算法效率较低，而且规划 Lync.in Link the world. Home About Projects SimpleDark 2009-09-24 / Chris posted in A lgorithm / 397 Views / 16 Comments 前些天在考虑一个几何算法，关于如何判断一个点是否在一个给定的多边形内部。这应该是一个比较常规的算法，我以前对几何算法了解的不多，所以既然想到了就稍微研究了一下。 查了一下相关的资料，目前有几个O(N)的算法，其中N是多边形的顶点数。 第一个叫做交替（Alternative）算法。如下图所示 算法检查所给定的点和在该点右边的多边形区域的边界的交点数，若交点数为奇数，则该点在多边形内部，若交点数为偶数，则该点在多边形外部。可以想象成从一个点向右发出一条射线，然后计算这条射线与多边形边界的交点数。从上图中标出的蓝色点向右射出的射线与多边形有1个交点，故判定其在多边形内部，而从标出的白色点向右射出的射线则有偶数个交点，故判定其在多边形外部。 这个算法的叙述起来很平常，但实现起来却有两个略带Tricky的地方。 其一是坐标精度引起的，因为计算机对于坐标的描述是离散的，在计算向右射出的射线与多边形交点的时 候很容易出现射线与多边形的某几条边平行的情况，对于这种情况，我们的算法需要向前多看几个点，以确定射线是确实与多边形相交还是只是“擦过”而已。 其二是对于非常靠近多边形边界的点的判定，你可以认为这些点是在多边形外，也可以认为是在多边形内，但你必须在算法中描述这些情况。 感兴趣的可以了解一下我的算法实现，附在文末。 这个算法在多边形为简单多边形的情况下是没有异议的，但在复杂多边形的情况下会有一些疑问，这涉及到“在多边形内还是多边形外”的定义问题。如下图 图中，如果用Alternative算法，则被多边形包围的那个点被判断为在多边形外部。 如果你认为这种定义不符合你的需要，那么有另外一种算法，称为Winding算法。 Winding算法的思路是这样的，将你置身于所给定的点上，然后让你的视线从多边形边界上的一点开始，选择一个方向绕着多边形的边界转一圈，如果你发现你的身体在这个过程中转了360度的非零整数倍，那么你所站在的这个点在多边形的内部，如果你的身体并没有转动（事实上你转动了，只是正向和逆向的转动抵消了），那么就在多边形的外部。 这个算法我没有去实现，一般来说它要比Alternative算法慢，因为它需要计算每条多边形的边与多给定的点之间的夹角。 关于算法实现： 程序的界面是用WTL写的，如果你想要编译源代码，请在Visual Studio中指定WTL的include文件夹位置。 算法核心代码如下，其中vSelectionPoints是多边形 多目标规划问题 3.5 黑龙江省可持续农业产业结构优化模型的求解 鉴于上面的遗传算法的基本实现技术和理论分析，对标准遗传算法进行适当改进，将其用于求解黑龙江省可持续农业产业结构优化模型中。黑龙江省农业产业结构优化模型具有大系统、多目标、非线性等特点，传统的求解方法受到了模型复杂程度的限制，由引言可知，遗传算法对解决此类问题具有明显的优势。下面介绍具体采用的遗传多目标算法操作设计以及模型求解过程。 3.5.1遗传多目标算法操作设计 3.5.1.1 实数编码方法 在求解复杂优化问题时，二进制向量表示结构有时不太方便，并且浮点数编码的遗传算法对变异操作的种群稳定性比二进制编码好（徐前锋，2000）。以浮点数编码的遗传算法也叫实数遗传算法（Real number Genetic Algorithms ，简称RGA ）。每一个染色体由一个浮点数向量表示，其长度与解向量相同。假如用向量),(21n x x x X 表示最优化问题的解，则相应的染色体就是 ),(21n x x x V ，其中n 是变量个数。 3.5.1.2 种群初始化方法 遗传算法中初始群体的个体是随机产生的，由于本文优化模型所涉及的变量容易给出一个相对较大的问题空间的变量分布范围，并且若给出一定的搜索空间也会加快遗传算法的收敛速度；因此本文采取3.3.2中的第一种策略，对每一个变量设置可能区间，然后在可能区间内随机产生初始种群。为保证不会遗漏最优解，选择区间跨度范围很大。 3.5.1.3 适应度函数设计 用遗传算法求解多目标优化问题中出现的一个特殊情况就是如何根据多个目标来确定个体的适应值。本文采用Gen 和Cheng 提出的适应性权重方法 （Adaptive Weight Approach ），该方法利用当前种群中一些有用的信息来重新调整权重，从而获得朝向正理想点的搜索压力（玄光男等，2004）。将目标函数按3.3.3所述转化成带有q 个目标（本文模型3 q ）的最大化问题： )}(,),(),({max 2211x f z x f z x f z q q （3-14） 对于每代中待检查的解来说，在判据空间中定义两个极限点：最大极限点 z 和最小极限点 z 如下： },,,{} ,,,{m in m in 2m in 1m ax m ax 2m ax 1q q z z z z z z z z （3-15） 其中m in m ax k k z z 和是当前种群中第k 个目标的最大值和最小值。由两个极限点定义的超平行四边形是包含当前所有解的最小超平行四边形。两个极限点每代更新，最大极限点最终将接近正理想点。目标k 的适应性权重用下式计算： ),,2,1(1 min max q k z z k k k 因此，权重和目标（Weighted-sum Objective ）函数由下面的公式确定 q k k k k q k k k z z x f x f x z 1m in m ax 1)()()( （3-16） 3.5.1.4 遗传操作 （1）选择操作。以比例选择法和最优个体保存法配合使用进行选择操作，即选择过程仍以旋转赌轮来为新的种群选择染色体，适应度越高的染色体被选中的概率越大；另一方面，为了保证遗传算法的全局收敛性，在选择作用后保留当前群体中适应度最高的个体，不参与交叉和变异，同时也确保当前最优个体不被随机进行的遗传操作破坏。 一般图形Voronoi图的离散生成 ————————————————————————————————作者：————————————————————————————————日期： 一般图形Voronoi图的离散生成-工程论文 一般图形Voronoi图的离散生成 刘欣LIU Xin （承德石油高等专科学校社科与数理部，承德067000）（Department of Social Science and Mathematics，Chengde Petroleum College，Chengde 067000，China） 摘要：由于一般图形形状和位置的任意性，一般图形Voronoi图往往比较复杂，难以将传统的构造法直接应用到一般图形Voronoi图的构造中。本文介绍了一般图形Voronoi图的离散构造法，并给出算法步骤及优势分析。Abstract：Because of the random graph shape and position，the general Voronoi graph is often more complex，it is difficult to construct the traditional method of direct application to the general structure of Voronoi graph. This paper introduces the construction method of general discrete Voronoi graph，and puts forword the algorithm steps and its advantages. 关键词：一般图形；Voronoi图；离散生成 Key words：general graphs；Voronoi diagram；discrete generation 中图分类号：TP391 文献标识码：A 文章编号：1006-4311（2015）19-0162-02 基金项目：河北省高等学校科学技术研究项，编号为QN20131159；承德市软科学研究计划项目（承德市公交线路的发展现状与优化分析）：201422123。作者简介：刘欣（1977－），女，河北承德人，承德石油高等专科学校社科数 多目标蚁群算法及其实现 李首帅（2012101020019） 指导老师：张勇 【摘要】多目标优化问题对于现阶段来说，是十分热门的。本文将对多目标规划当中的旅行商问题，通过基于MATLAB的蚁群算法来解决，对多目标问题进行局部优化。 【关键词】旅行商问题；蚁群算法；MATLAB 一、背景介绍 旅行商问题是物流领域当中的典型问题，它的求解十分重要。蚁群算法是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体的模拟进化算法,属于随机搜索算法。M. Dorigo等人充分利用了蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性,通过人工模拟蚁群搜索食物的行为(即蚂蚁个体之间通过间接通讯与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP问题。为区别于真实蚁群,称算法中的蚂蚁为“人工蚂蚁”。人们经过大量研究发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递,从而能相互协作,完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 二、蚁群算法原理介绍 1.蚁群在路径上释放信息素； 2.碰到还没走过的路口，就随机挑选一条路走。同时释放与路径长度有关的信息素； 3.信息素浓度与路长成反比； 4.最优路径上的信息浓度越来越大； 5.最终蚁群找到最优路径。 其实自然界中，蚁群这种寻找路径的过程表现是一种正反馈的过程，与人工蚁群的优化算法很相近。所以我们简单功能的工作单元视为蚂蚁，则上述的搜寻路径过程可以用来解释人工蚁群搜寻过程。 人工蚁群和自然界蚁群各具特点。人工蚁群具有一定的记忆能力。它能够记忆已经访问过的节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规律有意识地寻找最短路径。而自然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者 再经典不过的算法了： // 功能：判断点是否在多边形内 // 方法：求解通过该点的水平线与多边形各边的交点 // 结论：单边交点为奇数，成立! //参数： // POINT p 指定的某个点 // LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致） // int nCount 多边形定点的个数 BOOL PtInPolygon (POINT p, LPPOINT ptPolygon, int nCount) { int nCross = 0; for (int i = 0; i < nCount; i++) { POINT p1 = ptPolygon[i]; POINT p2 = ptPolygon[(i + 1) % nCount]; // 求解y=p.y 与p1p2 的交点 if ( p1.y == p2.y ) // p1p2 与y=p0.y平行 continue; if ( p.y < min(p1.y, p2.y) ) // 交点在p1p2延长线上 continue; if ( p.y >= max(p1.y, p2.y) ) // 交点在p1p2延长线上 continue; // 求交点的X 坐标-------------------------------------------------------------- double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x; if ( x > p.x ) nCross++; // 只统计单边交点 } // 单边交点为偶数，点在多边形之外--- return (nCross % 2 == 1); } 泰森多边形(Voronoi图)生成算法 一、文档目的 本文描述了在geomodel模块中，生成泰森多边形所使用的算法。 二、概述 GIS和地理分析中经常采用泰森多边形进行快速插值，和分析地理实体的影响区域，是解决邻接度问题的又一常用工具。 荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。如图1，其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图，或dirichlet图。 图1 泰森多边形 泰森多边形的特性是： ●每个泰森多边形内仅含有一个离散点数据 ●泰森多边形内的点到相应离散点的距离最近 ●位于泰森多边形边上的点到其两边的离散点的距离相等 泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。 在泰森多边形的构建中，首先要将离散点构成三角网。这种三角网称为Delaunay三角网。 三、Delaulay三角形的构建 Delaunay三角网的构建也称为不规则三角网的构建，就是由离散数据点构建三角网，如图2，即确定哪三个数据点构成一个三角形，也称为自动联接三角网。即对于平面上n个离散点，其平面坐标为(x i，y i)，i＝1，2，…，n，将其中相近的三点构成最佳三角形，使每个离散点都成为三角形的顶点。 图2 Delaunay三角网 模型的建立与求解 一、计算凸多边形的重心 对于任意凸多边形，我们以其重心为蛛网的中枢区中心，也即蜘蛛的等待猎物点，以此点出发，先发出放射丝，再织捕丝。 1.计算任意凸多边形重心的理论基础 1. 四边形的重心作法：连接出四边形的一条对角线，这样四边形就变成两个三角形的组合体，分别作出两个三角形的重心，并连接两个重心成一条线段AB ，同样，连接出四边形的另一条对角线，四边形就变成另外两个三角形的组合体，分别作出这两个三角形的重心，并连接两个重心成一条线段CD ，则线段AB ，CD 的交点就是四边形的重心。 2.五边形的重心作法：连接出五边形的任一条对角线，将五边形分为1个三角形与一个四边形组合体，分 别作出三角形的重心，和四边形的重心，并连成线段AB；连接五边形的另外一条对角形，将五边形分为另1个三角形与四边形的组合体，分别作出三角形与四边形的重心，并连接成线段CD；则AB、CD的交点就是五边形的重心。 3、用数学归纳法，对于六边形、七边形，N边形，都可以用上述方法，先连接出一条对角线，将N边形化为一个三角形与(N-1)边形，或四边形与(N-2)边形，然后分别作出重心，并连接成线段，然后再连接另外一条对象线，分别作出两个组合体的重心并连接成线段，两条线段的交点就是N边形的重心。 2．重心计算的算法程序实现： 有了以上理论基础，我们通过C++语言编写了一个计算任意凸多边形的程序，算法思想如下，算法程序见附录一。 ○1在平面上取一点(一般取原点)得到N个三角形OP[i]P[i+1](其中点的顺序为逆时针) ○2分别求出这N个三角形的重心Ci和面积Ai(注意此处面积是有向面积, 就是用叉乘求面积时保留其正负号) ○3求出A = A1+A2+...+AN(同样保留正负号的代数相加) ○4重心C = sigma(Ai+Ci)/A; 附录一：任意凸多边形重心C++算法 #include 循环算法流程图： 1．若输入a ＝18，b ＝3， 那么输出结果为_____． 2．执行如图所示的流程图， 则输出S ＝_______． 3．下图所示的流程图的输出结果为____． 4．下图所示的流程图的输出结果为____． 5．如图所示的流程图输出的第 2010个数为________． 6．下图所示流程图输入n ＝4， 输出的结果为 5 ． 7．下图流程图，当输入n ＝6时，输出的结果为35． 8．某一计算机运算程序的工作步骤如下： S1 输入数据n ； S2 变量A 与k 的初始值为A ＝3，k ＝1； S3 若k ＜n ，执行S4； 若k ＝n ，执行S7； S4 执行运算B ＝1 1－A S5 将B 的值赋给A ； S6 将k ＋1的值赋给k 后执行S3； S7 输出A ． 若输入n ＝2010，则计算机将输出A ＝__． 9．如下流程图，循环体执行的次数为49． 10．下图流程图所给的运行结果为S ＝90，那么判断框中应填入的判断条件为____． 11．下图流程图输出结果为S＝132，则判断框中应填_____ 12．以下给出的是计算1 2 ＋ 1 4 ＋ 1 6 ＋…＋ 1 20 的 值的一个流程图，判断框内应填入的条件为___． 13．下图流程图是计算1＋1 3 ＋ 1 5 ＋…＋ 1 99 的 流程图，请你补充完整． 14．下图所示的流程图的功能为____．15．下图流程图的执行中依次输入72，91， 58，63，84，88，90，17，55，61，73，64，77，82，94，60．该流程图的功能为___． %遗传算法解决多目标函数规划 clear clc syms x; %Function f1=f(x) f1=x(:,1).*x(:,1)/4+x(:,2).*x(:,2)/4; %function f2=f(x) f2=x(:,1).*(1-x(:,2))+10; NIND=100; MAXGEN=50; NV AR=2; PRECI=20; GGPA=0.9; trace1=[]; trace2=[]; trace3=[]; FielD=[rep([PRECI],[1,NV AR]);[1,1;4,2];rep([1;0;1;1],[NV AR])]; Chrom=crtbp(NIND,NV AR*PRECI); v=bs2rv(Chrom,FielD); gen=1; while gen 正多边形的计算之万法归宗解直角三角形 仪陇县银山初级中学董兴胜各边相等、各角也相等的多边形叫做正多边形，正多边形的外接圆和内切圆的圆心重合叫正多边形的中心。外接圆半径叫正多边形的半径.内切圆的半径叫正多边形的边心距。正多边形的每 一边所对的圆心角叫中心角,中心角的度数是 n 360。 笔者在教学中，发现学生对涉及有关正多边形的计算时，比如计算正多边形的边长，半径，正多边形的周长，正多边形的面积，或者是两个正多边形有关比值的计算，往往无从下手，表现在一遇到题就去画图，下手就算，既费时，又方向不清，结果往往是无功而返。通过多年的教学经验总结，提出了化归思想，即任何正多边形的计算问题都可以转化为一个重要的直角三角形，从而将正多边形的问题转化为解直角三角形的问题。 首先来认识一下正多边形的基本知识，仅以N＝３，４５６为例。 一计算正N边形的内角（如下图） 很容易知道正n边形的每个内角都等于 二将正N边形分割成等腰三角形（如下图所示） 设O为各正多边形的中心，即外接圆和内切圆的圆心，正n边形的n条半径分正n边形为n个全等的等腰三角形． 三将正N边形分割成直角三角形（如下图所示） 这一步只需要作正多边形的边心距，边心距又把上一步n 个等腰三角形分成了个２N 个直角三角形，这些直角三角形也是全等 的．因此正n 边形的半径和边心距把正n 边形分成2n 个全等的直角三角形。 通过这三步，实质是把正多边形的问题向直角三角形转化．由于这些直角三角形的斜边都是正n 边形的半径R ，一条直角边是正n 边形的边心距r n ，另一条直角边是正n 边形边长a n 的一半，一 个锐角是正n 边形中心角 的一半，即 ，所以，就把正n 边形的有关计算归结为解直角三角形问题．为了让学生理解深刻，容易记忆，笔者特总结出如下的口诀和图形： 一个中心，两条半径， 两半径之夹角等于中心角之一半，半径夹角之对边等于边长之一半多边形扫描转换(简化)
正多边形的有关计算一
基于 Voronoi 图的 简单多边形骨架提取
多目标线性规划的若干解法及MATLAB实现
计算机图形学(简单多边形裁剪算法)
Weiler-Atherton任意多边形裁剪算法
基于变分网格的曲面简化高效算法
一种偏向目标型的RRT算法实现
多边形区域算法
多目标规划问题知识讲解
一般图形Voronoi图的离散生成
多目标蚁群算法及其实现
点在多边形经典算法
泰森多边形(Voronoi图)生成算法
任意凸多边形的重心求解
算法流程图
多目标规划遗传算法
正多边形的计算