如何根据顶点和边求封闭图形

Question

已知：点坐标和边的两个顶点编号
如何求出来哪些点和哪些边可以组成封闭图形呢？

Answer 1

引自免费微信小程序：皆我百晓生

为了确定一组点和边是否能构成一个封闭图形（例如多边形），我们可以遵循以下几个步骤：

1. 确保所有点都在同一平面上。
2. 检查每个边是否连接两个不同的顶点，并且这些顶点在列表中只出现一次。
3. 边的顺序应该是连续的，也就是说，从一个顶点出发，沿着边的顺序应该最终回到起始顶点。

这里是一个Python函数，它接受点的坐标（作为元组列表）和边的定义（作为包含两个顶点索引的元组列表），并返回一个布尔值，表示这些点和边是否能构成一个封闭图形：

def are_points_and_edges_a_polygon(points, edges):
    # Step 1: Check if all points are in the same plane (assuming z-coordinate is 0)
    assert len(set(p[2] for p in points)) == 1, "Points must be on the same plane"

    # Step 2: Ensure each edge connects two different vertices and they appear only once
    unique_vertices = set()
    for edge in edges:
        vertex1, vertex2 = sorted(edge)  # Ensure consistent ordering
        if vertex1 not in unique_vertices or vertex2 not in unique_vertices:
            unique_vertices.add(vertex1)
            unique_vertices.add(vertex2)
        else:
            return False  # Vertex appears more than once

    if len(unique_vertices) != len(points):  # Ensure all points are used
        return False

    # Step 3: Check if the edges form a closed loop
    current_vertex = edges[0][0]
    for i in range(len(edges)):
        next_edge = edges[(i + 1) % len(edges)]
        if next_edge[0] != current_vertex:
            return False
        current_vertex = next_edge[1]

    return True

# Example usage:
points = [(0, 0), (0, 1), (1, 1), (1, 0)]
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
print(are_points_and_edges_a_polygon(points, edges))  # Output: True

这个函数首先检查所有的点是否在同一平面上，然后确保每个顶点仅被使用一次，最后通过遍历边的顺序来确认它们是否形成一个闭环。如果满足所有条件，则返回True，否则返回False。

请注意，这个函数假定输入的点是有序的，即它们按照一定的顺序形成了闭合路径。如果你的输入数据没有这样的信息，可能需要额外处理来找到正确的起点并调整边的顺序。此外，这个函数不考虑边的方向性，所以如果边有方向，你需要对边进行排序以保持一致的方向。