%0 Journal Article
%T A Fast Algorithm to Determine Whether the Intersection of Two Convex Regions Is Empty<br>判断两个凸多面体是否相交的一个快速算法
%A REN Shi-jun
%A HONG Bing-rong
%A HONG Bing-rong
%A <br>任世军
%A 洪炳熔
%A 孟庆鑫
%J 软件学报
%D 2000
%I 
%X Collision 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.
%K Path planning
%K collision detection
%K robot
%K linear inequality<br>路径规划
%K 碰撞检测
%K 机器人
%K 线性不等式.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=11D214D0A099A902&yid=9806D0D4EAA9BED3&vid=708DD6B15D2464E8&iid=E158A972A605785F&sid=8DBE05486163BAB2&eid=6D6B4A516C7DB6EE&journal_id=1000-9825&journal_name=软件学报&referenced_num=14&reference_num=6