碰撞检测问题是计算机仿真、CAD、机器人中的一个基本问题，主要用于提高虚拟场景的真实感或进行机器人的路径规划等。不同的碰撞检测基于不同的应用，因此提供的信息也不同。有的应用需要碰撞检测算法给出两物体沿各自运动路径运动过程中是否发生碰撞，有的应用则需要碰撞检测算法不仅给出两物体运动过程中是否碰撞，还需要提供距离信息，即两物体发生碰撞时它们之间的最短穿刺距离，或者两个在运动路径上没有碰撞的物体，它们之间的最短分离距离。目前已有很多种碰撞检测方法，但主要分为两大类：一类是离散的碰撞检测，如基于计算几何的方法、基于分离平面的方法、基于图形硬件的方法等；一类是连续碰撞检测，如扫描卷方法、基于对偶和Minkowski和的方法、基于KDS(Kinetic Data Structure)的方法、代数方法等。离散的碰撞检测方法是对两运动物体在时间轴上采样，在每个采样时刻判断两静态物体是否碰撞。在离散的碰撞检测方法中，如果物体运动速度很快或者物体很小，有可能会检测不到取样时间间隔之内发生的碰撞；缩短采样的时间间隔可以提高精度，但是会降低效率。连续碰撞检测的方法对物体的运动过程进行建模，构造出一条连续的路径，基于路径判断物体间的碰撞情况。本文研究的是利用代数方法进行连续的碰撞检测，提出了两个算法，一个是对两个运动的平面多边形进行碰撞检测，另外一个是对两个运动的LSS(Linearly Swept Spheres)进行碰撞检测以及距离信息的计算。代数方法的求解过程是把两个物体静止时的碰撞条件表达成一个代数条件，然后通过对物体的运动进行建模，将物体的运动表示成关于时间的函数，根据静止时碰撞的代数条件和运动函数将两个运动物体的碰撞条件表示成关于时间的代数条件，通过求解这个代数条件得到两个运动物体的碰撞时间。已有的利用代数方法求解碰撞检测问题是针对椭圆盘和椭球的。平面上运动的椭圆盘的碰撞检测，不能直接用来解决曲线多边形的碰撞检测问题。椭球作为一种包围体对某些物体的包围不够紧，某些物体，如人的手臂，用LSS包围体进行包围效果会更好。已有的对两个运动的平面多边形的碰撞检测，如基于图形硬件的方法和基于KDS的方法，是针对直线段多边形的，其中基于图形硬件的方法使用的是重复检测方法，而基于KDS的方法在解决一般的有理运动时需要将运动在各个方向上进行分解，增加了算法的复杂性。本文主要研究内容有：用二次曲线段集合表示曲线多边形；利用有理运动表示二维和三维空间中的运动；通过对控制点处的动力学镜像进行插值计算得到物体的运动方程；提出两段二次曲线段在有理运动下的碰撞条件；提出直接利用曲线边进行平面多边形碰撞检测的算法；利用多项式的Bernstein形式进行求解；利用包围盒技术提高算法的效率；利用距离公式将两个LSS在三维空间做有理运动的碰撞条件转化成9个多项式，计算9个多项式并对求出的交点进行可用性检验；利用多项式的Bernstein形式进行求解；得到发生碰撞的情况中，两个运动物体的最近穿刺距离和未发生碰撞情况中，两物体在运动过程中的最近分离距离。本文的主要贡献：1)提出两段二次曲线段在有理运动下碰撞的代数条件；2)提出了直接利用曲线边进行平面多边形的碰撞检测算法。该算法比以往的算法更加精确，效率也较高。而且表示曲线多边形的曲线段集合只要求在端点处一阶连续；3)提出作为包围体的LSS的快速有效的碰撞检测算法；得到发生碰撞的情况中，两个运动物体的最近穿刺距离和未发生碰撞情况中，两物体在运动过程中的最近分离距离。