问检查是否所有顶点都在循环中连接。
EN

Stack Overflow用户

提问于 2017-05-14 02:40:54

回答 2查看 753关注 0票数 0

我正在写一个项目，你可以画一个多边形与顶点和线连接，然后将它们运行到一个物理引擎，像pymunk。

我想确保所有的顶点都在这样的循环中连接

如果它没有像这样完全连接起来

每个顶点是一个顶点对象，如下所示

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是连接到该顶点的顶点列表，如果一个循环中的顶点列表被连接在一起，.How会找到它。

polygon

python

pygame

平台电商解决方案

为客户提供电商客服、电商图片系统识别及搜索的快速搭建方案

回答 2

Stack Overflow用户

回答已采纳

发布于 2017-05-14 05:09:43

如果我们把它看作一个图，我们就有了顶点，pointsTo是一个边的邻接列表。我也假设一个无向图，基于问题中的插图，所以如果A->B那么B->A，我们可以把多边形看作N圈。我忽略了屏幕上没有实际顶点的情况下的边交叉的可能性。

假设它是一个N-循环.然后每个顶点正好有两个边，所有的顶点都是连通的。这两种方法都很容易测试。

(注:如果每个顶点都有两条边，那么你就有了连接。连接的测试只是看看是否有多个多边形，或仅仅一个，并使证明更容易。有关类似的概念，请参见K%C3%B6nigsberg。正如这个著名的问题所显示的，如果允许多个多边形，但只想测试没有连接到多边形的额外行，则可以测试偶数。)

现在，假设一个图通过了上述测试--假设，从任意点开始，然后开始访问图后面的pointsTo顶点，而不使用以前访问过的边/顶点。每次访问一个新的顶点，这都是您第一次访问，因此您不能在该顶点使用其他pointsTo，因此您可以继续到顶点用完为止。那时，您有两个未使用的pointsTo --一个进入起始顶点，另一个进入结束顶点。它们要么pointsTo一个不存在的顶点，要么彼此pointsTo，这意味着它是一个N圈。

从而证明了上述测试的正确性。

我说过测试事物很容易，所以我应该这样做:要测试图形是否连通，请参阅理论)。

将已访问的标志(初始化为false)添加到所有顶点。选择任何一个顶点，然后开始访问邻居。当您用完时，查看是否有任何顶点未被访问。

或者创建一组vertex.id，在访问时添加它们。最后，检查len(该集合)是图中的顶点数。

票数 1