非自交多边形的轮廓内缩外扩算法

太过爱你忘了你带给我的痛 2022-11-05 14:53 160阅读 0赞

### 文章目录 ###

*   *  1. 项目介绍
     *  2. 算法步骤
     *   *  2.1 内缩点的生成
         *  2.2 无效内缩线段的处理
         *  2.3 全局无效环的处理
     *  3. 使用方法及结果演示
     *   *  3.1 使用方法
         *  3.2 结果演示
     *  4. 不足之处
     *  5. 参考资料

## 1. 项目介绍 ##

本项目是论文A new offset algorithm for closed 2D lines with Islands的JAVA实现。  
**本项目的GitHub地址：https://github.com/Lee-0o0/polygon-offset-algorithm。欢迎大家star！**

该论文主要描述了多个非自交多边形轮廓内缩算法，何为轮廓内缩？就是将轮廓线向着多边形内部进行等距离缩进，在内缩过程中，需要解决新的轮廓点确定、自交点的去除等问题。用论文中的示意图演示如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center]

## 2. 算法步骤 ##

该算法主要包括三个步骤。

### 2.1 内缩点的生成 ###

现有一个轮廓点序列P，为了生成内缩点，首先需要确定轮廓点的类型：

轮廓点类型：

1.  凸点：以该轮廓点为顶点的内部角小于180°，如图a；
2.  凹点：以该轮廓点为顶点的内部角大于180°，如图b；
3.  平点：以该轮廓点为顶点的内部角等于180°，如图c；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 1]

假设缩进距离为R，轮廓点 P i P\_i Pi的缩进点表示为 Q i Q\_i Qi。 P i − 1 P\_\{i-1\} Pi−1表示 P i P\_i Pi的前一个轮廓点， P i + 1 P\_\{i+1\} Pi\+1表示 P i P\_i Pi的后一个轮廓点，则 θ i θ\_i θi表示 P i − 1 P i P\_\{i-1\}P\_i Pi−1Pi和 P i + 1 P i P\_\{i+1\}P\_i Pi\+1Pi之间的夹角。向量 e i e\_i ei和 e i + 1 e\_\{i+1\} ei\+1分别表示从 P i − 1 P\_\{i-1\} Pi−1指向 P i P\_i Pi和 P i P\_i Pi指向 P i + 1 P\_\{i+1\} Pi\+1的单位向量。

![在这里插入图片描述][20210306231814833.gif_pic_center]  
![在这里插入图片描述][20210306231834640.gif_pic_center]

如果轮廓点Pi是凸点，如图a，则内缩点生成公式为：

![在这里插入图片描述][20210306231913901.gif_pic_center]

如果轮廓点Pi是凹点，如图b，则内缩点生成公式为：

![在这里插入图片描述][20210306231936373.gif_pic_center]

如果轮廓点Pi是平点，如图c，则内缩点生成公式为：

![在这里插入图片描述][20210306231948318.gif_pic_center]

**由于无法找到方法确定每个点的类型，则采用如下方法确定内缩点：**

*  首先通过角平分线确定内缩点的方向，即单位向量 P i P i − 1 P\_iP\_\{i-1\} PiPi−1和 P i P i + 1 P\_iP\_\{i+1\} PiPi\+1相加确定内缩点方向；
 *  然后将每个点作为凸点计算内缩点距离，得到确定的内缩点；
 *  通过射线法确定内缩点是否在轮廓内，如果在轮廓内，则表示该点是正确的内缩点；如果不在轮廓内，则表示相反的方向，相同的距离是正确的内缩点。

### 2.2 无效内缩线段的处理 ###

如果轮廓线段过短，并且缩进距离过大，就有可能产生无效内缩线段，如图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 2]

为了保证内缩轮廓的准确性，我们需要对无效内缩线段进行处理。首先，需要识别所有的无效内缩线段，然后进行处理。

首先我们需要识别无效内缩线段，利用无效内缩线段的方向与原轮廓线段方向相反的特点进行识别。即若轮廓点 P i P\_i Pi， P j P\_j Pj的内缩点分别为 Q i Q\_i Qi， Q j Q\_j Qj，则可以根据两向量点积的正负值判断：

