从等正方形构造的几何图形中提取轮廓（圆周）多边形

Question

我确定一定有一种方法可以执行以下操作，但我不知道它叫什么，所以我不能 google 它。

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

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

为了更清楚，我想写一个这样的函数（伪代码）：

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

如果我没猜错你想获取图像的圆周轮廓

对于矢量和光栅输入，您可以 adapt/use finding holes in 2D point set。无论如何，您想寻找 (convex) Hull 算法的某种二维改编 ...

如果您的输入是光栅：

您可以用不同的颜色（例如蓝色）填充背景
将蓝色像素旁边的所有像素重新着色（变为红色）
将所有非红色像素重新着色为白色
将所有红色像素重新着色为黑色

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

如果您的输入是向量：

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

[Edit1] 你的 input/output 是向量所以

形成所有行的列表
删除出现超过一次的所有行

如果你的正方形是任意大小的，那么你需要通过切割重叠部分来更精确地做到这一点...
将第一条线添加到多边形（将其从线列表中删除）
查找与最后添加到多边形的线具有相同终点的线
将其添加到多边形（从线列表中删除）
循环 #4 直到找不到行 ...
如果仍有未使用的有效线，这意味着存在不止一个多边形，因此请添加新的空多边形并转到#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输出

从等正方形构造的几何图形中提取轮廓（圆周）多边形

Outline (circumference) polygon extraction from geometry constructed from equal squares

algorithm

math

geometry

2d

vector