algorithm - 从等正方形构造的几何图形中提取轮廓(圆周)多边形

Question

我确定一定有一种方法可以执行以下操作，但我不知道它叫什么，所以我无法用谷歌搜索它。

我需要一个从 A 到 B 的算法。有人知道它叫什么或有链接吗？

编辑:对不起，我不够清楚。图 A 由正方形组成，我基本上需要一个算法来移除正方形并将其变成多边形(图 B)。输入是轴对齐正方形的普通列表，输出应该是构成多边形的顶点列表。方 block 将始终像网格一样对齐，它们不会重叠。

为了更清楚，我想写一个这样的函数(伪代码):

struct Square {
    x, y, size: float
}
struct Polygon {
    vertices_x, vertices_y: float[]
}
function convert_to_polygon(IN squares: Square[]) -> OUT Polygon {
    //The algorithm I need goes here
}

Answer 1

如果我没看错你想获得图像的圆周轮廓。

对于矢量和栅格输入，您可以调整/使用 finding holes in 2D point set .无论如何，您想寻找某种 (convex) Hull 算法的 2D 改编 ...

如果您的输入是光栅:

1. 您可以用不同的颜色(例如蓝色)填充背景
2. 将蓝色像素旁边的所有像素重新着色(变为红色)
3. 将所有非红色像素重新着色为白色

4. 将所有红色像素重新着色为黑色

   如果您需要在项目符号 #2 处停止的矢量输出并创建红点列表。然后应用连接像素分析来检测线条在多边形中的顺序......对于正方形这应该很容易但是对于任意图像你需要line regression或霍夫变换 ...

如果您的输入是矢量:

然后删除所有内线。因此，被其他线围成 H 形状的线。您还可以检测所有小方 block ，然后删除重复的线条。

[Edit1] 你的输入/输出是向量所以

1. 形成所有行的列表

2. 删除所有出现超过一次的行

   如果您的正方形是任意大小的，那么您需要通过切割重叠部分来更精确地做到这一点......

3. 将第一条线添加到多边形(将其从线列表中删除)

4. 找到与最后添加到多边形的线具有相同终点的线
5. 将它添加到多边形(从线列表中删除它)
6. 循环 #4 直到找不到行 ...
7. 如果仍然有未使用的有效线，这意味着有不止一个多边形，那么添加新的空多边形并转到#3

在 C++ 中，我破坏了这样的东西:

// temp structures
struct _pnt  { float x,y;       _pnt(){}; _pnt(_pnt& a){ *this=a; }; ~_pnt(){}; _pnt* operator = (const _pnt *a) { *this=*a; return this; }; /*_pnt* operator = (const _pnt &a) { ...copy... return this; };*/ };
struct _lin  { int p0,p1,n;     _lin(){}; _lin(_lin& a){ *this=a; }; ~_lin(){}; _lin* operator = (const _lin *a) { *this=*a; return this; }; /*_lin* operator = (const _lin &a) { ...copy... return this; };*/ };
// your in/out structures
struct _sqr  { float x,y,s;     _sqr(){}; _sqr(_sqr& a){ *this=a; }; ~_sqr(){}; _sqr* operator = (const _sqr *a) { *this=*a; return this; }; /*_sqr* operator = (const _sqr &a) { ...copy... return this; };*/ };
struct _pol { List<float> x,y;  _pol(){}; _pol(_pol& a){ *this=a; }; ~_pol(){}; _pol* operator = (const _pol *a) { *this=*a; return this; }; /*_pol* operator = (const _pol &a) { ...copy... return this; };*/ };
List<_sqr> sqr; // squares
     _pol  pol; // polygon

