-1

如果主题令人困惑，我很抱歉。这是因为我不知道我真正在寻找什么。我有一组 P 点 ( |P| < 10^5)。每个点都有整数坐标 ( between -10^4, 10^4) 如何找到直线，它穿过输入指定的所有点。条件是该线必须是最粗的，并且您必须输出该直线的粗度，精确到小数点后 2 位。任何提示、线索、想法或算法名称将不胜感激。

PS。这既不是作业也不是 SPOJ。我只是通过做上一版的问题来准备编程比赛。而那个我无法解决的问题，即使我不知道从哪里开始寻找解决方案......

4

2 回答 2

1

您可以从确定该点云的凸包开始（参见例如http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm），并尝试找到以最短距离限制该多边形的两条平行线。

我认为这应该是一个更简单的问题，因为它允许您将平行线的方向基于凸包的段（其中数量有限）。

一种实现方式可以是依次处理凸包的每个部分。每段，画一条穿过它的线（这是两条平行线之一），然后确定包围凸包的最近的另一条平行线。对凸包的每个部分执行此操作，同时记录到目前为止您在平行线之间找到的最小距离。最后，您应该获得最佳结果。

显然，这仍然需要一种有效的方法来确定最近的另一条平行线。这样做的一种（天真，但可能足够好）的方法是获取不在当前段上的凸包的所有顶点，并确定通过它的线的垂直距离（例如http://en.wikipedia .org/wiki/Distance_from_a_point_to_a_line）。所有这些顶点的最大距离也是到平行线的最小距离。

在伪代码中：

Function FindThinnestLine(PointCloud P)
   CH = ConvexHull(P)

   optS = nothing
   optDist = infinite

   For each segment S in CH
      L = the line through S

      /* Find the minimum distance that the line parallel to L must have in order to enclose CH */
      maxDist = 0
      For each vertex P in CH, except the two that limit S
         dist = The distance between L and P
         maxDist = max(dist, maxDist)

      /* If the current S has a smaller maxDist, it is our new optimum */
      if(maxDist < optDist)
         optS = S
         optDist = maxDist

   Return the line through optS and the line parallel to optS at a distance of optDist as the result
End Function

这是一个 O(n^2) 算法，其中 n 是凸包中的段数。

编辑 想想看，你不需要为每个 S 迭代凸包的 O(n) 个顶点（为了找到 maxDist），只需要第一个S。假设我们称之为第一个顶点 oppV （opp与 S 相反），假设我们按顺时针顺序处理凸包的段。对于我们处理的每个后续 S，新的 oppV 可以是相同的顶点，也可以是其右邻居之一（但绝不是左邻居，否则这些段不会形成凸多边形）。
因此，处理凸包的片段可以在 O(n) 中完成（但创建凸包仍然是 O(n log n)）。

于 2012-11-16T10:06:44.890 回答
0

包含 P 的给定子集的所有点的最粗线应该是线段 的垂直平分线xy，其中x和y是子集的两个点，highest distance d它们之间有 。这条线的粗细也是如此d。

于 2012-11-16T10:03:27.663 回答