7

我正在尝试为我解决一个相当困难的问题。我对编程并不陌生，但我真的不知道如何解决这个问题。它给出了一组点 (point [])，其中 Xi 和 Yi 坐标作为输入。程序必须输出多边形凸包的周长，但如果有必要，它可以将凸包分成两部分，两个独立的凸包，每个凸包都包含许多点。此划分的目标是具有更短的周长（如果这两个外壳的周长之和小于一个外壳的周长；例如：两个远离彼此的点簇）。问题还在于不能超过两个船体。我会很感激任何想法。

这个问题有一个简单的说明（可能还有很多点）。在这里，您可以看到两个分开的船体的周长比一个船体的周长短。 在此处输入图像描述

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

2 回答 2

4

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

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

于 2013-11-01T03:28:44.367 回答
1

我同意 MBo 的观点，诀窍是找到一个宽间距来切割两个船体。但我不同意旋转卡尺是正确的方法。你关心的不是外在的维度，而是内在的维度。如果您有一组非常宽的点，它们被组织成两条平行的水平线，那么您希望在两条线之间进行切割，而不是每条线的一半。

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

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

于 2013-11-15T12:54:08.983 回答