算法 & 数据结构——多边形填充

作者: 落单的毛毛虫 | 来源:发表于2019-04-13 20:08 被阅读89次

在很多图形相关的编辑器里都会有选区功能,有的只能按某种固定形状选择,比如:矩形,圆形……,有的可以按任意形状选择,有的甚至可以分析图片自动选区(例如:Photoshop魔法棒工具),今天来说说任意形状选区怎么实现。

通过鼠标描点,再用线段连接,组合成一个几何选区,这看似没有难度,它实际上……的确没有难度。如果要填充选区内部,这就有一丢丢难度(至少很久前我被这个问题困住很久)。

计算机图形接口

在计算机里,图片普遍都是矩形的,当渲染一张图片到屏幕时,这张图片会被拆成两个三角形,这两个三角形将图片斜角对折切开,然后提交到渲染管道,而这个渲染管道则由显卡接管。

至于为什么会被拆成三角形,因为计算机3D渲染技术已经非常成熟,而3D渲染完全可以渲染2D图像,因此显卡只需要按3D渲染的架构设计就可以了,但是,3D图形比2D图形复杂的多,因为2D形状统统都可以在一个矩形的图片上画出来,而3D要显示一个形状需要模型,而怎么构建这个模型就成了问题。例如:立方体模型,六个面,那可以用六个正方形来构建。但是球形或更复杂的模型,纯用正方形去拼凑完全不可能,因此这可能需要各种各样的形状,从而导致非常凌乱。如果有一种图元可以拼凑出任意形状的模型,那一切都完美,三角形正是这样的图元,它虽然不能完美拼凑任意形状的模型,却可以在硬件允许的情况下无限近似任意形状的模型。当前流行的显卡通常只支持三角形硬件加速,听说俄罗斯还有人搞圆形硬件加速的?
上面大概已经说明三角形和渲染管道的关系了,下面进入正题。

闭合路径

要填充一个不规则的选区,要把它拆分成多个三角形,而怎么拆分成三角形就是问题所在。

任意形状选区

在拆分三角形之前,需要计算出选区内包含的所有闭合路径,因为一个选区可能会有多个闭合路径,就像上图显示,选区包含了两个闭合路径,要填充这两个闭合路径.

选区的数据结构是一组顶点列表[p0, p1, p2...pN]
从 p2 开始遍历:
pi -> p(i+1) 正好构成一条线段,将这条线段与前面的线段做相交检测,一旦相交,则说明此时遇到了一个闭合路径.
记录交点CrossP,
记录交点线段的起点CrossA,
记录交点线段的终点CrossB.
[CrossP, CrossB, ..., pi] 顶点列表则是该闭合路径.
随后将这个闭合路径的顶点列表从原始顶点列表中剔除,并将CrossP插入到CrossB的位置.
直到把原始顶点列表遍历完毕,则所有的闭合路径都被计算出来了.

三角形切割

已经得到了所有的闭合路径,接下来就可以切割三角形了.这非常容易,因为每一个闭合路径都是一个多边形,只需要求得这个多边形的中点,再从中点依次连接到各个顶点就可以了.

切割三角形

从图中可以清楚的看到闭合路径的中心,以及从中心连接到各个顶点的线段,因为图中的闭合路径只有四个顶点,因此只需要切割四个三角形就足够了.
计算多边形中心的公式:

(p[i] + p[i+1] + p[N]) / N

如果一切都是这么容易,那活着就舒坦了,几何学告诉我们,上述算法并不是总是凑效.

凹多边形切割

凹多边形闭合路径

从图中可以看出,闭合路径只有一个,但这个路径是凹多边形,按上述的方法求得中心很可能在多边形外面,连接出来的三角形并不正确.需要先把凹多边形切割成凸多边形,这非常容易.

只需要在多边形的凹点处,延伸出一条线段,连接到最近的边,这条线段作为交界,划分出两个多边形,再分别将这两个多边形重复此步骤,直到没有凹点,则这个多边形是凸多边形.

首先需要知道如何判断一个多边形是凹的还是凸的.
以左上角为原点的2D坐标系来说.

当一个顺时针排列的多边形,某一条边往左拐,这个多边形是凹多边形.
当一个逆时针排列的多边形,某一条边往右拐,这个多边形是凹多边形.
计算边的拐向很容易,只要判断两条边的向量积符号是正是负就行了.
//    向量拐向公式
//    具体拐向跟坐标系有关,在本例中,顺时针排列,向量积小于零是左拐.
Cross(p0p1, p1p2) < 0? "左拐?右拐?": "左拐?右拐?"

因为顶点顺序是随机的,因此可能是顺时针排列也可能是逆时针排列,所以要先计算出这个多边形的排列顺序,计算思路非常容易:
只需要遍历多边形顶点,对所有边计算拐向,如果左拐向多余右拐向,则是逆时针排列,否则是顺时针排列.

float Cutting::Polygon::CheckOrder(const math::Points & points)
{
    auto order0 = 0;    //  顺时针
    auto order1 = 0;    //  逆时针
    for (auto i = 0; i != points.size(); ++i)
    {
        auto & a = points.at(INDEX(i    , points.size()));
        auto & b = points.at(INDEX(i + 1, points.size()));
        auto & c = points.at(INDEX(i + 2, points.size()));
        if (CheckOrder(a, b, c) < 0)
        {
            ++order1;
        }
        else
        {
            ++order0;
        }
    }
    return order0 > order1 ? 1.0f : -1.0f;
}

整个算法到这就结束了,下图是凹多边形切割后的形状,很容易发现,多了几根线段,这些线段正是切分成凸多边形的线段,而闭合路径也由1个变成了3个,再用上述的方法计算三角形就容易多了.

切割凹多边形 填充选区

效果展示

png png

相关文章

  • 算法 & 数据结构——多边形填充

    在很多图形相关的编辑器里都会有选区功能,有的只能按某种固定形状选择,比如:矩形,圆形……,有的可以按任意形状选择,...

  • 实验四、多边形填充算法

    实验四、多边形填充算法 一.区域填充算法 区域填充– 对区域重新着色的过程 –将指定的颜色从种子点扩展到整个区域...

  • 多边形点填充算法

    算是一个很小的小算法,一般的话,可以考虑对当前多边形的 box(长方形)初步计算其填充点(保存在一个 List ...

  • AI好用的一些快捷键

    基础操作 快捷键说明<切换为颜色填充>切换为渐变填充/切换为无填充多边形+上下键增加/减少边数多边形+上下键+鼠标...

  • 多边形的偏移填充算法

    前言 多边形偏移 (polygon offset) 算法可能我们印象不深,不过用过 autoCAD 的同学应该有印...

  • 多边形的 symbol 填充算法

    symbol 可以认为是一个或多个 polyline,每个 polyline 可以是闭合的也可以是不闭合的,与多边...

  • Open GL常见函数

    1.多边形填充模式 glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); 全部填充...

  • 多边形的平行线填充算法

    最近做的一个小算法,使用平行线填充一个多边形区域。用过 AutoCAD 的同学应该知道,可以选定一个区域,指定平行...

  • 数据结构&算法

    常见排序算法小结如何判断一个单链表是否有环?程序员必须知道的10大基础实用算法及其讲解排序算法总结 校招常考算法J...

  • 微信小程序map

    地图多边形 https://www.jianshu.com/p/cc6c75cd0bfb多边形的填充颜色: 例如我...

网友评论

    本文标题:算法 & 数据结构——多边形填充

    本文链接:https://www.haomeiwen.com/subject/xzlrwqtx.html