algorithm - 将凸包分成两个独立的部分

Question

我正在尝试为我解决一个相当困难的问题。我不是编程新手，但我真的不知道如何解决这个问题。它以 Xi 和 Yi 坐标为一组点 (point []) 作为输入。该程序必须输出多边形凸包的周长，但如果有必要，它可以将凸包分成两部分，两个独立的凸包，每个凸包将包含多个点。这种划分的目标是使周长更短(如果这两个船体的周长之和小于一个船体的周长；例如:两个彼此远离的点簇)。问题还在于不能有两个以上的船体。如果有任何想法，我将不胜感激。

这个问题有一个简单的说明(可能有更多的点)。在这里您可以看到两个分离的船体的周长比一个的周长短。

ADD:实际上，“周长”是指周长。

这是我的代码的关键部分:

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];
    }

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 

已添加: finding the farthest pair of points with rotating calipers link

新增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 时，你会得到左边的点为正值，左边的点为负值线的右侧(线上点的值为零)