凸包的划分成两个独立的部分

Question

我正在尝试解决一个对我来说相当困难的问题。我不是编程新手，但我真的不知道如何解决这个问题。输入一组带有Xi和Yi坐标的点（点[]），程序必须输出多边形凸包的周长，但如果必要，它可以将凸包分成两部分，两个单独的凸包，每个凸包都包含若干点。这种划分的目的是为了使周长更短（如果这两个凸包的周长之和比一个凸包的周长更短；例如：两个远离彼此的点簇）。问题还在于不能有超过两个的凸包。我会感激任何想法。

这里有一个简单的问题说明（可能会有更多的点）。在这里，您可以看到两个分离的凸包的周长比一个凸包的周长更短。 补充：实际上，“周长”指的是周长。

以下是我的代码的关键部分：

m.x = (a.x + b.x)/2;
    m.y = (a.y + b.y)/2;

    ab.first = b.x - a.x;
    ab.second = b.y - a.y;

    for (i=0; i<n; ++i)
    {
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 > 0)
            left[l++]=p[i];
        else if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 < 0)
            right[r++]=p[i];
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 == 0)
            mid[md++]=p[i];
    }

- user2943215

---

是的，我很抱歉没有表达清楚。程序必须输出凸包的周长，就这样。但是如果可以创建两个凸包，并且两个凸包的周长之和小于一个凸包的周长，则输出这些凸包的周长之和。 - user2943215

听起来很合理。您介意编辑一下问题，使这一点更加清晰明了吗？ - Dennis Meng

我认为你的意思是使用 hull1 + hull2 < big hull？ - sdasdadas

此外，我认为不可能找到一种分割方式，使得两个凸壳的周长小于大凸壳。这可能可以在几行数学证明。 - sdasdadas

@sdasdadas - <===> 可以分成 < 和 >，这表明断开两个最大的非相邻边可能会起作用。 - andrew cooke

Answer 1

当存在两个（或更多）长期分离的集群时，使用两个船体似乎会有益处。因此，我建议尝试一种简单的方法（可能是近似的）：

construct convex hull
find the farthest pair of points (A, B) in hull with rotating calipers
divide all the points with middle perpendicular to AB segment
find hulls of resulted clouds and calculate profit or loss 

新增: 旋转卡壳算法求解最远点对问题链接

新增2: 如何通过中垂线将点云分割成两部分:

中点: M = (A + B)/2
(M.X = (A.X + B.X)/2, M.Y = (A.Y + B.Y)/2 )

AB向量: (B.X-A.X, B.Y-A.Y)

中垂线的一般式方程：

(y-M.Y) / AB.X = - (x-M.X) / AB.Y
(y-M.Y) * AB.Y + (x-M.X) * AB.X = 0
//incorrect  x * AB.X + y * AB.Y - (AB.Y^2 + AB.X^2)/2 = 0
x * AB.X + y * AB.Y - (B.Y^2 - A.Y^2 + B.X^2 - A.X^2)/2 = 0

当你在最后一个方程中使用P [i] .X和P [i] .Y代替x和y来表示每个点时，对于在直线左侧的点将得到正值，对于在直线右侧的点将得到负值（直线上的点值为零）

- MBo

---

嗨，我又回到这个问题上了，因为最近几天时间不多。现在我已经构建了凸包并计算出周长。我正在计算直径的过程中，但你能给我一些关于如何用中垂线分割点的想法吗？（我不知道这是否重要，但我是用C++编程的。） - user2943215

我还有一个问题。在计算“中点M =（A + B）/ 2 AB向量（B.X-A.X，B.Y-A.Y）”时，（A + B）/ 2乘以向量（B.X-A.X，B.Y-A.Y）吗？抱歉，我不太了解向量，最近只在C语言中编程。 - user2943215

不，它没有被乘。只是引用。 - MBo

我理解你的建议，认为你的答案是正确的。但是我在C++方面并不那么熟练，因此我不知道如何实现旋转卡壳和正确使用向量。如果你能够做到这一点并在这里发布，我会非常高兴。我上传了我目前编写的代码。 - user2943215

最后一个问题，我保证！为什么它必须是AB向量，而不仅仅是点M？这为什么很重要？ - user2943215

Answer 2

我同意MBo的观点，关键是要找到一个广泛的间隔来切割两个船体。但我不认为旋转卡尺是正确的方法。你关心的不是外部尺寸，而是内部尺寸。如果你有一组非常宽的点，这些点被组织成两条平行的水平线，你想在两条线之间切割，而不是在每条线的中间切割。

基本上，我认为你想找到一个“厚”的分离线，将点集分成两个部分，并且与两侧的点尽可能远离。这被称为“最远超平面问题”，通常用于支持向量机算法的无监督变体。

这是一个困难的（NP-hard）问题，但有近似算法。基本思想是取许多潜在的角度来画线，并找出在该角度下放置线以最大化其分离的位置。

- Sneftel