将凸壳分成两个独立的部分

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 

添加： 使用旋转卡尺链接查找最远的点对

补充2：如何用中垂线分割点云：

中点：M = (A + B)/2
(MX = (AX + BX)/2, MY = (AY + BY)/2 )

AB向量：（BX-AX，BY-AY）

中垂线有一般方程：

(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 时，您将获得线左侧点的正值，线右侧点的负值（线上点的值为零）