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 。无论如何，你想寻找某种(凸)赫尔算法的二维适应......

如果您的输入是栅格:

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

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

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

如果您的输入是矢量:

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

[编辑1]你的输入/输出是矢量，所以

1. 形成所有行的列表

2. 删除所有出现多次的行

   如果你的方 block 是任意大小的，那么你需要通过切割重叠的线段来更精确地做到这一点......

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线是原来的正方形sqr
• 黄线是多边形 pol输出