ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.4P.563-568




ж͹Ƿཻһ㷨
ۡ
ժҪڻ·滮,ײ㷨ռʮҪĵλ.ܻ˷ϵͳ,ײõʱ·滮ʱռ൱ı.ǣνһײٶܻ·滮ϵͳо˷ǳؼ.ײתΪжάռ͹Ƿཻ.һ,һµ㷨,˼ȡһһ͹ָһ,еһλùϵѰཻƽ.Ľλһƽ棬ҵһཻƽԶ϶ཻ.
ؼʡ·滮,ײ,,Բʽ.
ͼšTP242
A Fast Algorithm to Determine Whether the Intersection of Two Convex Regions Is Empty
REN Shi-jun
Department of Computer Science and EngineeringHarbin Institute of TechnologyHarbin150001
Department of Mechanical EngineeringHarbin Engineering UniversityHarbin150001
HONG Bing-rong
Department of Computer Science and EngineeringHarbin Institute of TechnologyHarbin150001
MENG Qing-xin
Department of Mechanical EngineeringHarbin Engineering UniversityHarbin150001
AbstractCollision detection algorithms play a very important role in the field of robot path planning. In a simulation system of intelligent robot, collision detection takes up a large portion of the time for the robot to plan a complete path from the initial position to the final position. So how to reduce the time the robot uses to detect collision becomes a key problem. But collision detection finally will transform to a problem to determine whether the intersection of two convex regions formed by linear inequalities is empty or not. The authors present a new algorithm in this paper. Firstly, a vector pointing from one polyhedron to the other is picked. Then the authors start to find an intersection plane of one polyhedron based on the scalar product of the norm vector of the plane and the picked vector. If such a plane is found, the intersection of the two convex polyhedra is not empty.
Key wordsPath planning, collision detection, robot, linear inequality.
ڻ·滮㷨УײռʮҪĵλ,ڻ˵Ĺռ͹ģۡϰȵ.ڻ·滮,ҪϰԼее֮Ƿײ,Ҫ͹γɵļ֮Ƿн.н,˵ϰײ߻ееײ,˵ϰﲢײ.ײ㷨Ǵӿռ伸ѧĽǶȣ1ݻŻĽǶȣ2,3ݳ,Ҫ.ڱУǸһ㷨ռе͹ײ.ڻ˵ķϵͳУ(еۺϰ)ĽģüͼѧеB-repʽ߽ʾʽ.һ3Ҫ,㡢.ڼд洢һһǴ洢˽ṹ(ָ㡢֮Ĺϵ),㼰ķ.ڻеۺϰ˶жҪʵʱؼÿһ㼰ķ̣ȷλ.
nάռԲʽΧɵ͹AB,Ƿֱʽ(1)ʽ(2)
(1)
(2)
pi=(pi1,pi2,...,pin)T,ri=(ri1,ri2,...,rin)T,x=(x1,x2,...,xn)T,ʽ(1)ɱʾΪ

ʽ(2)ɱʾΪ

1㷨ۻ
1. g=(g1,g2,...,gn)TΪAı߽,tA,Ҷڦ(01gt-gA,ôһi0ʹ1i0m,pTi0g-t0pTi0g=qi0.
֤:gΪAı߽,AΪ͹,gA.
,֤һi0ʹ1i0m,pTi0g=qi0.Ϊ,i1impTigqi.ڶi1im)ĵλe,

