在我的工作中，我必须将一些随机的点包围在边界中。凸包占用了额外的空间，并且不是最紧的形状，因此我对其进行了修改，以通过以下方式放松边缘:
i)给定点数绘制凸包。
ii)现在，对于不在凸包边界上的每个点，检查是否可以将其添加到边界上(当然，这会更改边界形状)，同时确保没有给定的点位于新的多边形形状之外。 (点在多边形算法中)
iii)如果所有点都位于多边形内，则对其他点重复步骤2。
iv)如果边界上不能再包含任何点，则停止。
现在，问题出在任何样本测试集上，所有点都包含在边界中。我的怀疑是:
i)这是凹壳吗？
ii)与我简单地按逆时针顺序排列给定点并在所有点上绘制和多边形而不是先绘制凸包的方式有什么不同？
iii)对于任意给定数量的点，我是否可以通过它们绘制非自交多边形，以使所有点都位于多边形的边界上？
最佳答案
假设您对2D多面体感兴趣(可以是nD；更容易解释和可视化2D!)，则需要找到一组点的四个Pareto frontiers，这将导致您成为“非主导”船体寻找。为什么选择四个前沿？考虑下面的例子
请注意，您需要四个边界(最大与最大，最小与最大，最小与最小以及最小与最小)来完全定义多面体的边缘。此外，请注意，船体是否凸出取决于您的观点。上面的示例显示的边界不是凸的也不是连续的，因此，多面体也不是凸的也不是连续的。四个帕累托边界的集合包括完整的多面体形状。
如果您希望自己实现这一点，那还不错，只需将每个点与每个点进行比较以比较它们的轴并确定哪个点会使两个轴朝着一个有利的方向前进。这称为成对比较。
对于已经使用C++编码的解决方案，这应该是开始https://github.com/kevinduh/pareto的好地方
关于c++ - 凹面船体在边界上取多边形的所有点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45181714/