凹壳取多边形边界上的所有点

Question

在我的工作中，我需要将一些随机的点围成一个边界。凸包占用了额外的空间并且不是最紧密的形状，所以我对它进行了修改，以以下方式放松边缘：

i）为给定数量的点绘制凸包。

ii）现在对于凸包边界上不的每个点，检查它是否可以添加到边界（当然这会改变边界形状），同时确保没有任何给定点位于新多边形形状的外部。（点在多边形算法）

iii）如果所有点都在多边形内，请为其他点重复步骤2。

iv）如果不能再将点包含在边界上，请停止。

现在的问题是，在任何样本测试集中，所有点都被包括在边界内。我的疑问是：

i）这是一个凹壳吗？

ii）这与我是否只需按逆时针顺序排列给定点并通过它们绘制多边形有何不同？

iii）对于任何给定数量的点，是否可以绘制一个非自交多边形，使得所有点都位于多边形的边界上？

- Mojo Jojo

---

也许扫描线算法可以帮助解决问题。 - Scheff's Cat

我不会称之为“凹面的”。我认为这被称为“非相交”或“不自相交”。 - Scheff's Cat

请问您能否分享获取“我实际得到的”结果图像的源代码？我们期望得到与“我实际得到的”图像相同的结果。谢谢。 - Banng

Answer 1

假设您对2D多面体感兴趣（它可以是n-D；只是更容易解释和可视化2D！），您需要找到一组点的四个Pareto frontiers，这将导致您正在寻找的“非支配”外壳。为什么是四个边界？请考虑下面的例子。

请注意，你需要四个边界（最大值与最大值、最小值与最大值、最大值与最小值和最小值与最小值）来完全定义多面体的边缘。此外，请注意，外壳是否凸取决于你的点。上面的示例显示了一个不凸且不连续的边界，因此，该多面体也不是凸面体也不是连续的。四个帕累托边界的集合构成了完整的多面体形状。

如果你想自己实现这个功能，那么就需要将每个点与每个点进行比较，比较它们的轴并确定哪个点在有利的方向上推进了两个轴。这被称为成对比较。

对于已经编码的C++解决方案，这应该是一个很好的起点 https://github.com/kevinduh/pareto。

- Manuel J. Diaz