從等方塊構建的幾何體提取輪廓（圓周）多邊形

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輸出