我的对象是在蜂窝网格中构建的。所有对象都已连接。红线代表每个节点之间的连接。我听说二进制空间分区（BSP）树在这种类型的问题上很好，但不知道在我的情况下前后是什么。我需要一种方法来构建带孔的2D多边形
我实现使用蜂窝状网格系统的查找如图所示（X，Y）
class Node {
Point position; //center position
Point grid; //honeycomb grid system
}
class MyObject {
Node lookup(Point grid);
}
我需要表示作为用户添加更多节点到场景上，一种方法，图中的数据结构迅速确定网格点（针对MyObject）： 1.外 2.内部 3.孔内
有多大你正在工作的空间？
用一个简单的矩形网格模拟整个事情，假设偶数行错开右边。
任何节点具有坐标[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）的边界所有未选中空节点，并使用上述算法，以纪念他们为外。所有剩余的空节点都是空洞。
根据您的网格大小，您可以将其作为包含对象状态（或甚至char s，状态为数字位）的二维二维数组结构/对象，尺寸为[MAX_X + 1] [MAX_Y + 1]如果它的大小合理，或者是一个完整节点的列表（矢量），每个节点都包含它的坐标，状态，并且如果你想让它更快地达到最优速度，那么它就是邻居。在这种情况下，搜索形状，找到所有空的邻居节点的潜在漏洞。具有极端坐标（最低/最高x/y）的边缘节点属于“外部”。跟随那些有完全邻居的空的邻居，找到形状的外缘。所有剩下的都是内部边缘，在遵循算法开始之后，您将拥有所有的“洞”。
我的建议：
替代地，在使用平方的近似值，例如，工作，因为在这里看到：
我需要我美味的早晨咖啡，但我不知道如何在哥斯达黎加工作咖啡机，但是当我不可避免地在天花板上弄到地面和牛奶时，我可以试着煮咖啡来寻求帮助。你需要为你的问题做同样的事情 - 展示你到目前为止所尝试的内容，无论是代码（最好）还是你已经完成的任何研究 – Bojangles
如果你想使用现成的实现boost提供几何库。 –
了解更多有关更大问题的信息可能会让我们更好地了解最佳解决方案。 –