алгоритм определения прямоугольника по координатам

Question

У меня есть пользовательский ввод, который состоит из нарисованного прямоугольника (фристайл).Теперь эта нарисованная фигура не идеальна, поэтому я хотел бы перерисовать форму для них на основе алгоритма.

У меня есть куча координат из чертежа пользователя.Я хотел бы найти самые большие (x, y) и самые низкие (x, y) координаты и использовать расстояние между ними, чтобы определить диагональ прямоугольника.

Но у меня возникают трудности с определением наибольшей(x, y) координата и самая низкая (x, y) координата.

Я не могу взять наибольший y с наибольшим x или наибольший x с наибольшим y, например, потому что, возможно, пользователь простосделал случайный выступ в их линии.(Имеет ли это смысл?)

Притворимся ниже, это нарисованная пользователем линия ... если бы я использовал наибольший у с наибольшим х, у меня не было бы желаемой координаты (потому что он нашел бы координату в случайномВыдвинуться)

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

Надеюсь, вы понимаете, к чему я клоню ..

Полагаю, можно сказать, что мне нужна координата, ближайшая к (0,0)и если бы мой холст был 1000 х 1000, я бы хотел, чтобы вторая координата была ближайшей к (1000, 1000).(две крайние координаты)

Кто-нибудь может помочь с этим алгоритмом?

Заранее спасибо!

Answer 1

В зависимости от того, насколько хорошо вы хотите, чтобы сгенерированный алгоритмом прямоугольник соответствовал пользовательскому вводу, вы можете попробовать следующее:

1. Усредните все координаты x и y, чтобы получить центр прямоугольника (Xc, Yc).
2. Найдите самое высокое и самое низкое значение x, вычтите самое низкое из самого высокого и разделите на два. Повторите для значений у. Давайте назовем эти Xs и Ys (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 стороны ( путем проверки горизонтального и вертикального отклонения с некоторым порогом), а затем вычислите среднее значение для каждой стороны и скорректируйте его для сторон связи.