从由相等正方形构造的几何图形中提取轮廓(周长)多边形 [英] Outline (circumference) polygon extraction from geometry constructed from equal squares

问题描述

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

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.

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

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

对不起，我不够清楚.图 A 由正方形组成，我基本上需要一个算法来删除正方形并将其变成多边形(图 B).输入是轴对齐正方形的普通列表，输出应该是构成多边形的顶点列表.正方形将始终像在网格上一样对齐，它们不会重叠.

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
}

推荐答案

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

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

对于矢量和光栅输入，您可以调整/使用在二维点集中寻找孔.无论如何，您想寻找某种 (convex) Hull 算法的 2D 适应 ...

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 ...

如果您的输入是光栅:

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

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

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

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

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 ...

如果您的输入是矢量:

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

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] 你的输入/输出是矢量所以

1. 形成所有行的列表

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

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 ...

将第一行添加到多边形(从行列表中删除)

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

在 C++ 中我破坏了这样的东西:

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;
            }
        }
    }

• 列表<T>l; 只是动态线性数组模板(类似于std::vector)
• 表示T[l.num] l;
• l.num 是数组的当前大小
• l.add(x); 将新项目 x 添加到数组末尾 ...
• 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 ...

这是结果:

• Aqua 线是原始正方形 sqr
• 黄色线是多边形pol输出
• Aqua lines are the original squares sqr
• Yellow lines are the Polygon pol output

这篇关于从由相等正方形构造的几何图形中提取轮廓(周长)多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！