我已经编写了一些糟糕的代码来实现 3D Delauney 三角剖分的目标（E3 中的随机点），但是耗时是巨大的，并且当五个点恰好（或几乎由于舍入误差）在一个球体上时，我的代码无法正确处理这种情况。
我使用基本数据结构，即四面体列表和点列表以及四面体与其邻域的关系列表。该算法是增量插入。
有人能告诉我我应该更喜欢哪种数据结构和算法吗？在这种情况下可以使用四边数据结构吗？当我阅读关于这个主题的论文时，我发现这个数据结构可能不适合 3D 应用（严格来说，不适合 3D 流形应用？我昨天才知道什么是流形，请帮帮我......）。分治法是更好的算法吗？谢谢！
这是在 scipy (python) 提供的 qhull 中实现的。如果由于某种原因您不能直接使用这些实现，文档中对数据结构的解释可能会有所帮助。
3D 中的数据结构是纯代数的。
您需要的是以下数组：
Vertex V：网格的顶点坐标，a数组，每列是-,- 和-坐标，并且行索引对应于该顶点的索引。
Element to Vertex E2V：四面体元素到顶点编号，a大批。每行代表一个四面体，该行上的每一列是该四面体的索引顶点（该特定索引的行号V）。
Face to Vertex F2V：三角形面向顶点编号，带有大批。每行代表一个面，该行上的每一列是该面的索引顶点（该特定索引的行号V）。
Edge to Vertex F2V: 边到顶点编号，带有大批。每行代表一条边，该行上的每一列是该边的索引顶点（该特定索引的行号V）。
前两个是必要的数据结构，所有其他数组都可以使用代数运算从前两个生成。其他值得注意的数组是Element to Edge, Face to Edge, Vertex to Element（共享顶点的元素），Face to Element（共享面的元素）， Edge to Face（共享边的面）等。
3D Delaunay 三角测量的实施听起来并不像其他答案所说的那么简单。取决于您感兴趣的软件，我可能会更新我的答案。