论文研究求两个相交凸多边形并的凸包及交的算法.pdf

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段，利用凸壳顶点有序性，分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q，求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性，使算法的时间复杂度达到最小。