图3
证明:
???OB?BD?OB?BC?CD
显然:
??CD?AE
?又?OB?BC?OB?BC?OC?OA
????OB?BC?CD?OA?AE ??即OB?BD?OA?AE
5.1.2 对直线与圆相切的关系
根据对题目的分析, 可以知道机器人避开障碍物应该是与障碍物的顶点为圆心的圆相切. 因此对机器人走的直线与障碍物的顶点为圆心的圆相切几种情况进行分析. 情况1 直线与一个圆相切
图4: 直线与一个圆相切的图形
已知: 如图4所示, 过A, B点作圆O的切线分别为F, E. A(x1,y1) B(x2,y2) O(x0,y0) ?AOF??, ?AOB??, ?BOE??, ?FOE??, OF?OE?r.
?求: 1)线段AF; 2)线段EB; 3)圆弧FE; 4)点F; 5)点E.
解: 1)
?AO?(x1?x0)2?(y1?y0)2
5
BO?(x2?x0)2?(y2?y0)2 AB?(x2?x1)2?(y2?y1)2
?AF?(x1?x0)2?(y1?y0)2?r2
2) 同理求得:
BE?(x2?x0)2?(y2?y0)2?r2
3)
??arccos(r) AOr) BO22??arccos(2??arccos(AO?OB?AB2?BO?AO)
??360???????
??r?FE= ?1804)
sin?EBO?rr ??EBO?arcsinOBOB设直线BE的斜率为k2, 直线OB斜率为k1 由直线夹角公式, 可知:
tan?EBO?k1?k21?k1k2
k1?解得k2值为:
y2?y0
x2?x0k2?其中
k1?tan?EBO
1?k1tan?EBOr OB?EBO?arcsin
6
EB直线方程:
y?y2?k2(x?x2) ( 1 )
圆方程:
(x?x0)2?(y?y0)2?r2 ( 2 )
综合（ 1 ）（ 2 ）式解方程组可得到E点坐标.
5） 同理可求出F点坐标
情况2 直线与两个圆外切
两圆重合后的计算方法类似于情况1.
图5: 直线与两个圆外切的图形 图6: 将两个圆合并后的图形 已知：过A, B作圆C和圆D的切线，切点分别为F,G.EH为两圆的外切线,且EH=CD. ?CD//EH且CD?EH, CE?CD
?四边形EHDC为平行四边形
所以需求的长度即为情况1 的计算结果加上EH即可. 情况3 直线与两圆内切
图7: 直线与两个圆内切的图形 图8: 拆分图 如图5所示:
?F, H分别为圆C,D的切点, 又?圆C，圆D的大小相同
??EMC??HMI???CEM??DIM??FCM??IHM ?CE?DI?
7
则
EM=MI
即M总坐标为:
?x3?x4y3?y4?,?? 22????连接BMAM把图7分割成如图8所示的两个图为BEFM与AIHM
再利用情况1的解法, 得到相关的结果. 5.2问题一模型的建立与求解 5.2.1 思路与算法 一、基本思路
首先对路线进行粗选, 对粗选后的路线看作无向图, 采用求最短路线问题的方法, 运用Dijkstra算法选择最优路径. 二、粗选依据
(1)当两点间可经直线到达, 则选直线为路径(直线优先)
(2)当无法按照直线到达时, 则选上下的两条路径绕过障碍物, 并根据定理5.1.1的定理原则选择贴近障碍物的路径. 三、Dijkstra算法 步骤:
( 1 )赋初值:
令S?{u0},l(u0)?0.?v?S?V\\S,令l(v)?W(u0,v),z(v)?u0,u?u0.
( 2 )更新
l(v),z(v):?v?S?V\\S,若l(v)?l(u)?W(u,v),则令：l(v)?l(u)?W(u,v),z(v)?u. ( 3 )设v?是使l(v)取最小值的S中的顶点，则令S?S?{v?},u?v?. ( 4 )若S??,转（2）；否则，停止. 5.2.2 对O→A路径的求解
图9: O→A的路线图 图10: O→A最终路线图
再通过matlab软件(程序见附件1)计算出O→A从障碍物5的右下角时, 路径
8
L=492.86个单位. 从障碍物5的左上角时, 路径L=471.04个单位. 则最短路程是从O经过障碍物5的左上顶点进行转弯到达点A. 如表1所示.
表1：机器人从O→A经过的最短路线 经过圆心 前切点 后切点 圆弧长度 到前一点的点 切线长度 O (0, 0) b (80, 210) (70.51, 213.14) (76.61, 219.41) 9.05 224.72 A (300, 300) 237.25 总路程: L=471.04个单位 总时间: t?96.02秒 注: 例如前切点(70.51, 213.14)表示O到障碍物5的左上角小圆的切线的切点. 后切点(76.61, 219.41)表示A到障碍物5的左上角小圆的切线的切点. 5.2.3 对O→B路径的求解
得到如图11所示可能路线
图11: O→B的路线图
1、根据粗选原则得到图11, 并转化为有向图.如图12所示.
将图7路线看做为有向图O→B, 运用图论的方法来确定最短的路线, 如图8所示
a h O b c g B d e f j
9