Установите фиксированный прямоугольник на множество точек

Question

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

Представьте, что у вас есть набор точек, которые не сортированы и не всегда показывают полный корпус прямоугольника. На изображении ниже должна быть показана проблема:

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

Возможно, я мог бы найти линии регрессии сначала, но это швы, чтобы можно было пойти по-другому.

Буду признателен за любые подсказки.

Answer 1

Просто набросок решения:

1. Высота и ширина прямоугольника фиксируется, так что вы можете определить его с тремя параметрами (x0, y0, тета): скажем, нижний левый угол и поворот ,
2. Используйте функции расстояния как pnt2line дано здесь http://www.fundza.com/vectors/point2line/index.html
3. Теперь напишем функцию обертку: для каждой точки, вычислить расстояние от всех четырех краев прямоугольника и назначить distance[i] как минимум этих четырех расстояний
4. использования это distance массив в scipy.optimize.curve_fit, чтобы найти наиболее пригодные параметры

Answer 2

Если есть останцы, RANSAC может быть вашим хорошим другом. Чтобы выполнить подгонку, вам нужно три точки, взятые с разных сторон. Так что просто выберите три случайные точки и предположите, что две из них принадлежат одной стороне, а другая - ортогональной. Поиск параметров позы - это не большая проблема. Вы можете вычислить ошибку установки из функции расстояния, как описано в @VBB (для каждой точки берет кратчайшее расстояние в сторону).

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

Для окончательной установки ярусов вы можете использовать трюк.

• Назначьте каждый мерцаний ближайшей стороной;

• Центр кластера каждой стороны на соответствующем центроиде;

• Поверните кластеры каждой другой стороны на 90 °;

• Это дает единый кластер с одной ориентацией; выполните обычную линию, чтобы получить эту ориентацию.

Answer 3

определить расстояние D (R (Р), Q) между фиксированным размером прямоугольником R (P) в положении P и точка Q, чтобы быть длиной самой короткой прямой линии, соединяющей два. Это очень легко определить в качестве аргумента функции по случаям.

Теперь просто используйте какую-либо форму градиентного спуска, чтобы найти оптимальное значение P * так, чтобы сумма d (R (P *), Q)^2 для Q в вашем точечном множестве была минимизирована.