于存光YU Cun-guang

（黑龙江科技大学，哈尔滨 150022）

（Heilongjiang University of Science and Technology，Harbin 150022，China）

0 引言

简单多边形核是计算几何的核心问题，它在工程设计、计算机图形学等领域中有广泛应用。求多边形核有很多有效算法，对于多边形无核的研究相对较少，文献[1]给出了一种判断简单多边形的核是否为空的一个快速算法，但对于多边形具有连续凹点情形没有考虑，文献[2]给出无核多边形的一种划分，将多边形分为多个有核多边形，也没有对多边形无核算法进行深入研究。本算法结合多边形凹点情况，提出处理连续凹点多边形无核的平行射线法，给出一种快速判断多边形无核算法，并且当多边形有核时给出多边形核的一个点。

1 算法思想

由n 个顶点构成多边形P，顶点记为v1，v2，…vn，沿多边形顶点顺序，按逆时针行走，多边形P 内部在多边形左侧，这样的多边形称为简单多边形，即非相邻的边不相交。多边形的核K 是指其内部任意一点与多边形边界一点的连线都在多边形内部。由于多边形的凸点在多边形内是可见的，多边形核只与凹点有关，所以本算法只处理凹点。

直线可以表示为Ax+By+C=0 的形式，在直线左侧记为Ax+By+C≥0，直线右侧记为Ax+By+C≤0，这里都包括直线本身。

1.1 线性求交法判断多边形无核或求多边形核一个交点，如果简单多边形不是凸多边形，将多边形的边分为三类：①第一类边，vi是凸点，vi+1是凹点，多边形核只可能在直线vivi+1左侧，即，Ax+By+C≥0。如图1 所示。②第二类边，vi+1是凸点，vi是凹点，多边形核只可能在直线vi+1vi右侧，即Ax+By+C≤0。如图2 所示。③第三类边，vivi+1都是凹点，多边形核不可能在直线vivi+1上。如图3，4 所示。

图1 第一类边

图2 第二类边

图3 射线vi-1vi和射线vi+2vi+1不平行有核

图4 射线vi-1vi和射线vi+2vi+1平行无核

多边形核是判断线性不等式围成凸空间是否为空的问题[3]。这样只需处理两类边在多边形内是否有交即可。文献[1]没有处理连续凹点问题，本算法利用射线平行法迅速判断出多边形无核的情况，有核再利用线性求交计算核的一个点。

1.2 射线平行法处理连续凹点多边形无核，由下面两种情况推广：①对于有两个连续凹点的情况，当射线vi-1vi和射线vi+2vi+1不平行，即相交时，多边形可能有无核；当射线vi-1vi和射线vi+2vi+1平行或大于平行角，即不相交时，多边形无核。如图3，4 所示。②对于有三个连续凹点的情况，当不满足两个连续凹点条件时，当射线vi-1vi和射线vi+3vi+2不平行，即相交时，多边形可能有无核；当射线vi-1vi和射线vi+3vi+2平行或大于平行角，即相交时，多边形无核。对于多于三个连续凹点情况可由这两种情况推广。如图5，6 所示。

2 算法实现

算法：

输入 多边形P 的顶点pi（xi，yi），i=1，2，…n 按逆时针方向排列。

输出 多边形P 无核或多边形核一个点K 坐标。

预处理 确定多边形P 的凸，凹顶点，并对凹点重新编号（逆时针方向排列），标记连续凹点设为R={r1，r2，…rm}，非连续凹点设为Q={q1，q2，…qk}。

Step1 利用射线平行法判断R 顶点多边形无核，输出多边形P 无核。

Step2 利用线性求交法，求Q，R 顶点多边形无核，输出多边形P 无核。

Step3 多边形有核，输出线性求交的交点pj。

3 结论

本算法利用射线平行法可以迅速判断多边形无核情况，然后利用线性求交法处理多边形第一类边和第二类边快速求出多边形无核或核的一个交点。算法预处理只需要线性次乘法便可确定多边形P 各顶点的凸凹性，并记住凸凹顶点。Step1 处理至多m 次求平行运算。Step2 判断qi的第一类边或第二类边相交情况需要k 次求交，判断rj各类边需要m 次求交，最后还要求与多边形求交，整个循环需要nmk 次求交。所以本算法求多边形无核及多边形核一个交点时间复杂度O(nmk)。

[1]王钲旋,徐长青,庞云阶.判断简单多边形的核是否为空的一个快速算法[J].计算机辅助设计与图形学学报,2000,12(9):656-659.

[2]汪嘉业，汪卫.简单多边形分解成凸多边形差组合的算法[J].计算机辅助设计与图形学学报，1992，4(2):22-29.

[3]任世举，洪炳熔.判定由线性不等式围成的凸空间是否为空的一个快速算法[J].计算机学报，1998，21(10):896-901.

[4]周培德.计算几何——算法设计与分析（第二版）[M].清华大学出版社，2001.

[5]陈炳发，钱志锋，廖文和.简单多边形凸凹性的自识别算法[J].计算机辅助设计与图形学学报，2002，14(3):214-217.

[6]Etzion M,Rappoport A.On Compatible Star Decompositions[J].IEEE Trans-actions on Visualization and Computer Graphics,1997,3(1):87-95.