void sqr2pol_init()
    {
    _sqr s;
    int i,j,p0,p1,p2,p3;
    float x,y,x0,x1,y0,y1,a=32,d,_zero=1e-3;
    // [init square list to your scenario]
    sqr.num=0; pol.x.num=0; pol.y.num=0;
    s.s=a; s.x=a; s.y=a;
    sqr.add(s); s.x+=a;
    sqr.add(s); s.x+=a;
    sqr.add(s); s.x+=a;
    sqr.add(s); s.x =a; s.y+=a;
    sqr.add(s); s.x =a; s.y+=a;
    sqr.add(s); s.x+=a;
    // [compute point and line lists]
    List<_pnt> pnt; _pnt p;
    List<_lin> lin; _lin l;
    for (pnt.num=0,lin.num=0,i=0;i<sqr.num;i++)
        {
        x=sqr[i].x;
        y=sqr[i].y;
        a=sqr[i].s*0.5;
        x0=x-a; x1=x+a;
        y0=y-a; y1=y+a;
        // add non duplicate points only
        p.x=x0; p.y=y0; for (j=0;j<pnt.num;j++) { x=pnt[j].x-p.x; y=pnt[j].y-p.y; if ((x*x)+(y*y)<=_zero) break; } if (j>=pnt.num) pnt.add(p); p0=j;
        p.x=x0; p.y=y1; for (j=0;j<pnt.num;j++) { x=pnt[j].x-p.x; y=pnt[j].y-p.y; if ((x*x)+(y*y)<=_zero) break; } if (j>=pnt.num) pnt.add(p); p1=j;
        p.x=x1; p.y=y1; for (j=0;j<pnt.num;j++) { x=pnt[j].x-p.x; y=pnt[j].y-p.y; if ((x*x)+(y*y)<=_zero) break; } if (j>=pnt.num) pnt.add(p); p2=j;
        p.x=x1; p.y=y0; for (j=0;j<pnt.num;j++) { x=pnt[j].x-p.x; y=pnt[j].y-p.y; if ((x*x)+(y*y)<=_zero) break; } if (j>=pnt.num) pnt.add(p); p3=j;
        // add non duplicate lines (and update counter n for duplicates)
        l.p0=p0; l.p1=p1; l.n=0; for (j=0;j<lin.num;j++) if (((lin[j].p0==l.p0)&&(lin[j].p1==l.p1))||((lin[j].p0==l.p1)&&(lin[j].p1==l.p0))) { lin[j].n++; break; } if (j>=lin.num) lin.add(l);
        l.p0=p1; l.p1=p2; l.n=0; for (j=0;j<lin.num;j++) if (((lin[j].p0==l.p0)&&(lin[j].p1==l.p1))||((lin[j].p0==l.p1)&&(lin[j].p1==l.p0))) { lin[j].n++; break; } if (j>=lin.num) lin.add(l);
        l.p0=p2; l.p1=p3; l.n=0; for (j=0;j<lin.num;j++) if (((lin[j].p0==l.p0)&&(lin[j].p1==l.p1))||((lin[j].p0==l.p1)&&(lin[j].p1==l.p0))) { lin[j].n++; break; } if (j>=lin.num) lin.add(l);
        l.p0=p3; l.p1=p0; l.n=0; for (j=0;j<lin.num;j++) if (((lin[j].p0==l.p0)&&(lin[j].p1==l.p1))||((lin[j].p0==l.p1)&&(lin[j].p1==l.p0))) { lin[j].n++; break; } if (j>=lin.num) lin.add(l);
        }
    // [copy singular lines only to polygon + connected lines analysis/reorder]
    // add first usable (n==0) line to polygon
    p0=-1;
    for (i=0;i<lin.num;i++)
     if (lin[i].n==0)
        {
        pol.x.add(pnt[lin[i].p0].x);
        pol.y.add(pnt[lin[i].p0].y);
        pol.x.add(pnt[lin[i].p1].x);
        pol.y.add(pnt[lin[i].p1].y);
        p0=lin[i].p0;   // p0 = start of polygon
        p1=lin[i].p1;   // p1 = current end of polygon
        lin[i].n++;     // mark as unusable
        break;
        }
    // add next line to p1 until you can
    for (j=1;j;)
        {
        for (i=0,j=0;i<lin.num;i++)
         if (lin[i].n==0)
            {
            p2=-1;
            if (lin[i].p0==p1) p2=lin[i].p1;
            if (lin[i].p1==p1) p2=lin[i].p0;
            if (p2<0) continue;
            pol.x.add(pnt[p2].x);
            pol.y.add(pnt[p2].y);
            lin[i].n++;     // mark as unusable
            p1=p2;          // update last point
            j=1;            // continue search
            break;
            }
        }
    }

• List<T> l;只是动态线性阵列模板(类似于 std::vector )
• 代表T[l.num] l;
• l.num是数组的当前大小
• l.add(x);添加新项目 x到数组的末尾...

这是结果:

• Aqua 线条是原始方 block sqr
• 黄色 线是多边形 pol输出