从坐标确定矩形的算法

Question

我有一个由绘制的矩形(自由式)组成的用户输入。现在这个画出来的图形还不够完美，所以我想根据算法重新给他们画出形状。

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

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

例如，我不能将最大的 y 与最大的 x 或最大的 x 与最大的 y 结合起来，因为用户可能只是在他们的行中意外地突出了。 (这有意义吗？)

假装下面是一条用户画的线..如果我用最大的 y 和最大的 x，我就不会得到想要的坐标(因为它会在意外突出的地方找到坐标)

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

希望你明白我的意思..

我猜另一种表达方式是，我希望坐标最接近 (0,0)，如果我的 Canvas 是 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 函数替换为平均函数。一个简单的可能涉及仅对中心点的一侧(上方/下方或左侧/右侧)的点进行平均，并将它们用作距中心的偏移量。请注意，这将为您提供四个偏移量，在任何给定时间您只会使用其中两个。

这里提出的粗略想法可以根据您期望的用户输入类型(例如，您期望的失真程度)进行调整以适应口味。假设您能够通过点本身或用户输入方法(例如，使用离散操作而不是一次绘制矩形的每一侧)来区分边，则可以使用线性回归线进行进一步改进。

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