根据坐标确定矩形的算法

Question

我有由绘制的矩形（自由式）组成的用户输入。现在这个绘制的图形并不完美，所以我想根据算法重新绘制它们的形状。

我有一堆来自用户绘图的坐标。我想找到最大的 (x,y) 和最小的 (x,y) 坐标，并使用它们之间的距离来确定矩形的对角线。

但我很难确定最大 (x,y) 坐标和最小 (x,y) 坐标。

例如，我不能将最大的 y 与最大的 x 或最大的 x 与最大的 y 一起使用，因为也许用户只是在他们的行中意外地突出了。 （这有意义吗？）

假设下面是用户绘制的线..如果我使用最大的 y 和最大的 x，我将不会得到所需的坐标（因为它会在意外突出的地方找到坐标）

                       ----
                      /    \
                 ----/      \--------                 -----        --
  --------------/                    \---------------/     \------/  \--

希望你理解 我想表达

的另一种方式是，我想要最接近 (0,0) 的坐标，如果我的画布是 1000 x 1000，我希望第二个坐标最接近 (1000 ，1000）。 （两个极端坐标）

任何人都可以帮助解决这个算法吗？

提前致谢！

Answer 1

根据您希望算法生成的矩形适应用户输入的程度，您可以尝试以下操作：

1. 对所有 x 和 y 坐标求平均值，得到矩形的中心 (Xc, Yc)。
2. 找到最高和最低的 x 值，用最高值减去最低值，然后除以二。对 y 值重复此操作。我们将这些称为 X 和 Y（s 代表“侧面”）。
3. 重要的角点（左上角和右下角）将变为 (Xc - Xs, Yc - Ys) 和 (Xc + Xs, Yc + Ys)。
4. 适当地画线。

现在，这将为您提供一个边界框，其中包含所有用户给定的点。如果您正在寻找更多的最佳拟合类型算法，请将第二步中的 (max - min) / 2 函数替换为平均函数。一个简单的方法可能涉及仅对中心点一侧的点（上方/下方或左/右）进行平均，并将它们用作距中心的偏移量。请注意，这将为您提供四个偏移量，但在任何给定时间您只会使用其中两个。

这里提出的粗略想法可以根据您期望的用户输入类型（例如，您期望它可能有多扭曲）进行调整。假设您能够通过点本身或用户输入方法来区分边（例如，使用离散操作而不是一次绘制矩形的每条边），可以使用线性回归线进行进一步的改进。

希望这个简单的例子能为您指明正确的方向。

Answer 2

如果你想找到距离(0,0)最近的点，那就找到它吧！

point FindClosestToOrigin(point[] P)
{
  point closest = P[0];
  foreach(point p in P)
  {
      if (DistanceOriginS(p) < DistanceOriginS(closest)) closest = p;
  }
  return closest;
}
float DistanceOriginS(point p)
{
   return p.x*p.x + p.y*p.y;
}

您可以轻松修改算法以找到最接近屏幕边缘其余部分的点。

Answer 3

只需对所有点进行平均并将其用作矩形边的位置..当然，这假设您能够区分矩形的四个边，否则您可以尝试一种将坐标分成 4 个边的方法（通过检查具有一定阈值的水平和垂直变化），然后计算每条边的平均值并调整它以链接边。