追踪顶点的连接并确定何时形成多边形。

Question

追踪顶点的连接并确定何时形成多边形。

c#algorithmgeometrypolygongraph-theory

4

我正在尝试在 C# 中开发一个游戏机制，涉及连接顶点并形成多边形。

可以有 5 到 30 个顶点。每个顶点可以用一条直线连接（这些线不能相交）。当一条线闭合了一个多边形时，多边形内部会被涂上特定的颜色。（如果在闭合过程中多边形内部会存在一个点，则无法关闭该多边形）

例如，下面的两张图片不可能出现：

然而，这可以：

我遇到的问题是如何区分刚刚闭合的多边形并记住它（以防我关闭与其共享边缘的多边形）。我可以有多个闭合的多边形，直到可以从每个顶点绘制不违反交叉规则的所有线条为止。

我尝试记住已绘制的线条AB、ED、CD、CA等，并寻找循环，但当我关闭多个多边形时，我需要更多信息才能知道哪些多边形已经闭合。但我很难想出如何做到这一点。

例如（下图），如果绘制了线n，我想找到刚刚创建的多边形。

有人知道我该如何实现这个吗？任何想法、帮助或见解都会很有帮助。

- Ivan Horvatin

这篇论文可能会有所帮助：从一组线条中检测多边形，http://www.inesc-id.pt/pt/indicadores/Ficheiros/936.pdf - meowgoesthedog

如果您已经有代码来检查是否创建了有效的多边形，那么包括线条 n 的任何有效多边形都将是新的...至少我认为是这样的 :P - Theo Walton

2个回答

1

当玩家试图声明一个新边缘时，您可以：

检查该边缘是否与现有的已声明边缘相交；
对于已声明边缘（不在两个多边形边界上），执行广度优先搜索以查看是否存在从新边缘一端开始并到达另一端的路径 - 在这种情况下将形成一个多边形；
如果已经形成了一个多边形：
- 检查多边形内是否有任何顶点 - 如果有，则玩家无法声明该边缘。
- 每条边都有两个侧面。所形成多边形的内部将位于其边界沿着每条边的一侧 - 您可以跟踪此内容，然后任何后续多边形也必须在这些边的另一侧（或多侧）被限制在游戏中有效选择的范围内。如果一条边的两侧都有声明的多边形，则该边不能位于任何后续多边形的边界上。

你可能需要在点周围生成凸包，以排除外部多边形，这样当玩家形成多边形时，他们将被限制在凸包的内部。

- MT0

有什么方法可以计算多边形的哪一侧是形成的吗？我正在思考和寻找方法，但似乎无法理解如何以及为什么。您能提供更多见解吗？ - Ivan Horvatin

请查看 https://dev59.com/qH3aa4cB1Zd3GeqPZi1x。您可以在线段中心的垂直方向上略微偏移一个虚拟点（确保偏移量小于任意两个点之间最小距离的一半），并从该点沿给定方向（例如垂直方向）投射一条射线（直线）。如果射线与多边形边界相交奇数次，则在多边形内部，如果是偶数次，则在外部。 - MT0

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James Barrass · Accepted Answer

可能有点简单，但你可以存储一个Dictionary<Face,List<Vertex>>，然后使用linq进行查询。你可以通过添加反向查找来简化它。Dictionary<Vertex, List<Faces>>。

场景1：路径触碰到同一面的边缘

为了测试新路径DC，你需要获取2个顶点D和C，并找到包含这两个顶点的所有面。从D开始在List<Vertex>中创建路径到C。

现在用C -> D做同样的事情。

现在你有了2条路径，D -> E -> C和C -> A -> B -> D，都使用D -> C形成有效的面，现在你必须枚举所有顶点并消除任何包含现有顶点的面。

场景2：路径触碰到不属于任何面的边缘

这条路径是开放的。

场景3：路径触及不同面的边缘

面1：ABDEC 面2：AGF

测试路径FC。F是面2的一部分，C是面1的一部分。

查找交点：Face1.Face2 == A，这是两个列表中唯一的点，这次你得到了2组2条路径。

FA
FGA

AC
ABDEC

要从F到达A，需要将这些路径相乘

FAC FGAC FABDEC FGABDEC

现在可以测试这些面是否有效。

对于这种更复杂的情况（3个面接触，面共享边缘），也许保留所有连接边缘的图形会更容易，这将为检测两个顶点之间可能的路径提供更简单的方法。

请注意，包含3个顶点的任何路径都形成一个可能的面，可以检查其有效性。