![在这里插入图片描述][20210306232027972.gif_pic_center]

当识别了所有的无效内缩线段后，则根据无效内缩线段是否连续分为两种处理方式：

情形一：无效内缩线段不连续，即一条无效内缩线段的相邻线段都是有效内缩线段；

情形二：无效内缩线段连续，即存在至少两条无效内缩线段相邻；

在提出无效内缩线段的解决方法之前，我们提出两个概念：前置边和后置边。按照轮廓方向遍历，前置边是指无效内缩线段按照轮廓方向向前的第一条有效内缩线段，同理，后置边是指无效内缩线段按照轮廓方向向后的第一条有效内缩线段。

现在我们考虑情形一的处理方法，即无效内缩线段不连续。处理步骤如下：

（1）计算无效内缩线段的前置边和后置边的交点P；

（2）更新无效内缩线段的前置边的起点为交点P，更新后置边的终点为P；

算法图示如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 5]

现在我们考虑情形二的处理方法，即无效内缩线段连续。处理步骤如下：

（1）找到无效内缩线段所对应的原轮廓边，并采用传统的线段内缩方法得到新的对应的内缩线段；

（2）分别计算新的内缩线段与原轮廓的交点，并更新新的内缩线段；

（3）分别计算新的内缩线段与前置边和后置边的交点，并更新前置边的起点为交点，后置边的终点为交点；

（4）计算前置边和后置边的交点，并更新前置边的起点为交点，后置边的终点为交点。

算法图示如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 8]

### 2.3 全局无效环的处理 ###

在处理了无效内缩线段后，全局无效环有可能出现，如图所示：  
![在这里插入图片描述][20210306232402986.png_pic_center]

为了保证结果的准确性，我们需要消除全局无效环。在进行详细算法描述之前，我们需要确定追踪规则。

追踪规则：从起始点沿着轮廓方向进行追踪，如果遇到自交点，则将自交点存入栈中，作为下一个起始点，并改变追踪方向为相交线段的方向。

算法主要包括四步：

（1）在内缩轮廓中任意选取一个起始点，并标记为已访问；

（2）遵循追踪规则进行内缩轮廓点的访问，如果该点未被访问，则进行已访问标记；如果访问的该点与起始点相同，则表示已访问了一个环，进行下一步判断。如果该点已访问，则表示原轮廓过于复杂，生成的内缩轮廓存在异常情况，此时应结束整个算法流程。

（3）如果该环的方向与原轮廓的方向相同，则表示该环不是全局无效环，接纳为有效内缩轮廓；反之则舍弃。

（4）如果栈不为空，则将栈顶元素弹出作为起始点，然后进行步骤（1）——（3），直至栈为空。

最终，所有返回的环就是内缩轮廓结果，如图所示：

![在这里插入图片描述][20210306232412556.png_pic_center]

## 3. 使用方法及结果演示 ##

### 3.1 使用方法 ###

首先，从release中下载jar包，然后导入到自己的工程项目中。

然后创建多边形的点列表，调用算法，画图显示结果。

**注意**：如果每层之间的距离是负数，则会生成外扩轮廓。

// import com.lee.algorithm.OffsetAlgorithm;
    // import com.lee.display.MainWindow;
    // import com.lee.entity.Point;
    
    // 准备多边形数据
    List<Point> polygon = Arrays.asList(
        new Point(100,100),
        new Point(200,100),
        new Point(300,200),
        new Point(200,300),
        new Point(100,300)
    );
    // 结果数据
    List<List<Point>> contours = new ArrayList<>();
    contours.add(polygon);
    // 生成5层内缩轮廓，每层之间的距离为10
    for (int i = 1; i <= 5; i++){ 
        List<List<Point>> offset = OffsetAlgorithm.offsetAlgorithm(polygon, 10*i);
        if (offset != null) { 
            contours.addAll(offset);
        }
    }
    // 画图显示
    MainWindow mainWindow = new MainWindow(contours);
    mainWindow.show();

结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 9]

### 3.2 结果演示 ###

