三角网格

[编程题]三角网格

热度指数：769 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

【注意：本题按通过的Case比例给分】

三角网格是计算机图形学中表示物体的常用形式，我们常用一个顶点索引和三角形索引表示具体网格。

在一个三角网格中，如果两个三角形共用同一条边则称这两个三角形是相连的，如果一个三角网格的任意两个三角形都直接或间接相连，则称这个三角网格是连通的。
如果一个三角网格可以展开成平面图，这称这个三角网格为平面三角网格，在平面三角网格中，单个三角形的顶点可以有顺时针或者逆时针两种排列，代表了三角形两种不同的朝向。
给定一个N个顶点，M个三角形组成的平面连通三角网格，需要你调整所有三角形索引的顶点顺序，使得所有三角形都和输入的第一个三角形具有相同的朝向，并且在每个三角形内部，序号最小的顶点放在首位。

输入描述:

第一行，两个整数N，M 表示有N个顶点和M个三角形 (3<=N<=400, 1<=M<800)
接下来M行，每行三个数字Ai, Bi, Ci(1<=Ai<=N, 1<=Bi<=N, 1<Ci<=N)，表示第i个三角形的顶点序号

输出描述:

输出M行，每行三个数字，表示调整后的三角形顶点索引，输出的三角形顺序需要和输入保持一致。

示例1

输入

输出

算法知识视频讲解

Python

greatofdream

构造三叉树并使用bfs搜索，但是对于判断相邻的三角形是否同向比较笨拙，需要改进

import sys
class Node():
    def __init__(self, index, vertex):
        self.index = index
        self.vertex = vertex
        self.children = []
        self.visited = False
        self.rotated = False
    def rotate(self):
        self.vertex = [self.vertex[0], self.vertex[2], self.vertex[1]]
    def order(self):
        ind = self.vertex.index(min(self.vertex))
        if ind==1:
            self.vertex = [self.vertex[1], self.vertex[2], self.vertex[0]]
        elif ind==2:
            self.vertex = [self.vertex[2], self.vertex[0], self.vertex[1]]
        # print(self.vertex)
## 构造边列表加速查询
edges = dict({})
nodes = []
N, M = map(int, sys.stdin.readline().split())
# 三叉树
for i in range(M):
    tri = list(map(int, sys.stdin.readline().split()))
    nodes.append(Node(i, tri))
    # 查询是否有相邻三角
    for j in range(3):
        v1, v2 = tri[j], tri[(j+1)%3]
        if v1 > v2:
            v1, v2 = v2, v1
        if (v1, v2) in edges:
            nodes[edges[(v1, v2)]].children.append((v1, v2, i))
            nodes[i].children.append((v1, v2, edges[(v1, v2)]))
        else:
            edges[(v1, v2)] = i
# BFS
neighbor = []
neighbor.append(nodes[0])
nodes[0].order()
nodes[0].rotated = True
while len(neighbor)!=0:
    node = neighbor.pop()
    node.visited = True
    for i in node.children:
        if nodes[i[2]].visited==False:
            # 旋转方向并入栈
            if nodes[i[2]].rotated==False:
                edge = i[0:2]
                ind0, ind1 = node.vertex.index(edge[0]), node.vertex.index(edge[1])
                in0, in1 = nodes[i[2]].vertex.index(edge[0]), nodes[i[2]].vertex.index(edge[1])
                # print(ind0, ind1, in0, in1, ((ind1-ind0+3)%3), ((in1-in0+3)%3))
                if ((ind1-ind0+3)%3) == ((in1-in0+3)%3):
                    nodes[i[2]].rotate()
                nodes[i[2]].order()
                nodes[i[2]].rotated = True
            neighbor.append(nodes[i[2]])
for i in range(M):
    print(' '.join(map(str, nodes[i].vertex)))

编辑于 2025-04-12 15:58:34 回复(0)