在我的工作中，我必须在边界中包含一些随机的点组 . 凸形船体占用了额外的空间而且没有最紧凑的形状，所以我修改它以通过以下方式放松边缘：
i）为给定的点数绘制凸包 .
ii）现在对于不在凸包边界上的每个点，检查是否可以将其添加到边界（当然这会改变边界整形），同时确保没有给定的点位于新的多边形形状之外 . （点多边形算法）
iii）如果所有点都位于多边形内部，则重复步骤2以获得其他点 .
iv）如果边界上不能包含更多点，请停止 .
现在，问题在于任何样本测试集，所有点都包含在边界中 . 我的怀疑是：
i）这是一个凹形船体吗？
ii）如果我只是按照逆时针顺序排列给定的点并通过所有这些点绘制多边形而不是先绘制一个凸包，这有什么不同？
iii）对于任何给定数量的点，我是否可以通过它们绘制非自相交多边形，这样所有点都位于多边形的边界上？
1 回答
假设您对2D多面体感兴趣（它可以是n-D;它更容易解释和可视化2D！），您需要找到一组点的四个Pareto frontiers，这将导致您正在寻找的'non-dominated'船体 . 为什么有四个边界？考虑下面的例子
请注意，您需要四个边界（最大与最大，最小与最大，最大与最小，最小与最小）来完全定义多面体的边缘 . 此外，请注意船体是否凸起取决于您的要点 . 上面的例子显示了一个不凸而不连续的边界，因此，多面体不是凸的也不是连续的 . 四个帕累托边界的集合包括完整的多面体形状 .
如果您希望自己实现这一点，那就不是太糟糕了，只需要将每个点与每个点进行比较以比较它们的轴并确定哪个点使两个轴向有利的方向前进 . 这称为成对比较 .
对于C中已经编码的解决方案，这应该是一个很好的起点https://github.com/kevinduh/pareto