作为输入，我有一组三角形，它们形成带孔的凹网格。每个三角形由三个顶点组成：（vi，vj，vk）不提供邻接信息。算法必须将具有相同法向的三角形集合“并集”成多边形。所以输出是（pi，pj，pk，…，ps），。。。
例如（见下图），假设我们有由三角形组成的网格
（v0，v1，v4），（v1，v3，v4），（v1，v2，v3）
（v2，v6，v4），（v6，v5，v4）。
作为输出，我们有：
（p0，p1，p4）
（p1，p2，p3，p4）
我在寻找解决上述问题的有效算法。任何建议，提示或文章都是值得赞赏的。
最佳答案
看看自适应网格粗化算法这些通常用于计算流体动力学（Ansys CFX，CD-Adapco Star CCM+等）的高级软件/结构动力学（anasys等人）。其中，对给定网格的自动细化和粗化是有利的。
一些免费的论文可以让你在这个问题上有一个很强的起点：
https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/coarsening.pdf
http://tetra.mech.ubc.ca/ANSLab/publications/coarsen.pdf
http://www.cs.cmu.edu/~glmiller/Publications/MiTaTe98.pdf（这相当数学化）
google在自适应网格细化算法领域的额外搜索将揭示关于该主题的类似论文。
编辑自适应网格协同的一种基本方法是边折叠方法，它将一个边减少到一个顶点，从而删除两个元素。李旭，谢泼德M.S.，比亚尔M.W.“网格修改的三维各向异性网格适配”，《应用力学与工程的计算机方法》，2004年。有一个很大的粗化算法，在伪代码中定义为
for all edge in short edge list do
for all vertex that bounds the current edge do
if vertex is not yet tagger then
append vertex to dynamic list
tag vertex to be in dynamic list
end if
end for
end for
while vertices not tagged processed in dynamic list do
get an unprocessed vertex Vi from the list
get Ej , the shortest mesh edge in transformed space connected to Vi
if the transformed length Ej is greater than Llow then
remove Vi from the dynamic list
else
evaluate edge collapse operation of collapsing Ej with Vi removed
if the edge collapse would create an edge longer than Lmax then
evaluate relocated vertex Vi
else if the edge collapse would lead to
at/inverted elements then
evaluate the swaps(s)/collapse compound operation
end if
if any local mesh modication is determined then
tag neighbouring vertices of Vi in the dynamic list as unprocessed
apply the local mesh modication
remove Vi from the dynamic list if it is collapse
else
tag Vi as processed
end if
end if
end while
这是从一个令人印象深刻的硕士论文，我在过去使用。可以找到here
我希望这能有帮助。
关于algorithm - 分割的逆任务，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10928383/