凹面船体在边界上取多边形的所有点

Question

在我的工作中，我必须在边界中包含一些随机点。凸包正在采取额外的空间，并没有严格的形状，所以我修改它放宽以下方式边缘：

ⅰ）画出凸包点为在给定数量。

II）现在对凸包边界检查每个点不如果它可以被添加到（当然，改变边界整形）的边界，同时确保没有任何给定的点在于新的外多边形形状。 （在多边形算法点）

ⅲ）如果所有的点位于多边形重复步骤2对于一些其它点的内部。

iv）如果没有更多的点可以包括在边界上，停止。现在

，这个问题是在任何样品的测试集，越来越包括在边界内的所有点。我的疑惑是：

i）这是一个凹形的船体吗？

II）这怎么不同，如果我只是在安排逆时针顺序给点意见，并通过所有的人，而不是先绘制一个凸包绘制和多边形？

III）这是真的，对点的任何给定的电话号码，我可以通过他们得出一个非自相交多边形，这样所有的点位于多边形的边界？

Answer 1

假设你有兴趣在一个2D多面体（也可以是第二;！它只是更容易解释和可视化2D），你需要找到一组点的四个Pareto frontiers，这会导致您正在寻找的“非主导”船体。为什么四个边界？考虑下面

注意的例子，你需要四个边界（最大值与最大值，最小值与最大值，最大主场迎战分钟，分钟对分）完全定义的多面体的边缘。此外，请注意，船体是否凸出取决于你的观点。上面的例子显示了一个非凸和不连续的边界，因此，多面体不是凸的，也不是连续的。四个帕累托边界的集合包含完整的多面体形状。

如果你正在寻找这个工具自己，这是不是太糟糕，只是要求每个点比较对每个点比较它们的轴，并确定哪些点在有利的方向前进两个轴。这被称为两两比较。

对于C++已经编码的解决方案，这应该是启动https://github.com/kevinduh/pareto