algorithm - 我需要一种构造带孔的2D多边形的方法

我的物体是在蜂窝状网格中建造的所有对象都已连接。红线表示每个节点之间的连接。我听说二进制空间分区（BSP）树很好地解决了这类问题，但不确定在我的例子中前面和后面是什么。
我已经使用蜂巢网格系统实现了查找，如图所示（x，y）

class Node {
    Point position; //center position
    Point grid; //honeycomb grid system
}

class MyObject {
    Node lookup(Point grid);
}

我需要一个数据结构，当用户向场景中添加更多节点时表示图形，并且需要一种快速确定网格点是否为（相对于MyObject）的方法：
一。外部
2.里面
三。在洞里

最佳答案

你工作的地方有多大？
用一个简单的矩形网格来模拟整个过程，假设偶数行是错开的。
任何节点的坐标[x,y]
对于(y%2 == 0)邻居节点是[x-1,y][x+1,y][x,y+1][x,y-1][x-1,y-1][x-1,y+1]
对于(y%2 == 1)邻居节点是[x-1,y][x+1,y][x,y+1][x,y-1][x+1,y-1][x+1,y+1]
每个节点可以是完整的或空的，空的节点可以被选中或不选中。最初不检查所有空节点。
通过以下方式检查节点是否属于孔：
如果节点已满-它不属于孔，它属于形状。
如果节点为空，则将节点标记为选中。
遍历所有邻居节点：
跳过标记为选中或已满的节点
递归地对所有未选中的节点重复搜索。
如果递归将您带入任何x<0, y<0, x>MAX_X, y>MAX_Y，则中止。节点在形状之外
如果递归结束时未找到游戏场的边，则该节点属于一个洞。
此外，现在可以重复将所有已检查节点转换为外部节点或孔的过程，以供以后参考。
如果要在开始时索引所有孔，可能更容易在运动场（x==0, y==0, x==MAX_X, y==MAX_Y）的边界处找到所有未选中的空节点，并使用上面的算法将它们标记为外部所有剩余的空节点都是洞。
根据网格大小，您可以将其实现为二维结构/对象数组，其中包含对象状态（甚至chars，状态为数字位）、大小为[MAX_X+1][MAX_Y+1]，如果大小合理，或者作为完整节点的列表（向量），每个节点都包含其坐标、状态，如果您希望速度更优化，还可以是邻居在这种情况下，搜索形状，查找所有空的邻居节点以查找潜在的孔。具有极坐标（最低/最高x/y）的边节点属于“外部”跟随他们的空邻居有完整的邻居，找到形状的外缘。所有剩余的都是内部边缘，在遵循从它们开始的算法之后，你将拥有所有的“洞”。

关于algorithm - 我需要一种构造带孔的2D多边形的方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20236883/