ʦģ0.x,ֻҪx-g,pTix=pTig+pTi(x-g),pTi(x-g)ܡpiȡ
ӶpTixpTig+(qi-pTig)=qi,1im,xA.ӶgΪAڵ,ì.
,֤pTigqiiһһi0ʹ1i0m,pTi1g-t0.I1ipTigqi1im,I2={iiI11im.iI1pTig-t0.iI2ʹpTig-t0,ȡ1ȡ1=1.iI2,pTit-g0,ôpTitg0,ôpTig1tg=pTig+1pTitgqi.ɼ֪,iI1,pTig1tg=pTig1pTitgpTigqi.g1tgA,붨ì.

2. sA,tB,ʹsB,tA,ôAB٦,һi0,ʹ1i0m,pTi0st0,ABɣxpTi0xqi0٦.Ҳһi1,ʹ1i1n,rTi1st0,ABɣxrTi1xsi1٦.
֤:AB٦.÷֤.i1im,ֻҪpTist0ABɣxpTixqi,༴ڼϦɦ,ԼpTixqi,ôA1xpTixqipTigt01im,ABA1B.
(1)  0,ʹ001,s0tsAB.
(i) tBB͹,Զڦ0ܦ1stsB.
(ii) ڦ0ܦ1i1impTist0sA,
pTis+tsݣpTispTitspTisqi,
Ƕڦ0ܦ1stsA1.
(i)(ii)֪,ڦ0ܦ1stsA1BABA.1ʱ,stsstst,tA.ì.
(2) ڦ0ܦ1st-sAB.st߶ûABĵ.AB͹(͹ĽΪ͹)ҷǿ,,ȡһgABʹgstֱߵľ.0,ڿռȡһgt-s.Ϊӵstֱӵggtsֱ໥ƽ,,stggt-sλͬһƽ沢stgtsg߶ιһƽı.˵gtsA,sAsgts߶ҲA.ͬtg߶B.εԽߵĽABӶAB.㵽stֱߵľgstֱߵľ,ì.ǣڦ0gtsA.gΪAı߽.ݶ1֪һi0ʹ1i0m,pTi1gt0pTi0gqi0.,ΪsA,pTi0stpTi0ۣsggt=pTi0sgpTi0gt=pTi0sqi0+pTi0gt0.֤.

2жϿռ͹Ƿཻ㷨
㷨Ҫõף4λ㷨.жϿռһԲʽΧɵ͹ռǷǿռ.ǿռ򷵻еһ.
GΪһ̬(һάάԼάռеһ),AΪһԲʽ,xiangliang(A)ʾжAȷļǷǿռλ㷨,㷨Աʾ.
xiangliang(A)

Step 1. Aкìܳʽ,򷵻NULL.
Step 2. AеĲʽյ1ϵڡںС0ԭֳ3A1,A2A3.
Step 3. A1Ҧ3,ȥAеĵ1.ٴεxiangliang(A).G=xiangliang(A).GӦĵ1һʵһΪG.G.
Step 4. A1ߦ3,A2еĵ1ȥ,G=xiangliang(A2)(A2ȡGΪȫ0).1,õ1ִ.3,õ1С.вʽĵ.õĵ1Gһ𹹳µGG.
Step 5. A1еĲʽĸСڻߵA3еĲʽĸ,ȡA1еĲʽ,Ϊʽ(Ϊd),ʽ,õµĲʽ,ʹеıAеıĸ.G=xiangliang().G=NULL,ȡһʽ.ִ.GdһGһµG.G.вʽȡ,򷵻NULL.
Step 6. A1еĲʽĸA3еĲʽĸ,ȡA3еĲʽ,Ϊʽ(Ϊd),ʽ,õµĲʽ,ʹеıAеıĸ.G=xiangliang().G=NULL,ȡһʽ.ִ.GdһGһµG.G.вʽȡ,򷵻NULL.

ABֱʾԼռе͹Բʽ,qiujiao(A,B)ʾȷA,BĽǷǿռ㷨,㷨Աʾ.
BOOL qiujiao(A,B)

Step 1. ԼAԼBĲʽΪʽҲìܲʽreturn TRUE.
Step 2. ԼAԼBĲʽìܲʽ,return FALSE.
Step 3. s=xiangliang(A),t=xiangliang(B).
Step 4. s=NULLt=NULL,return FALSE.
Step 5. sBtA,return TRUE.
Step 6. ԼAĲʽĸԼBĲʽĸ,ôѡԼAĲʽʹøòʽķts0.øòʽԼABĲʽõʽA1B1,ʹA1B1еıABбĸ.ظһ,qiujiao(A1B1)=TRUE,return TRUE.򣬼ִ.
Step 7. ԼBĲʽĸԼAĲʽĸ,ôѡԼBĲʽʹøòʽķtsС0.øòʽԼABĲʽõʽA1B1,ʹA1B1еıABбĸ.ظһ,qiujiao(A1,B1)=TRUE,return TRUE.򣬼ִ.
Step 8. return FALSE.

һʵʵĻ˷ϵͳпжİΧ(bounding box)Ƿཻཻ͹Ҳཻ򣬽һ㷨ж͹Ƿཻ.ײЧ.
3ʵ 
1:άռи͹ABͼ1ʾ.

Fig.1 Two intersected polyhedra
ͼ1ཻ͹

Fig.2 Two polyhedra intersected on only edges not vertex
ͼ2ֻǵཻ͹
͹ƽ淽̷ֱɷ(3)(4).
(3)
(4)
λ㷨ʽ(3)ʽ(4)е(0,0,0)(-0.5,0.5,0.5).ڵ(-0.5,0.5,0.5)ʽ(3),͹ཻ.
2:άռи͹ABͼ2ʾ.
͹ƽ淽̷ֱɷ(5)(6)
(5)
(6)
λ㷨ʽ(5)ʽ(6)е(0,0,-2)(-0.5,0.5,0.5).ʽ(5)еĲʽĸʽ(6)еĲʽĸ.ȡʽ(5)еĲʽ.ڴʱt-s=(-0.5,0.5,2.5),ֻе4ʽӦƽ淽̵ķt-s0,Ϊʽ,ʽ(5)ʽ(6)Ϊ
(7)
(8)
λ㷨ֱʽ(7)ʽ(8)е(0,0)(-0.5,0.5).(-0.5,0.5)ʽ(7),ʽ(7)ʽ(8)Ľ.Ӷʽ(5)ʽ(6)ĽҲ.
4ʵ
IBM 486ʵ㷨,ͨݶ㷨˲,1.
Table 1Experimental results of the algorithm (Experimented on IBM 486)
1㷨ʵ(IBM 486ִ)

Problem scaleExecution time(s)
No. of A's constraintsNo. of B's constraintsNo. of instancemaximumminimumaverage
60 60300.030.010.01
8060300.040.010.01
8080200.060.020.03
100100200.140.070.09
250250201.931.21.52

ģ,ִʱ(),ԼĿ,,ִʱ,ִʱ,ƽִʱ.
ӱ1ʵԿ㷨ǳЧ.һʵʵĻ˹滮ϵͳִһ㷨֮ǰж͹İΧǷཻ,Ȼһ㷨ж.ܹһ߹滮ϵͳײЧ.
̴ѧ繤ѧԺ150001
ҵѧѧ빤ϵ150001
ۣҵѧѧ빤ϵ150001
Σ̴ѧ繤ѧԺ150001
ο
1Liu Lian-feng, Wang Yong-xi. A three dimensional algorithm on detecting collision between robot and its environment. Robot, 1996,18(1):5054
(,Ӿϲ.ռ·滮һά㷨.,1996,18(1):5054)
2Zeghloul S, Rambeaud P. A fast algorithm for distance calculation between convex objects using the optimization approach. Robotica, 1996,14:355363
3Bobrow J E. A direct minimization approach for obtaining the distance convex polyhedra. International Journal of Robotics Research, 1989,8(3):6576
4Ren Shi-jun, Hong Bing-rong. A fast algorithm to determine whether convex regions bounded by multiple linear constraints are empty. Chinese Journal of Computers, 1998,21(10):896901
(,.жԲʽΧɵ͹ռǷΪյһ㷨.ѧ,1998,21(10):896901)


