3D Delaunay 增量算法的最佳初始形状是什么?

本文介绍了3D Delaunay 增量算法的最佳初始形状是什么?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在使用增量方法制作 3D Delaunay.我已经在 2D 中使用初始三角形对其进行了测试，用于插入顶点并且效果很好，但是如果我将三角形用于 3D，则某些顶点不会落入任何外接球体中，因此它们不会被插入.我尝试过使用四面体，但如果第一个节点落入四个面中，则所有顶点都会创建朝向这个新顶点的新边，并删除所有初始三角形.

I'm doing 3D Delaunay, with the incremental method. I've tested it in 2D with an initial triangle for inserting the vertices and it works great, but if I use a triangle for 3D, some vertices do not fall into any circumscribed sphere therefore they don't get inserted. I've tried with a tetrahedron but if the first node falls into the four of the faces, all vertices create new edges towards this new vertex, and deletes all of the initial triangles.

推荐答案

你可以阅读我对这个问题的回答 (Bowyer-Watson 算法:如何通过删除具有超三角形顶点的三角形来填充左侧的洞").如果超三角形太小，有时你会以超三角形外的外接圆结束.您可以尝试多边形内点测试来避免它.

You can read my answer for this question (Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices). If the supertriangle is too small sometimes you end with circumcircle outside of the supertriangle. You can try a point-in-polygon test to avoid it.