从等方块构建的几何体提取轮廓（圆周）多边形

Question

我确定必须存在一种方法来执行以下操作，但我不知道它是什么，所以我不能谷歌它。

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

编辑：对不起，我不太清楚。图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

如果我得到它的权利要得到图像的圆周轮廓。

对于矢量和光栅输入，您可以修改/使用finding holes in 2D point set。反正你想寻找某种（凸）赫尔算法的2D适应...

如果你的输入栅格：

1. 你可以洪水填充背景，不同的颜色（例如蓝色）
2. 重新着色旁边，是蓝色像素（一个或多个）
3. 重新着色所有非红色像素为白色

4. 重新着色所有红色PIX的所有像素（红色） els to black

   如果您需要在子弹＃2处停止的矢量输出并创建红点列表。然后应用连接像素分析，以检测线多边形他们的订单......对于正方形这应该是容易的，但对于任意图像，您将需要line regression或Hough变换 ...

如果输入的是矢量：

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

[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添加到数组末尾...

这是结果：

• 水族线是原来的正方形sqr
• 黄线多边形pol输出