从二维图块数组创建多边形形状
我有一个 2D 数组，其中仅包含布尔值，显示数组中该点是否存在图块。其工作原理如下，假设如果 array[5,6] 为 true，则坐标 (5,6) 处有一个图块。数组描述的形状是一个连通的多边形，内部可能有孔。
基本上我需要的是描述数组中形状的顶点和面的列表。
我已经寻找了一段时间，找不到解决这个问题的方法，任何帮助将不胜感激。
编辑：这一切都已完成，以便我可以获取形状并将它们碰撞在一起。
这个项目只是我正在做的事情，以帮助提高我的编程技能/物理等。Edit2
：感谢所有的帮助。基本上我的问题与将位图图像转换为矢量图像非常相似。如果其他人在未来遇到我曾经做过的同样的问题。
I have a 2D array which just contains boolean values showing if there is a tile at that point in the array or not. This works as follows, say if array[5,6] is true then there is a tile at the co-ordinate (5,6). The shape described by the array is a connected polygon possibly with holes inside of it.
Essentially all i need is a list of vertex's and faces which describe the shape in the array.
I have looked for a while and could not find a solution to this problem, any help would be appreciated.
Edit: This is all done so that i can then take the shapes and collide them together.
This project is just something i am doing to help advance my programming skills / physics etc.
Edit2: Thanks for all the help. Basicly my problem was very similar to converting a bitmap image to a vector image. http://cardhouse.com/computer/vector.htm is useful if someone else in the future encounters the same problems i have done.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
不要过分关注单个像素。重点关注像素的角点 - 四个像素相交的点。这些角的坐标将非常类似于像素的半开坐标。半开界限包含下界，但不包含上限，因此从 1 到 3 的半开范围为 {1, 2}。
定义一组边缘 - 两个像素之间的单像素长线（垂直或水平）。然后形成一个邻接图 - 如果两条边共享一个点，则它们是相邻的。
接下来，识别连接的边集 - 每个点都直接或间接连接到其他点的子图。从逻辑上讲，大多数连接的子图应该形成闭环，并且您应该确保所有循环都被视为简单的闭环。
问题之一是位图的边缘。如果您想象您的位图是无限位图的一小部分，其中每个越界像素的值为 0，则可能会简化事情。根据该规则在位图边缘包含像素边缘。这应该确保所有循环都已关闭。
另外，考虑那些有四个边界边缘的像素角 - 即像素图案是其中之一...
在这些情况下，“1”像素应被视为单独多边形的一部分（否则您最终会得到缠绕） -规则并发症）。在这些情况下调整邻接规则，以便基本上得到两个连接的（直角）边，它们碰巧在一个点处接触，但不被视为相邻。它们仍然可以连接，但只能通过其他边缘间接连接。
另外，使用附加的标志数组来识别已在循环中使用的像素边缘 - 也许一个用于水平边缘，一个用于垂直边缘。这应该可以更轻松地找到所有循环，而无需重复评估任何循环 - 您扫描主位图，当您发现相关边缘时，您可以在扫描周围以找到整个循环之前检查这些数组。当您扫描循环时，您可以在这些数组中设置相关标志（或循环 ID 号）。
顺便说一句 - 不要将这些步骤视为字面上的构建此数据结构的步骤，而更多地将其视为抽象层。关键是要意识到您正在执行图形操作。您甚至可以使用引用位图的适配器，但提供适合某些图形算法直接使用的接口，就好像它使用专门的图形数据结构一样。
要测试特定循环是否是孔，请选取（例如）最左侧的垂直像素边缘（在循环上）。如果右侧的像素被填充，则该循环是多边形边界。如果左边的像素被填充，则循环就是一个洞。注意 - 一个好的测试像素可能是在跟踪循环之前找到第一个像素边缘时找到的像素。这可能不是最左边的边缘，但它将是该扫描线的最左边/最上面。
最后一个问题是简化 - 找出像素边缘一起形成直线的位置。这可能可以内置到首先识别循环的扫描中，但最好在开始扫描之前找到一个角点。完成后，每条线都使用 while-I-can-continue-tracing-the-same-direction 循环来识别 - 但要注意那些两个多边形在角点接触的问题。
尝试将所有这些东西组合起来可能听起来像一个复杂的混乱，但诀窍是将问题分成不同的类/函数，例如使用提供底层（例如位图）抽象视图的类。不要太担心调用开销或优化 - 内联和其他编译器优化应该可以处理这个问题。
真正有趣的是一些矢量图形程序已经做了一段时间的更智能的跟踪，您可以在其中获得对角线、曲线等。
Don't focus too much on the individual pixels. Focus on the corners of the pixels - the points where four pixels meet. The co-ordinates of these corners will work a lot like half-open co-ordinates of the pixels. Half-open bounds are inclusive at the lower bound, but exclusive at the upper bound, so the half-open range from one to three is {1, 2}.
Define a set of edges - single-pixel-long lines (vertical or horizontal) between two pixels. Then form an adjacency graph - two edges are adjacent if they share a point.
Next, identify connected sets of edges - the subgraphs where every point is connected, directly or indirectly, to every other. Logically, most connected subgraphs should form closed loops, and you should ensure that ALL loops are considered simple, closed loops.
One issue is the edge of your bitmap. It may simplify things if you imagine that your bitmap is a small part of an infinite bitmap, where every out-of-bounds pixel has value 0. Include pixel-edges on the edge of the bitmap based on that rule. That should ensure all loops are closed.
Also, consider those pixel-corners where you have four boundary edges - ie where the pixel pattern is one of...
The these cases, the '1' pixels should be considered part of separate polygons (otherwise you'll end up with winding-rule complications). Tweak the rules for adjacency in these cases so that you basically get two connected (right-angle) edges that happen to touch at a point, but aren't considered adjacent. They could still be connected, but only indirectly, via other edges.
Also, use additional arrays of flags to identify pixel-edges that have already been used in loops - perhaps one for horizontal edges, one for vertical. This should make it easier to find all loops without repeatedly evaluating any - you scan your main bitmap and when you spot a relevant edge, you check these arrays before scanning around to find the whole loop. As you scan around a loop, you set the relevant flags (or loop ID numbers) in these arrays.
BTW - don't think of these steps as all being literal build-this-data-structure steps, but more as layers of abstraction. The key point is to realise that you are doing graph operations. You might even use an adaptor that references your bitmap, but provides an interface suitable for some graph algorithm to use directly, as if it were using a specialised graph data structure.
To test whether a particular loop is a hole or not, pick (for example) a leftmost vertical pixel edge (on the loop). If the pixel to the right is filled, the loop is a polygon boundary. If the pixel to the left is filled, the loop is a hole. Note - a good test pixel is probably the one you found when you found the first pixel-edge, prior to tracing around the loop. This may not be the leftmost such edge, but it will be the leftmost/uppermost in that scan line.
The final issue is simplifying - spotting where pixel-edges run together into straight lines. That can probably be built into the scan that identifies a loop in the first place, but it is probably best to find a corner before starting the scan proper. That done, each line is identified using a while-I-can-continue-tracing-the-same-direction loop - but watch for those two-polygons-touching-at-a-corner issues.
Trying to combine all this stuff may sound like a complicated mess, but the trick is to separate issues into different classes/functions, e.g. using classes that provide abstracted views of underlying layers such as your bitmap. Don't worry too much about call overheads or optimisation - inline and other compiler optimisations should handle that.
What would be really interesting is the more intelligent tracing that some vector graphics programs have been doing for a while now, where you can get diagonals, curves etc.
您必须澄清您想要的结果。像下面这样的输入
作为
输入？如果是，这看起来相当微不足道 - 如果有一个四边形，为什么不为每个数组条目生成一个四边形，否则什么也不生成？
您可以使用简单的状态机来解决此问题。当前状态由当前位置 (x,y) 和当前方向组成 - 左 (L)、右 (R)、上 (U) 或下 (D)。 “X”是当前位置，有八个邻居可以控制状态变化。
然后只需遵循以下规则 - 在状态 X、Y、D 中检查两个给定字段并相应地更改状态。
You will have to clarify your desired result. Something like the following
given
as the input? If yes, this seems quite trivial - why don't you just generate one quadrilateral per array entry if there is a one, otherwise nothing?
You can solve this problem using a simple state machine. The current state consist of the current position (x,y) and the current direction - either left (L), right (R), up (U), or down (D). The 'X' is the current position and there are eight neighbors that may control the state change.
Then just follow the following rules - in state X,Y,D check the two given fields and change the state accordingly.