从坐标确定矩形的算法

Question

我有一个用户输入的自由绘制矩形。但是这个图形不完美，所以我想根据算法重新绘制它。

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

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

例如，我不能仅使用最大x和最大y或者最大y和最大x，因为用户可能只是在他们的线条中意外地突出了一点。（明白我的意思吗？）

假设下面是用户绘制的线条。如果我使用最大的y和最大的x，我将无法得到期望的坐标（因为它会找到意外的突出部分的坐标）。

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

希望你能理解我的意思...

我想说的另一种方式是，我希望找到最靠近（0,0）的坐标，如果我的画布大小为1000 x 1000，那么我希望第二个坐标最接近（1000,1000）。 （两个极端坐标）

有人能帮忙这个算法吗？

提前感谢！

- developer

---

这个矩形是否平行于X和Y轴？或者这个矩形可以在二维空间中旋转吗？ - user425445

你知道用户是否从矩形的一个角落开始，先画了一条边吗？我在考虑通过在每条边上拟合一条直线来获取矩形。必须有一种搜索算法来决定哪些点属于哪条边。有很多可能性......嗯 - John Alexiou

@Julian - 不，矩形可以相对于轴以任何方式旋转。 - developer

@Jalexiou - 不，形状可以从任意点开始绘制（不一定是角落），并且以一条连续的线绘制（即不能为形状绘制多条线）。 - developer

Answer 1

根据您希望算法生成的矩形与用户输入匹配的程度，您可以尝试以下方法：

1. 平均所有x和y坐标，以得到矩形的中心点（Xc，Yc）。
2. 找到最高和最低的x值，将最低值从最高值中减去并除以2。 对y值重复此操作。 我们称这些值为Xs和Ys（s代表“边”）。
3. 重要的角落（左上角和右下角）将变为（Xc-Xs，Yc-Ys）和（Xc + Xs，Yc + Ys）。
4. 根据需要绘制线条。

现在，这将为您提供一个边界框，其中包含所有用户给定的点。 如果您正在寻找更适合的算法，则应将步骤二中的（max-min）/ 2函数替换为平均函数。 简单的平均函数可能仅涉及对中心点一侧的点进行平均处理（向上/向下或向左/向右），并将其用作偏移量。 请注意，这将为您提供四个偏移量，但您每次只会使用其中两个。

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

希望这个快速示例能为您指明正确的方向。

- MysteryMoose

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

你可以轻松修改算法，以找到离屏幕其他边缘最近的点。

- DennyRolling

---

啊..我从没想过这个!! 我感觉很蠢。但是不应该是sqr(p.x^2 + p.y^2)吗？（也就是你计算的平方根） - developer

你说得对，那是距离的平方，但是你不需要实际距离来找到最小值。 - DennyRolling

@Julian - 请记住，由于矩形可以旋转且用户可以添加“噪音”，因此不能保证距离0,0最近的点是一个角落！ - user425445

为什么不缓存 DistanceOriginS(closest)，这样你就不必为每个点再次计算它了。 - John Alexiou

Answer 3

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

- Jack

---

我无法区分四个边，因为该形状仅使用一次绘制（只使用一条线来绘制形状）。 - developer