找到从矩形到点数组的最近点

Question

我有一个矩形和点 (pts) 数组。点可以在矩形内，也可以不在矩形内。我需要在矩形内找到一些点 P(x, y) 到 P 之间的最大距离，并且来自 pts 的每个点将是最小的。

换句话说，对于矩形内的所有 space，我需要选择函数 Dist 的值最小的一个点。

float Dist(Vector2 p, Vector2[] pts)
{
  float d = float.MinValue;
  foreach (Vector2 point in pts)
  {
    float dx = point.x - p.x;
    float dy = point.y - p.y;
    d = Math.Max(d, Math.Sqrt(dx * dx + dy * dy));
  }
  
  return d;
}

Answer 1

移除位于矩形内的点 P 的约束会将其变成 the smallest circle problem，它具有线性最坏情况解和简单的随机预期线性时间解。你的问题也可以化为最小圆问题，线性时间内解决。

对于矩形左侧垂直边 l 左侧的每个点 A，考虑其相对于 l 的镜像 A'。如果圆心在矩形内部的圆包含点 A，则它也必须包含 A'。让我们为左侧的左侧、右侧的右侧、上侧的上方和下侧的下方的每个点构造相应的镜像，并将它们添加到集合中。对于“角”点，如图中的 B 点，我们还添加了它们镜像的镜像（B''' 点必须也在包含 B 的任何圆中）。请注意在构造的集合中，每个点如何位于矩形的水平边界之间，或者在矩形的水平边之一上具有镜像。垂直边也是如此。事实证明，所得到的点集的最小外接圆的中心始终位于矩形内。

确实，考虑最小外接圆的水平直径。必须至少有一个点位于圆的封闭（即包括端点）上半部分，否则圆半径可能会缩小。但是矩形的上边界不允许严格位于直径以下，否则我们的点穿过水平线的镜像将结束在圆之外。以此类推，矩形的下边界不能在直径之上，左边界不能在垂直直径的右边，右边界不能在垂直直径的左边。这意味着圆心在矩形内部，Q.E.D。

Vector2 Center(Rectangle rectangle, Vector2[] pts) {
    extended_pts = []
    foreach (Vector2 point in pts) {
        extended_pts.append(point)
        if (point.x < rectangle.x_min) {
            extended_pts.append((2*rectangle.x_min - point.x, point.y));
            if (point.y < rectangle.y_min)
                extended_pts.append((2*rectangle.x_min - point.x, 2*rectangle.y_min - point.y));
            if (point.y > rectangle.y_max)
                extended_pts.append((2*rectangle.x_min - point.x, 2*rectangle.y_max - point.y));
        }
        if (point.x > rectangle.x_max)
            extended_pts.append((2*rectangle.x_max - point.x, point.y));
            if (point.y < rectangle.y_min)
                extended_pts.append((2*rectangle.x_max - point.x, 2*rectangle.y_min - point.y));
            if (point.y > rectangle.y_max)
                extended_pts.append((2*rectangle.x_max - point.x,  2*rectangle.y_max - point.y));
        if (point.y < rectangle.y_min)
            extended_pts.append((point.x, 2*rectangle.y_min - point.y));
        if (point.y > rectangle.y_max)
            extended_pts.append((point.x, 2*rectangle.y_max - point.y));
        }
    return SmallestCircleCenter(extended_pts);
}

找到从矩形到点数组的最近点

Find nearest point from a rectangle to array of points

math

geometry