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

【文件属性】：
文件名称：论文研究-求两个相交凸多边形并的凸包及交的算法.pdf
文件大小：596KB
文件格式：PDF
更新时间：2022-10-03 05:16:01
论文研究 凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段，利用凸壳顶点有序性，分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q，求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性，使算法的时间复杂度达到最小。