本节主要演示各种不同的图形生成内缩轮廓效果。主要的代码文件在`test/com/lee/test/OffsetTest.java`中，多边形轮廓点数据在`file`文件夹下。

// 生成三角形的内缩轮廓，共十层内缩轮廓，每层之间的距离为3.0 
    offsetTest("file/triangle.txt",3.0,10);

结果演示：最外层是原始的多边形轮廓

![在这里插入图片描述][20210306232508123.png_pic_center]

offsetTest("file/rectangle.txt",3.0,20);

![在这里插入图片描述][20210306232522525.png_pic_center]

offsetTest("file/star.txt",3.0,10);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 10]

offsetTest("file/tunnel.txt",3.0,25);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 11]

offsetTest("file/5edge.txt",5.0,5);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 12]

## 4. 不足之处 ##

*  对于本算法，如果内缩的距离过大或多边形过小，则会导致结果的不准确。
    
    例如：内部已经出现轮廓相交缠绕的情况。
    
    解决方法：可以以内缩轮廓为原始轮廓，再次小距离缩进。不要以最初的轮廓进行大距离缩进。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 13]

*  对于自交的图形，本算法无法解决；对于曲线图形，本算法无法解决。针对这两个问题，GitHub有相关项目已经解决，具体可参考：https://github.com/jbuckmccready/CavalierContours，相关论文可参考：An offset algorithm for polyline curves
 *  对于工程结构、算法细节来说，本项目还有待提升。

## 5. 参考资料 ##

\[1\] Kim, H.-C., Lee, S.-G., & Yang, M.-Y. (2005). A new offset algorithm for closed 2D lines with Islands. The International Journal of Advanced Manufacturing Technology, 29(11-12), 1169–1177. doi:10.1007/s00170-005-0013-1

\[2\] Liu, X.-Z., Yong, J.-H., Zheng, G.-Q., & Sun, J.-G. (2007). An offset algorithm for polyline curves. Computers in Industry, 58(3), 240–254. doi:10.1016/j.compind.2006.06.002

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/4e89739a300041ba810f33352960c850.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/f81d9ba606c74efb9b14225b5f151e5b.png
[20210306231814833.gif_pic_center]: /images/20221023/273db61cdef54fe0bbbc188e02993385.png
[20210306231834640.gif_pic_center]: /images/20221023/ac46c5b66e624d41ab6880d8dc0b1c77.png
[20210306231913901.gif_pic_center]: /images/20221023/0d42e09864e14a49b1125a0bfa3c2fb9.png
[20210306231936373.gif_pic_center]: /images/20221023/6c4696f3e618411cbfb5f879dc4b056e.png
[20210306231948318.gif_pic_center]: /images/20221023/e0900cc21cc74d5c9338acfe0e526102.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221023/7dc71d37af2e4658902229d9b46c9de7.png
[20210306232027972.gif_pic_center]: /images/20221023/f2caac4637984d58b462eb745bf3b851.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221023/fcbeb2d2d2ce4d64bac1469db2d33e54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221023/44bcb4a6901b46b3955b8ee3a4047236.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221023/0b6d23b200264c1d856e5905df3e5f5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221023/ddd4330a7c6747fe9165d24709196d93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221023/eda1b485b05f4df4846489f695aeab77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221023/b90b04a31d104747a58a0a31344591f6.png
[20210306232402986.png_pic_center]: /images/20221023/72e10b80229b4a0f9c48d1f8607b063a.png
[20210306232412556.png_pic_center]: /images/20221023/2ea9aa8888a14ed08fe6fd4be5012369.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221023/debb8254e07749c4824ac8b5c7ccd1ca.png
[20210306232508123.png_pic_center]: /images/20221023/883eaaeff86c486fb2ee88d4df99d538.png
[20210306232522525.png_pic_center]: /images/20221023/1cd92740cc96489a8b7f67b579f0825a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221023/0f7e97e59f9847a8b2ec06d31a2a0c7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221023/308f1e9958644a80bdfb635a250997f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221023/529a0b68b39e4b88b061ebec840ad9f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjYxMjUx_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221023/5c2920c199214ebea51a00251b14b8ea.png