在 2d 中，凸包基本上表示为点之旅。似乎这种表示可能会超出二维。因为，我将很快与他们合作，我想提前知道这样做的“标准”是什么，如果有这样做的话，因为船体可能会被其他人使用。
澄清：我所指的标准是关于输出格式的，这样程序就可以从该输出中利用外壳来做其他事情。
问问题
1181 次
1 回答
4
点的集合总是足以完全指定任何船体，但在实践中计算点的连通性通常需要再次运行船体算法。
编辑：如果您需要边缘或面部数据，您可以在 quickhull 等算法中免费获得。我将假设 N 维。基本上，人们不断地寻找由 N 个点定义的平面，以及相关的法向量。如果法向量给定的平面一侧仍有点，则创建由最远点定义的新平面，并删除新平面集错误一侧的任何点。这些平面定义了 (N-1) 个单元（在 3D 中这些是面，在 2D 中这些是边）并在算法中的这一点上给出船体的最高维度表示。该算法继续进行，直到没有平面的点位于错误的一侧。最后的平面给出了最终船体的 (N-1) 个单元，它们的定义点是顶点。http://www.qhull.org/使用了许多策略，其中最明显的是使用 Delaunay 三角剖分（一旦你有了凸包算法，你就有了代码）。
在二维中，您有一个点列表和一些边。如果你愿意，你可以命令他们参观。您需要任何船体的边缘和点。
在 3D 中，您需要点和边，或面和边，或点和面作为最小表示。但有时同时拥有这三个可能是有效的。也许你想用它们构成的边缘来表示面部，也许是点，也许两者兼而有之。这是内存和时间或可访问性之间的权衡。
在更高维度上你也有同样的东西，但有单元格（3D+ 面）以及面、边和点。随着维度的增加，存储单元数据所需的空间可能会变得非常大，因此点和边的集合可能变得可取，您可以在这里看到这种模式的证据：http ://en.wikipedia.org/wiki/Hypercube#元素。
然后，您可以选择如何表示高维单元格，它们参考点、边缘、面、低维单元格、高维单元格。问题是：你跟踪不同维度细胞之间的每一个关系（比如面和边缘之间的关系，但更高维度）？或者这些关系的类型数量将超线性增加，这是一个额外的组合，每种类型的数量关系也将被表示。因此，您是否将其全部扔掉并即时计算。即使是中等规模的问题，对空间和时间的要求也会变得很重要——所以表示的选择实际上取决于你在做什么。
就个人而言，我通常使用一组带有引用它们的边的点。
于 2012-11-24T11:34:09.047 回答