正方形网格中的多边形 [英] Polygon from a grid of squares
问题描述
我正在寻找一种算法，以找到包围没有孔的正方形连续网格的多边形，如下所示:
I'm looking for an algorithm to find the polygon that surrounds a contiguous grid of squares without holes as shown here:
.
我已经拥有每个网格正方形，这些正方形存储有关构成其周围区域(即顶部，右上角，顶部-底部，无边缘等)的边缘类型的数据，认为该数据可以被算法利用.如果有人可以为这种算法提供一些伪代码，那就太好了.
I already have each of the grid squares storing data about the kind of edges with the surrounding area that they are composed of (i.e. top, top-right, top-bottom, no edges, etc.), so I'm thinking that this data could be utilized by the algorithm. If someone could provide some pseudocode for such an algorithm that would also be great.
该算法的输入将是一个数据对象列表，每个对象都有一个Vector2Int描述网格位置(请注意，这些只是网格内的位置，而不是顶点)，以及一个枚举，它给出了边缘的类型广场与周围地区都有.假定每个网格正方形的大小为一个单位，输出将是描述周围多边形的顶点的Vector2的有序列表.
The input to the algorithm would be a list of data objects, each with a Vector2Int describing the grid positions (note that these are simply positions within a grid, not vertices) as well as an Enum that gives the type of edges that the square has with the surrounding area. The output would be an ordered list of Vector2s describing the vertices of the surrounding polygon, assuming that each grid square is one unit in size.
我在下面的链接中发现了一个类似的问题，但是我想对我的情况特有的算法进行详细说明，特别是考虑到我已经存储的关于边缘的数据.我还希望该算法避免计算每个平方的顶点，并运行一堆直接搜索以消除共享的顶点，因为我觉得这对于我的特定应用程序可能在计算上过于昂贵.我只是怀疑必须有更好的方法.
I have found a similar question in the link below, but I wanted some elaboration on the kind of algorithm that would be specific to my case, especially given the data that I already have stored about the edges. I'd also prefer the algorithm to avoid calculating each of the squares' vertices and running a bunch of straightforward searches to eliminate the shared ones, as I feel that this might be too computationally expensive for my particular application. I just have a suspicion that there has to be a better way.
现在，我开始认为某种迷宫行走算法实际上可能适合我的情况.我正在研究一个我认为会起作用的解决方案，但是编写起来非常麻烦(需要对矩形边缘和围绕圆周的行进方向进行大量的条件检查)，并且可能不如可能的快
Now I'm beginning to think that some sort of maze walking algorithm might actually be appropriate for my situation. I'm working on a solution that I think will work, but it's very cumbersome to write (involving a tonne of conditional checks against the square edges and the direction of travel around the circumference) and probably isn't as fast as it could be.
推荐答案
我不确定您的数据结构所包含的内容，并且我假设您有一个通过某个点(角点或中心点)的坐标已知的正方形列表).
I am not sure to understand what your data structure contains, and I assume that you have a list of squares known by the coordinates of some point (corner or center).
计算边界框并创建相同大小的二进制位图.除非几何图形真正稀疏，否则位图的面积将与平方数的数量级相同.
Compute the bounding box and create a binary bitmap of the same size. Unless the geometry is really sparse, the area of the bitmap will be of the same order as the number of squares.
对于每个正方形，将相应的像素涂成黑色.然后使用轮廓算法.要获得正方形的轮廓，您将需要在像素到像素移动与要附加的轮廓片段之间设计一个对应表.
For every square, paint the corresponding pixel black. Then use a contouring algorithm. To obtain the outline of the squares, you will need to design a correspondence table between the pixl-to-pixel moves and the outline fragments to be appended.
这篇关于正方形网格中的多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
