Алгоритм для наилучшего соответствия прямоугольника

Question

Я ищу алгоритм, который лучше всего подходит для произвольного прямоугольника для неупорядоченного множества точек. В частности, я ищу прямоугольник, где сумма расстояний точек до любого из краев прямоугольника минимизирована. Я нашел множество оптимальных алгоритмов линий, окружности и эллипса, но ни один из них для прямоугольника. В идеале, мне бы хотелось что-то на C, C++ или Java, но на самом деле это не было так суетливо.

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

Answer 1

Вот некоторые идеи, которые могут вам помочь.

Мы можем оценить, если точка находится на краю или на углу следующим образом:

1. Собирают Пункта п neares соседи
2. Посчитать медиан
3. Расчет точек точек матрицы ковариации следующим образом:
   1. Начать с Covariance = ((0, 0), (0, 0))
   2. Для каждой точки вычислить d = point - centroid
   3. Covariance += outer_product(d, d)
4. Рассчитать собственные значения ковариации. (Например, с СВД)
5. Классифицировать точка:
   • если одно собственное значение велико, а другой очень мало, мы, вероятно, на краю
   • в противном случае мы должны быть на углу

Извлеките все угловые точки и выполните сегментацию. Выберите четыре сегмента с большинством записей. Центроид этих сегментов является кандидатом на углы прямоугольника.

Рассчитать нормированные векторы направления двух противоположных сторон и рассчитать их среднее значение. Вычислите среднее значение двух других противоположных сторон. Это векторы направления параллелограмма. Если вы хотите прямоугольник, вычислите перпендикулярный вектор к одному из этих направлений и вычислите среднее значение с другим вектором направления. Тогда направление прямоугольника является средним вектором и перпендикулярным вектором.

Чтобы рассчитать углы, вы можете проецировать кандидатов по их направлениям и перемещать их так, чтобы они образовывали углы прямоугольника.

Answer 2

Вот общая идея. Создайте сетку с маленькими ячейками; рассчитать оптимальную линию для каждой не слишком пустой ячейки (вычисление немедленно , поиск не производится). Соедините смежные ячейки, убедившись, что стандартное отклонение улучшается/не ухудшается. Таким образом, мы обнаруживаем четыре стороны и четыре угла и разделяем наши точки на четыре группы, каждая из которых принадлежит к одной из четырех сторон.

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

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

---

Для линии Y = a*X+b, минимизировать сумму квадратов перпендикулярных расстояний точек {х _я, у _я} к этой строке. Это прямо разрешимо для a и b. Для более вертикальных линий переверните Xs и Ys.

P.S. Я интерпретирую проблему как минимизацию суммы квадратов перпендикулярных расстояний каждой точки до ее ближайшей стороны прямоугольника, а не всех сторон прямоугольника.

Answer 3

Идея линии наилучшего соответствия заключается в вычислении вертикальных расстояний между вашими точками и прямой y = ax + b. Затем вы можете использовать исчисление, чтобы найти значения a и b, которые минимизируют сумму квадратов расстояний. Вычисление причины выбирается по абсолютной величине, потому что первая дифференцируема на 0.

Если вы попытались бы использовать тот же подход с прямоугольником, вы столкнулись бы с проблемой, что квадрат расстояния в сторону прямоугольник - кусочно определенная функция с 8 различными частями и не является дифференцируемой, когда куски встречаются внутри прямоугольника.

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

Answer 4

Я не совсем уверен, но вы можете поиграть с первыми 2 (3?) Размерами по сравнению с PCA из своих точек. он будет работать достаточно быстро для большинства случаев.