Let P=(po, p1,..., pn-1 ) and Q=(qo,q1..., qm-1) be two arbitrary convex polygonsin plane. In this paper, the author studies the problems of how to quickly determine their possiblecollision range and movable range. In...Let P=(po, p1,..., pn-1 ) and Q=(qo,q1..., qm-1) be two arbitrary convex polygonsin plane. In this paper, the author studies the problems of how to quickly determine their possiblecollision range and movable range. In the paper, a new sufficient and necessary condition for decidingpossible collision is proposed,and the basic characters of the oblique supporting lines are investigated,and on these grounds the problem to determine the possible collision range is transformed into thatof searching the supporting points on the sets of convex polygon vertexs. Using the strategy ofsearching simultaneously the sets of vertexes of P and Q, the author constructs the fast algorithmfor finding the supporting points, the time-complexity of which is O(log2(m + n)). Based on theseresults, the algorithms to quickly determine the range are given, which possess the time-complexityof O(log2(m+n)).展开更多
文摘Let P=(po, p1,..., pn-1 ) and Q=(qo,q1..., qm-1) be two arbitrary convex polygonsin plane. In this paper, the author studies the problems of how to quickly determine their possiblecollision range and movable range. In the paper, a new sufficient and necessary condition for decidingpossible collision is proposed,and the basic characters of the oblique supporting lines are investigated,and on these grounds the problem to determine the possible collision range is transformed into thatof searching the supporting points on the sets of convex polygon vertexs. Using the strategy ofsearching simultaneously the sets of vertexes of P and Q, the author constructs the fast algorithmfor finding the supporting points, the time-complexity of which is O(log2(m + n)). Based on theseresults, the algorithms to quickly determine the range are given, which possess the time-complexityof O(log2(m+n)).
