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

Question

I'm sure there must exist a way to do the following but I don't know what it's called so I cannot google it.

I need an algorithm to go from A to B. Does someone know what it's called or has a link to it?

EDIT: Sorry I wasn't clear enough. Figure A is made up of squares and I basicly need an algoritm which removes the squares and turns it into a polygon(Figure B). The input is a plain list of axis aligned squares, the output should be a list of vertices which make up a polygon. The squares will always be aligned like on a grid, they will not overlap.

To make it more clear, I want to write a function like this (pseudo code):

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

If I get it right you want to obtain the circumference outline of the image.

For both vector and raster input you can adapt/use finding holes in 2D point set. Anyway you want to look for some kind of 2D adaptation of (convex) Hull algorithm ...

if your input is raster:

1. you can flood-fill background with different color (for example blue)
2. recolor all pixels (to red) that are next to blue pixel(s)
3. recolor all non red pixels to white

4. recolor all red pixels to black

   if you need vector output that stop at bullet #2 and create list of red points. then apply connected pixels analysis to detect lines their order in polygon ... For squares this should be easy but for arbitrary image you will need line regression or Hough Transform ...

if your input is vector:

Then just remove all inner lines. So lines that are enclosed by other lines in H shape. You can also detect all small squares and then remove duplicate lines.

[Edit1] your input/output is vector so

1. form a list of all lines

2. remove all lines that are present more then once

   If your squares are in arbitrary size then you need to do this much more precise by cutting overlapping segments ...

3. add first line to the polygon (removing it from line list)

4. find line that has the same end point as last added line to polygon
5. add it to polygon (removing it from line list)
6. loop #4 until no line found ...
7. if there are still unused valid lines that means there is more than one polygon so add new empty polygon and goto #3

In C++ I busted something like this:

// 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; is just dynamic linear array template (similar to std::vector)
• it represents T[l.num] l;
• l.num is the current size of array
• l.add(x); adds new item x to the end of array ...

This is the result:

• Aqua lines are the original squares sqr
• Yellow lines are the Polygon pol output