检查所有顶点是否都连接在一个循环中

Question

我正在编写一个项目，您可以在其中绘制一个带有顶点和连接它们的线的多边形，然后运行将它们放入像 pymunk 这样的物理引擎中。

我想确保所有顶点都像这样连接成一个循环

如果没有像这样完全连接

每个顶点都是一个下面的 Vertex 对象

class Vertex():
    def __init__(self, id, position, pointsTo = [], rectSize = [10, 10]):
        self.id = int(id)
        self.position = tuple(position)
        self.rect = tuple((position[0], position[1], rectSize[0], rectSize[1]))
        self.pointsTo = list(pointsTo)

    def setPosition(self, position):
        self.position = tuple((position[0] - (self.rect[2] / 2), position[1] - (self.rect[3] / 2)))
        self.rect = tuple((self.position[0], self.position[1], self.rect[2], self.rect[3]))

    def getRect(self):
        return self.rect

其中 pointsTo 是连接到该顶点的顶点列表 .我如何找到顶点列表是否在循环中连接在一起[=13=]

Answer 1

如果我们把它看成一个图，我们有顶点，pointsTo是边的邻接表。我还假设一个无向图，基于问题中的插图，所以如果 A->B 那么 B->A。我们可以将多边形视为 N 循环。我忽略了屏幕上边缘交叉的可能性，图中没有实际顶点。

假设是N循环。那么每个顶点恰好有两条边，所有的顶点都是相连的。这两者都很容易测试。

(注意：如果每个顶点恰好有两条边，那么你已经连接起来了。连接测试只是看是否有多个多边形，或者只有一个多边形，以便证明更容易。见https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg 对于类似的概念。正如那个著名的问题所示，如果您允许多个多边形但只想测试未链接到多边形中的额外线，则可以测试 even。）

现在，假设一个图通过了上述测试——假设，从任意点开始并开始访问图后面的 pointsTo 顶点，从不使用之前访问过的 edge/vertex。每次你访问一个新的顶点，这是你第一次到那里，因此你不能在那个顶点使用其他 pointsTo，所以你可以继续，直到你运行个顶点。那时，您有两个未使用的 pointsTo——一个进入起始顶点，一个离开结束顶点。它们要么指向一个不存在的顶点，要么指向彼此，这意味着它是一个 N 循环。

至此上述测试得证

我说过测试东西很容易，所以我应该这样做：要测试图形是否连通，请参阅 https://en.wikipedia.org/wiki/Connectivity_(graph_theory)

为所有顶点添加一个已访问标志（初始化为false）。选择任何顶点，然后开始访问邻居。当你运行出去的时候，看看有没有哪个顶点还没有被访问过。

或者制作一组vertex.id的，访问时添加它们。最后，检查 len(that set) 是图中的顶点数

Answer 2

您需要查看 Strongly Connected Component 的定义，然后测试您的图是否由 Vertex 和 Edges 表示，即 Vertex.pointsTo 是否形成强连接包含列表中所有顶点的组件。

检查所有顶点是否都连接在一个循环中

Checking if all vertices are connect in a loop

python

pygame

polygon