确定解决迷宫的线段的最小数量 [英] Determine Minimum Number of Line Segments to Solve a Maze
本文介绍了确定解决迷宫的线段的最小数量的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个问题，那就是我需要定义一个顶点数最少的多边形，它与图像中不透明的每个像素相交或包含每个像素（设N是图像中的像素数）。我唯一的假设是图像不能在其边界（孔）内包含透明像素，并且至少有两个像素不透明。作为一个例子，可以说我有以下图片：
我对算法的想法是这样的：
$ b
1）确定边界像素。这是通过遍历每个像素，并确定是否有任何邻居（在四个像素之外，上方，右方和下方）是空的，在O（N）时间完成。存储像素和哪些邻居是不透明的，通过线性索引键入到像素数组中。假设有P个边缘像素，如下面的橙色所示。
2）获取边缘像素的邻接列表
在O（P）通过选择其中一个边缘像素，并选择基于空白邻居的方向。例如，如果像素具有底部和右边的邻居，则下一个像素将是右上角的一个像素或右侧的像素。从剩余边缘像素的字典中选择下一个边缘像素。将该像素追加到列表中，直到算法返回到开始像素。在下面的示例图像中有27个边缘像素（一些边缘像素不止一次）。
3）绘制一个所有边缘必须位于其间的迷宫。这是在O（P）时间通过遍历邻接列表完成的，并且在没有邻居的情况下向这些像素上的所有边添加边。另外，根据下一个边缘像素的方向将边缘添加到形状的内部。如果像素代表具有单个像素宽度的半岛，则将内边缘添加到边缘的中间而不是像素顶点。迷宫的内部显示为红色。请注意，迷宫边界是步骤2中找到的所有边缘像素的超集。
4）找到边几乎最小的多边形，不要触摸迷宫的边界。
这是我需要帮助的部分。有没有人有关于如何从步骤＃3到如下解决方案的建议？
解决方案
- 请参阅在2D点集中找到洞
- 类似的问题
- 只是反转地图，并使用每个网格平方的中点作为点
- ，这将导致：
- 有两种选择：在使用这个元素之前，可以通过1个单元缩小形状（可以放松一些细节）
- 改变H / V线，使它们是1个单元格缩短（从两边一半）
- ，这将导致类似这样的事情： .stack.imgur.com / 2h8Yv.pngalt =HV线缩水>
- 尾部呃一些代码中的变化我现在可以使用2次多重采样，所以结果是：
- 现在您可以以相同斜率连接相连的线，并在找到的角上应用诸如耳廓修剪之类的内容获得更接近你想要的多边形
- 它与上面的代码链接在上面
- 只是
map [] []条件反转以搜索多边形而不是孔 - ，并发现HV线从每边的一半收缩 。
-
_lin坐标是float现在需要4倍多重采样。
- 最好的结果是2x多重采样（避免多边形宽度= 1）
- ，因此地图中的每个单元格都会在单元格区域中添加2x2点。
- 我还添加了2个角点以更好地对齐
map [] []和您的图片 - See find holes in 2D point set
- it is very similar problem
- just invert the map and use midpoint of each grid square as point
- that will lead to this:
- as you want the inner polygon then there are 2 choices
- shrink shape by 1 cell before applying this (can loose some detail in shape)
- change the H/V lines so they are 1 cell shorter (half from both sides)
- that will lead to something like this:
- after some changes in code I can use 2x multi-sampling now so result is:
- now you can join connected lines with the same slope
- and apply something like ear clipping on the found corners to get more close to your desired polygon
- it is the same as the code in holes link above
- just the
map[][]conditions inverted to search polygons instead of holes - and found HV lines are shrinked by half of cell from each side
_lincoordinates arefloatnow so o need for 4x multisampling- the best results are with 2x multi-sampling (to avoid polygon width=1)
- so each cell in your map add as 2x2 points in the cell area
- I added also 2 corner points to better align
map[][]and your image
可能会留下一些留言）：
// --------------- -------------------------------------------------- ----------
// ---------------------------------- -----------------------------------------
// --- -------------------------------------------------- ----------------------
/ *用法：
int i;
pntcloud_polygons h;
pnt2D point [points];
h.scann_beg（）; for（i = 0; i
h.holes_beg（）; for（i = 0; i
* /
// ---------------------------------- -----------------------------------------
class pntcloud_polygons
{
public：
int xs，ys，n; //单元格网格x，y - 大小和点数
int **映射; //点密度图[xs] [ys]
// i =（x-x0）* g2l; X = X0 +（I * L2G）;
// j =（y-y0）* g2l; Y = Y0 +（j * L2G）;
double mg2l，ml2g; //向全局/地图空间（x，y）缩放/从/缩放全局/地图空间（x，y） map [i] [j]
double x0，x1，y0，y1; //使用区域（边界框）
struct _line
{
int id; //用于分割/多边形的孔的ID
float i0，i1，j0，j1; // map in map [] []
_line（）{}; _line（_line& a）{* this = a; }; 〜_line（）{}; _line * operator =（const _line * a）{* this = * a;返回这个; }; / * _ line * operator =（const _line& a）{... copy ... return this; }; * /
};
列表< _line>林;
int lin_i0; //开始外围线索引（较小的索引是洞内的H，V线）
struct _point
{
int i，j; // map in map [] []
int p0，p1; //上一个下一个点
int已使用;
_point（）{}; _point（_point& a）{* this = a; }; 〜_point（）{}; _point * operator =（const _point * a）{* this = * a;返回这个; }; / * _ point * operator =（const _point& a）{... copy ... return this; }; * /
};
列表< _point> PNT;
// class init和internal stuff
pntcloud_polygons（）{xs = 0; YS = 0; N = 0;地图= NULL; mg2l = 1.0; ml2g = 1.0; X0 = 0.0; Y0 = 0.0; X1 = 0.0; Y1 = 0.0; lin_i0 = 0; };
pntcloud_polygons（pntcloud_polygons& a）{* this = a; };
〜pntcloud_polygons（）{_free（）; };
pntcloud_polygons * operator =（const pntcloud_polygons * a）{* this = * a;返回这个; };
pntcloud_polygons * operator =（const pntcloud_polygons& a）
{
xs = 0; YS = 0; N = A.N;地图= NULL;
mg2l = a.mg2l; X0 = a.x0; X1 = a.x1;
ml2g = a.ml2g; Y0 = a.y0; Y1 = a.y1;
_alloc（a.xs，a.ys）;对于（int j = 0; j
]。
返回此;
}
void _free（）{if（map）{for（int i = 0; i< xs; i ++）if（map [i]）delete [] map [i];删除[]地图; } xs = 0; YS = 0; }
void _alloc（int _xs，int _ys）{int i = 0; _自由（）; XS = _xs; YS = _ys; map = new int * [xs]; if（map）for（i = 0; i< xs; i ++）{map [i] = new int [ys]; if（map [i] == NULL）{i = -1;打破; }} else i = -1; if（i <0）_free（）; }
//扫描边界框界面
void scann_beg（）;
void scann_pnt（double x，double y）;
void scann_end（）;
//动态分配
void cell_size（double sz）; //根据网格单元大小计算/分配网格大小= sz x sz
// scann pntcloud_polygons接口
void holes_beg（）;
void holes_pnt（double x，double y）;
void holes_end（）;
// global（x，y）< - 局部映射[i] [j] +半单元偏移
内嵌void l2g（double& x，double& y，int i，int j）{x = x0 +（（double（i）+0.5）* ml2g）; Y = Y0 +（（双（J）0.5）* ml2g）; }
inline void l2g（double& x，double& y，float i，float j）{x = x0 +（（double（i）+0.5）* ml2g）; Y = Y0 +（（双（J）0.5）* ml2g）; }
// local map [i] [j]< - global（x，y）
inline void g2l（int& i，int& j，double x，double y）{i =双（（x-x0）* mg21）; j = double（（y-y0）* mg21）; }
};
// -------------------------------------------- -------------------------------
void pntcloud_polygons :: scann_beg（）
{
x0 = 0.0; Y0 = 0.0; X1 = 0.0; Y1 = 0.0; N = 0;
}
// --------------------------------------- ------------------------------------
void pntcloud_polygons :: scann_pnt（double x，double y）
{
if（！n）{x0 = x; Y0 = Y; X1 = X; Y1 = Y; }
if（n <0x7FFFFFFF）n ++; //避免溢出
if（x0> x）x0 = x;如果（x1
// --------------------------------------- ------------------------------------
void pntcloud_polygons :: scann_end（）
{
}
// ------------------------------------- --------------------------------------
void pntcloud_polygons :: cell_size（double sz ）
{
int x，y;如果（sz <1e-6）sz = 1e-6，则
;
x = ceil（（x1-x0）/ sz）;
y = ceil（（y1-y0）/ sz）;
_alloc（x，y）;
ml2g = sz; mg2l = 1.0 / SZ;
}
// --------------------------------------- ------------------------------------
void pntcloud_polygons :: holes_beg（）
{
int i，j; （j = 0; j
}
// --------------------------------------- ------------------------------------
void pntcloud_polygons :: holes_pnt（double x，double y）
{
int i，j;
g2l（i，j，x，y）; （（j> 0）&<（j< ys））
if（（i> = 0）& map [i] [j] <0x7FFFFFFF）map [i] [j] ++; //避免溢出
}
// ----------------------------------- ----------------------------------------
void pntcloud_polygons :: holes_end（ ）
{
int i，j，e，i0，i1;
列表< int>九; //洞线开始/停止索引以加速多边形化
_line * a，* b，l;
_point * aa，* bb，p;
lin.num = 0; lin_i0 = 0; //清除行
ix.num = 0; //清除索引
//找到pntcloud_polygons（map [i] [j] .cnt！= 0）或（map [i] [j] .cnt> = treshold）
/ /并创建包含pntcloud_polygons
的H，V行的lin []列表，其中（j = 0; j
int i0，i1;如果（map [i] [j]！= 0）break;（$; $ x $; $ i $） I 0 = I-1; //找到多边形的起点
for（; i< xs; i ++）if（map [i] [j] == 0）break; I1 = I; //如果（i0 <0）继续，则找到多边形的结尾
; //跳过坏的情况（找到边或没有找到空洞）
if（i1> = xs）continue;
if（map [i0] [j]！= 0）继续;
if（map [i1] [j]！= 0）继续;
l.i0 = i0 + 0.5;
l.i1 = i1-0.5;
l.j0 = j;
l.j1 = j;
l.id = -1;
lin.add（l）;
for（i = 0; i
int J0，J1;如果（map [i] [j]！= 0）break（）;（b;
for（; j
if（j1> = ys）continue;
if（map [i] [j0]！= 0）继续;
if（map [i] [j1]！= 0）继续;
l.i0 = i;
l.i1 = i;
l.j0 = j0 + 0.5;
l.j1 = j1-0.5;
l.id = -1;
lin.add（l）;
}
// segmentate lin [] ...通过lin []将同一个洞的线条组合在一起。id
//基于矢量线数据的分段
//你也可以在孔检测过程中直接将位图[] []作为位图来分割
for（i = 0; i< lin.num; i ++）lin [i] .id = i; //所有行都是独立的
for（;;）//加入你可以
{
for（e = 0，a = lin.dat，i = 0; i< lin。 （b = a，j = i; j
{
//如果a，b不相交或相邻
if（a-> i0> b-> i1）继续;如果（b-> i0> a-> i1）继续，则
;如果（a-> j0> b-> j1）继续，则
;如果（b-> j0> a-> j1）继续，则
;
//如果他们标记为加入组
e = 1;打破; （e）break;
}
// join found ...停止搜索
}
if（！e）break; //找不到连接...停止分段
i0 = a-> id; // joid id ...将i1重命名为i0
i1 = b-> id; （a = lin.dat，i = 0; i< lin.num; i ++，a ++）
if（a-> id == i1）
a-> id = I0; （e = 0，a =& lin [0]，b =& lin）对$ {
}
// sort lin [] by id
如果（a-> id> b-> id）{1 = * a; i = 1; * A = * B; * B = 1; E = 1; }
// re id lin []并为（i0 = -1，i1 = -1，a =& lin [0]，i = 0; i
if（a-> id == i1）a-> id = i0;
else {i0 ++; I1 = A->编号; A-> ID = I0; ix.add（ⅰ）; }
ix.add（lin.num）;
// polygonize
lin_i0 = lin.num;
for（j = 1; j
i0 = ix [j-1]; I1 = IX [J];
//创建边界pnt []列表（仅限唯一点）
pnt.num = 0; p.used = 0; p.p0 = -1; p.p1 = -1; （a =& lin [i0]，i = i0; i< i1; i ++，a ++）
{
p.i = a-> i0;
p.j = a-> j0;
map [p.i] [p.j] = 0; （aa =& pnt [0]，e = 0; e< pnt.num; e ++，aa ++）
（（aa-> i == pi）& aa> j == pj））{e = -1;打破; （e> = 0）pnt.add（p）;}
if（e> = 0）
p.i = a-> i1;
p.j = a-> j1;
map [p.i] [p.j] = 0; （aa =& pnt [0]，e = 0; e< pnt.num; e ++，aa ++）
（（aa-> i == pi）& aa> j == pj））{e = -1;打破; （e> = 0）pnt.add（p）;}
if（e> = 0） （aa =& pnt [0]，i = 0; i< pnt.num; i ++，aa ++）
if（ （aa-> i> 0）&&（aa-> i< xs-1））//忽略标记点
如果（aa> j> 0）&（aa-> j< ys-1））
{//如果在$ b周围存在任何非空洞单元，则忽略边界点
（map [aa-> i-1] [aa-> j-1]> 0）继续;
if（map [aa-> i-1] [aa-> j]> 0）继续; （map [aa-> i-1] [aa-> j + 1]> 0）继续;
if（map [aa-> i] [aa-> j-1]> 0）继续; （map [aa-> i] [aa-> j + 1]> 0）继续; （map [aa-> i + 1] [aa-> j-1]> 0）继续;如果（map [aa-> i + 1] [aa-> j]> 0）则
继续; （map [aa-> i + 1] [aa-> j + 1]> 0）继续;
aa-> used = 1;
}
//删除标记点
（aa =& pnt [0]，e = 0，i = 0; i
//连接相邻点距离= 1
（i0 = 0，aa =& pnt [i0]; i0
{
i = aa-> i-bb-> i; if（i <0）i = -i; e = i;
i = aa-> j-bb-> j; if（i <0）i = -i; E + = I;
if（e！= 1）continue;
aa-> used ++;如果（aa-> p 0< 0）aa-> p 0 = i 1; else aa-> p1 = i1;
bb-> used ++;如果（bb-> p0 <0）bb-> p0 = i0;否则bb-> p1 = i0;
}
//尝试连接相邻点距离= sqrt（2）
（i0 = 0，aa =& pnt [i0]; i0
for（i1 = i0 + 1，bb =& pnt [i1]; i1
如果（bb->使用< 2） （（aa->已使用）&&（aa-> p 0）>（bb-> p1！= i0））
{
== bb-> p0））continue; //避免小的循环
i = aa-> i-bb-> i; if（i <0）i = -i; e = i * i;
i = aa-> j-bb-> j; if（i <0）i = -i; E + = I * I;
if（e！= 2）继续;
aa-> used ++;如果（aa-> p 0< 0）aa-> p 0 = i 1; else aa-> p1 = i1;
bb-> used ++;如果（bb-> p0 <0）bb-> p0 = i0;否则bb-> p1 = i0;
}
//尝试连接到最近点
int ii，dd; （aa>< pnt [i0]; i0< pnt.num; i0 ++，aa ++）
（aa->使用< 2）
{$ b （bb->已使用< 2）$ b（bb-> $ b $）对于（ii = -1，i1 = i0 + 1，bb =& pnt [i1]; i1 p0！= i1）&（aa-> p1！= i1））
if（（bb-> p0！= i0）& bb-> p1！= i0））
{
i = aa-> i-bb-> i; if（i <0）i = -i; e = i * i;
i = aa-> j-bb-> j; if（i <0）i = -i; E + = I * I; （（ii <0）||（e
if（ii <0）continue;
i1 = ii; BB =&安培; PNT [I1]。
aa-> used ++;如果（aa-> p 0< 0）aa-> p 0 = i 1; else aa-> p1 = i1;
bb-> used ++;如果（bb-> p0 <0）bb-> p0 = i0;否则bb-> p1 = i0;
}
//将连接点添加到lin [] ...这是洞外围！
//行是2 x复制的，因此一些额外的代码用于排序行sw的顺序是好主意
l.id = lin [ix [j-1]]。id;
//添加点的索引，而不是点
int lin_i1 = lin.num; （i0 = 0，aa =& pnt [i0]; i0
l.i0 = i0; （aa-> p 0> i 0）{l.i 1 = aa-> p 0; lin.add（升）;如果（aa-> p1> i0）{l.i1 = aa-> p1; lin.add（升）; （i0 = lin_i1，a =& lin [i0]; i0
对于（i1 = i0 + 1，b =& lin [i1]; i1
if（a-> i1 == b-> i0 ）{a ++;升= * A; * A = * B; * B = 1;一个 - ;打破; }
if（a-> i1 == b-> i1）{a ++;升= * A; * A = * B; * B = 1; I = A-> I0; A-> I 0 = A-> I1; A-> I1 = I;一个 - ;打破; }
//将点索引转换为点
（i0 = lin_i1，a =& lin [i0]; i0
bb =& pnt [a-> i0]; A-> I 0 = BB- I标记; A-> J0 = BB->焦耳;
bb =& pnt [a-> i1]; A-> I1 = BB- I标记; A-> J1 = BB->焦耳;
}
}
}
// ----------------------------- ----------------------------------------------
// ------------------------------------------------ ---------------------------
// ----------------- -------------------------------------------------- --------
I have a problem where I need to define a polygon with the minimum number of vertices that intersects or contains every pixel in an image that is not transparent (Let N be the number of pixels in the image). My only assumptions are that the image cannot contain transparent pixels within its boundary (holes), and that at least two pixels are non-transparent. As an example, lets say I have the following image:
My idea for an algorithm is thus:
1) Determine the edge pixels.
This is done in O(N) time by iterating through each pixel, and determining whether any neighbors (out of the four pixels left, above, right, and below it) are empty. Store the pixel and which neighbors were non-transparent, keyed by linear index into the array of pixels. Let there be P edge pixels, shown in orange below.
2) Get an adjacency list of the edge pixels.
This is done in O(P) time by selecting one of the edge pixels, and chosing a direction based on empty neighbors. For example, if a pixel has a bottom and right neighbor, then the next pixel will be either one in the upper-right corner, or the pixel immediately to the right. Select the next edge pixel from the dictionary of remaining edge pixels. Append that pixel to the list until the algorithm returns to the starting pixel. There are 27 edge pixels in the example image below (some are an edge pixel more than once).
3) Draw a maze that all edges must lie between.
This is done in O(P) time by iterating through the adjacency list, and adding an edge to all edges on those pixels without a neighbor. In addition, an edge is added to the interior of the shape based on the direction to the next edge pixel. If the pixel represents a peninsula with single pixel width, the inner edge is added to the middle of the edge instead of the pixel vertex. The interior of the maze is shown in red. Note that the maze boundary is a super-set of all the edge pixels found in step 2.
4) Find a polygon with almost minimal edges that does not touch the border of the maze.
This is the part I need help with. Does anyone have a suggestion of how you would go from step #3 to a solution such as the following?
解决方案
Here the inverted source code in C++ (there may be some hole comments left):
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
/* usage:
int i;
pntcloud_polygons h;
pnt2D point[points];
h.scann_beg(); for (i=0;i<points;i++) { p=point[i]; h.scann_pnt(p.x,p.y); } h.scann_end();
h.cell_size(2.5); // or (h.x1-h.x0)*0.01 ... cell size >> avg point distance
h.holes_beg(); for (i=0;i<points;i++) { p=point[i]; h.holes_pnt(p.x,p.y); } h.holes_end();
*/
//---------------------------------------------------------------------------
class pntcloud_polygons
{
public:
int xs,ys,n; // cell grid x,y - size and points count
int **map; // points density map[xs][ys]
// i=(x-x0)*g2l; x=x0+(i*l2g);
// j=(y-y0)*g2l; y=y0+(j*l2g);
double mg2l,ml2g; // scale to/from global/map space (x,y) <-> map[i][j]
double x0,x1,y0,y1; // used area (bounding box)
struct _line
{
int id; // id of hole for segmentation/polygonize
float i0,i1,j0,j1; // index in map[][]
_line(){}; _line(_line& a){ *this=a; }; ~_line(){}; _line* operator = (const _line *a) { *this=*a; return this; }; /*_line* operator = (const _line &a) { ...copy... return this; };*/
};
List<_line> lin;
int lin_i0; // start index for perimeter lines (smaller indexes are the H,V lines inside hole)
struct _point
{
int i,j; // index in map[][]
int p0,p1; // previous next point
int used;
_point(){}; _point(_point& a){ *this=a; }; ~_point(){}; _point* operator = (const _point *a) { *this=*a; return this; }; /*_point* operator = (const _point &a) { ...copy... return this; };*/
};
List<_point> pnt;
// class init and internal stuff
pntcloud_polygons() { xs=0; ys=0; n=0; map=NULL; mg2l=1.0; ml2g=1.0; x0=0.0; y0=0.0; x1=0.0; y1=0.0; lin_i0=0; };
pntcloud_polygons(pntcloud_polygons& a){ *this=a; };
~pntcloud_polygons() { _free(); };
pntcloud_polygons* operator = (const pntcloud_polygons *a) { *this=*a; return this; };
pntcloud_polygons* operator = (const pntcloud_polygons &a)
{
xs=0; ys=0; n=a.n; map=NULL;
mg2l=a.mg2l; x0=a.x0; x1=a.x1;
ml2g=a.ml2g; y0=a.y0; y1=a.y1;
_alloc(a.xs,a.ys);
for (int i=0;i<xs;i++)
for (int j=0;j<ys;j++) map[i][j]=a.map[i][j];
return this;
}
void _free() { if (map) { for (int i=0;i<xs;i++) if (map[i]) delete[] map[i]; delete[] map; } xs=0; ys=0; }
void _alloc(int _xs,int _ys) { int i=0; _free(); xs=_xs; ys=_ys; map=new int*[xs]; if (map) for (i=0;i<xs;i++) { map[i]=new int[ys]; if (map[i]==NULL) { i=-1; break; } } else i=-1; if (i<0) _free(); }
// scann boundary box interface
void scann_beg();
void scann_pnt(double x,double y);
void scann_end();
// dynamic allocations
void cell_size(double sz); // compute/allocate grid from grid cell size = sz x sz
// scann pntcloud_polygons interface
void holes_beg();
void holes_pnt(double x,double y);
void holes_end();
// global(x,y) <- local map[i][j] + half cell offset
inline void l2g(double &x,double &y,int i,int j) { x=x0+((double(i)+0.5)*ml2g); y=y0+((double(j)+0.5)*ml2g); }
inline void l2g(double &x,double &y,float i,float j) { x=x0+((double(i)+0.5)*ml2g); y=y0+((double(j)+0.5)*ml2g); }
// local map[i][j] <- global(x,y)
inline void g2l(int &i,int &j,double x,double y) { i= double((x-x0) *mg2l); j= double((y-y0) *mg2l); }
};
//---------------------------------------------------------------------------
void pntcloud_polygons::scann_beg()
{
x0=0.0; y0=0.0; x1=0.0; y1=0.0; n=0;
}
//---------------------------------------------------------------------------
void pntcloud_polygons::scann_pnt(double x,double y)
{
if (!n) { x0=x; y0=y; x1=x; y1=y; }
if (n<0x7FFFFFFF) n++; // avoid overflow
if (x0>x) x0=x; if (x1<x) x1=x;
if (y0>y) y0=y; if (y1<y) y1=y;
}
//---------------------------------------------------------------------------
void pntcloud_polygons::scann_end()
{
}
//---------------------------------------------------------------------------
void pntcloud_polygons::cell_size(double sz)
{
int x,y;
if (sz<1e-6) sz=1e-6;
x=ceil((x1-x0)/sz);
y=ceil((y1-y0)/sz);
_alloc(x,y);
ml2g=sz; mg2l=1.0/sz;
}
//---------------------------------------------------------------------------
void pntcloud_polygons::holes_beg()
{
int i,j;
for (i=0;i<xs;i++)
for (j=0;j<ys;j++)
map[i][j]=0;
}
//---------------------------------------------------------------------------
void pntcloud_polygons::holes_pnt(double x,double y)
{
int i,j;
g2l(i,j,x,y);
if ((i>=0)&&(i<xs))
if ((j>=0)&&(j<ys))
if (map[i][j]<0x7FFFFFFF) map[i][j]++; // avoid overflow
}
//---------------------------------------------------------------------------
void pntcloud_polygons::holes_end()
{
int i,j,e,i0,i1;
List<int> ix; // hole lines start/stop indexes for speed up the polygonization
_line *a,*b,l;
_point *aa,*bb,p;
lin.num=0; lin_i0=0;// clear lines
ix.num=0; // clear indexes
// find pntcloud_polygons (map[i][j].cnt!=0) or (map[i][j].cnt>=treshold)
// and create lin[] list of H,V lines covering pntcloud_polygons
for (j=0;j<ys;j++) // search lines
for (i=0;i<xs;)
{
int i0,i1;
for (;i<xs;i++) if (map[i][j]!=0) break; i0=i-1; // find start of polygon
for (;i<xs;i++) if (map[i][j]==0) break; i1=i; // find end of polygon
if (i0< 0) continue; // skip bad circumstances (edges or no hole found)
if (i1>=xs) continue;
if (map[i0][j]!=0) continue;
if (map[i1][j]!=0) continue;
l.i0=i0+0.5;
l.i1=i1-0.5;
l.j0=j ;
l.j1=j ;
l.id=-1;
lin.add(l);
}
for (i=0;i<xs;i++) // search columns
for (j=0;j<ys;)
{
int j0,j1;
for (;j<ys;j++) if (map[i][j]!=0) break; j0=j-1; // find start of polygon
for (;j<ys;j++) if (map[i][j]==0) break; j1=j ; // find end of polygon
if (j0< 0) continue; // skip bad circumstances (edges or no hole found)
if (j1>=ys) continue;
if (map[i][j0]!=0) continue;
if (map[i][j1]!=0) continue;
l.i0=i ;
l.i1=i ;
l.j0=j0+0.5;
l.j1=j1-0.5;
l.id=-1;
lin.add(l);
}
// segmentate lin[] ... group lines of the same hole together by lin[].id
// segmentation based on vector lines data
// you can also segmentate the map[][] directly as bitmap during hole detection
for (i=0;i<lin.num;i++) lin[i].id=i; // all lines are separate
for (;;) // join what you can
{
for (e=0,a=lin.dat,i=0;i<lin.num;i++,a++)
{
for (b=a,j=i;j<lin.num;j++,b++)
if (a->id!=b->id)
{
// if a,b not intersecting or neighbouring
if (a->i0>b->i1) continue;
if (b->i0>a->i1) continue;
if (a->j0>b->j1) continue;
if (b->j0>a->j1) continue;
// if they do mark e for join groups
e=1; break;
}
if (e) break; // join found ... stop searching
}
if (!e) break; // no join found ... stop segmentation
i0=a->id; // joid ids ... rename i1 to i0
i1=b->id;
for (a=lin.dat,i=0;i<lin.num;i++,a++)
if (a->id==i1)
a->id=i0;
}
// sort lin[] by id
for (e=1;e;) for (e=0,a=&lin[0],b=&lin[1],i=1;i<lin.num;i++,a++,b++)
if (a->id>b->id) { l=*a; *a=*b; *b=l; e=1; }
// re id lin[] and prepare start/stop indexes
for (i0=-1,i1=-1,a=&lin[0],i=0;i<lin.num;i++,a++)
if (a->id==i1) a->id=i0;
else { i0++; i1=a->id; a->id=i0; ix.add(i); }
ix.add(lin.num);
// polygonize
lin_i0=lin.num;
for (j=1;j<ix.num;j++) // process hole
{
i0=ix[j-1]; i1=ix[j];
// create border pnt[] list (unique points only)
pnt.num=0; p.used=0; p.p0=-1; p.p1=-1;
for (a=&lin[i0],i=i0;i<i1;i++,a++)
{
p.i=a->i0;
p.j=a->j0;
map[p.i][p.j]=0;
for (aa=&pnt[0],e=0;e<pnt.num;e++,aa++)
if ((aa->i==p.i)&&(aa->j==p.j)) { e=-1; break; }
if (e>=0) pnt.add(p);
p.i=a->i1;
p.j=a->j1;
map[p.i][p.j]=0;
for (aa=&pnt[0],e=0;e<pnt.num;e++,aa++)
if ((aa->i==p.i)&&(aa->j==p.j)) { e=-1; break; }
if (e>=0) pnt.add(p);
}
// mark not border points
for (aa=&pnt[0],i=0;i<pnt.num;i++,aa++)
if (!aa->used) // ignore marked points
if ((aa->i>0)&&(aa->i<xs-1)) // ignore map[][] border points
if ((aa->j>0)&&(aa->j<ys-1))
{ // ignore if any non hole cell around
if (map[aa->i-1][aa->j-1]>0) continue;
if (map[aa->i-1][aa->j ]>0) continue;
if (map[aa->i-1][aa->j+1]>0) continue;
if (map[aa->i ][aa->j-1]>0) continue;
if (map[aa->i ][aa->j+1]>0) continue;
if (map[aa->i+1][aa->j-1]>0) continue;
if (map[aa->i+1][aa->j ]>0) continue;
if (map[aa->i+1][aa->j+1]>0) continue;
aa->used=1;
}
// delete marked points
for (aa=&pnt[0],e=0,i=0;i<pnt.num;i++,aa++)
if (!aa->used) { pnt[e]=*aa; e++; } pnt.num=e;
// connect neighbouring points distance=1
for (i0= 0,aa=&pnt[i0];i0<pnt.num;i0++,aa++)
if (aa->used<2)
for (i1=i0+1,bb=&pnt[i1];i1<pnt.num;i1++,bb++)
if (bb->used<2)
{
i=aa->i-bb->i; if (i<0) i=-i; e =i;
i=aa->j-bb->j; if (i<0) i=-i; e+=i;
if (e!=1) continue;
aa->used++; if (aa->p0<0) aa->p0=i1; else aa->p1=i1;
bb->used++; if (bb->p0<0) bb->p0=i0; else bb->p1=i0;
}
// try to connect neighbouring points distance=sqrt(2)
for (i0= 0,aa=&pnt[i0];i0<pnt.num;i0++,aa++)
if (aa->used<2)
for (i1=i0+1,bb=&pnt[i1];i1<pnt.num;i1++,bb++)
if (bb->used<2)
if ((aa->p0!=i1)&&(aa->p1!=i1))
if ((bb->p0!=i0)&&(bb->p1!=i0))
{
if ((aa->used)&&(aa->p0==bb->p0)) continue; // avoid small losed loops
i=aa->i-bb->i; if (i<0) i=-i; e =i*i;
i=aa->j-bb->j; if (i<0) i=-i; e+=i*i;
if (e!=2) continue;
aa->used++; if (aa->p0<0) aa->p0=i1; else aa->p1=i1;
bb->used++; if (bb->p0<0) bb->p0=i0; else bb->p1=i0;
}
// try to connect to closest point
int ii,dd;
for (i0= 0,aa=&pnt[i0];i0<pnt.num;i0++,aa++)
if (aa->used<2)
{
for (ii=-1,i1=i0+1,bb=&pnt[i1];i1<pnt.num;i1++,bb++)
if (bb->used<2)
if ((aa->p0!=i1)&&(aa->p1!=i1))
if ((bb->p0!=i0)&&(bb->p1!=i0))
{
i=aa->i-bb->i; if (i<0) i=-i; e =i*i;
i=aa->j-bb->j; if (i<0) i=-i; e+=i*i;
if ((ii<0)||(e<dd)) { ii=i1; dd=e; }
}
if (ii<0) continue;
i1=ii; bb=&pnt[i1];
aa->used++; if (aa->p0<0) aa->p0=i1; else aa->p1=i1;
bb->used++; if (bb->p0<0) bb->p0=i0; else bb->p1=i0;
}
// add connected points to lin[] ... this is hole perimeter !!!
// lines are 2 x duplicated so some additional code for sort the order of line swill be good idea
l.id=lin[ix[j-1]].id;
// add index of points instead points
int lin_i1=lin.num;
for (i0=0,aa=&pnt[i0];i0<pnt.num;i0++,aa++)
{
l.i0=i0;
if (aa->p0>i0) { l.i1=aa->p0; lin.add(l); }
if (aa->p1>i0) { l.i1=aa->p1; lin.add(l); }
}
// reorder perimeter lines
for (i0=lin_i1,a=&lin[i0];i0<lin.num-1;i0++,a++)
for (i1=i0+1 ,b=&lin[i1];i1<lin.num ;i1++,b++)
{
if (a->i1==b->i0) { a++; l=*a; *a=*b; *b=l; a--; break; }
if (a->i1==b->i1) { a++; l=*a; *a=*b; *b=l; i=a->i0; a->i0=a->i1; a->i1=i; a--; break; }
}
// convert point indexes to points
for (i0=lin_i1,a=&lin[i0];i0<lin.num;i0++,a++)
{
bb=&pnt[a->i0]; a->i0=bb->i; a->j0=bb->j;
bb=&pnt[a->i1]; a->i1=bb->i; a->j1=bb->j;
}
}
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
这篇关于确定解决迷宫的线段的最小数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
