【摘要】 提出了求解平面上两个平移简单多边形在碰撞前最大可移动距离和碰撞时间的算法。该算法的时间复杂性为Ｏ（ｎｌｏｇｍ ＋ ｍ ｌｏｇｎ），其中ｍ 和ｎ 分别是两多边形的边数。本文还证明了这一算法是稳定而有效的。更多还原

【Abstract】 Movement interference detection is widely used in robotics and CAD/CAM. The existing methods for detecting interference between moving objects are for convex polygons or simple polygons whose convex envelops do not intersect. We present a method for detecting interference between any two simple polygons. Such a method, to our best knowledge, has not been reported in the open literatures. In subsection 2.1, we give the optimal algorithm for movement interference detection involving step 1 through 8. In subsection 2.2, we describe the algorithm in detail. We first simplify the problem by coordinate shift so that only one object is moving in this new coordinate. Then, we get an initial vertices subset in this new coordinate. After that, we further trim the subset by deleting the concave vertices. We use the trimmed subset to compute the minimum collision distance. The algorithm′s time complexity is O(n log m+m log n), where m and n donote the number of vertices of each polygon. Simulation result (section 3) shows that our algorithm is stable and effective.更多还原