Построить линии из нескольких точек 2D и измерить расстояние между этими линиями

Question

Несколько точек на 2D плоскости. Они представляют собой оконную раму преимущественно прямоугольной формы с некоторыми возможными вариациями. Точки, являющиеся частью каждой стороны, не обязательно образуют идеальную линию. Каждая сторона окна должна быть измерена.

Вращающееся электронное устройство, прикрепленное к окну, измеряет расстояние во всех направлениях, обеспечивая измерения на 360 градусов. Используя угол поворота и расстояние, набор точек наносится на 2D-систему координат. Пока все хорошо.

Теперь самое сложное. Измеренная оконная рама может иметь некоторые вариации. Точки должны быть преобразованы в прямые линии, и длина каждой линии должна быть измерена.

Я предполагаю, что необходимы следующие шаги:

1. Сгруппируйте разные точки в прямые линии. Это означает аппроксимацию каждой линии «между» образующими ее точками.
2. Рисование этих линий, избавление от отдельных точек, используемых для построения линий.
3. Найдите точки, где пересекаются каждые две линии.
4. Измерьте расстояние между этими точками. Однако не все расстояния между всеми точками интересны. Например, диагонали в кадре не имеют значения.

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

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

---

Новое изображение

Answer 1

Я бы решил это в 2 этапа:

• Очистка данных: округлить местоположение (X, Y) каждой точки до ближайшего кратного N (варьируйте N для разных степеней точности)
• Применение алгоритма упаковки подарков (также известного как март Джарвиса)
• Теперь у вас есть только те точки, которые не коллинеарны, и линии между ними, а также порядок, в котором их необходимо пройти, чтобы сформировать периметр.
• Переберите точки по порядку, возьмите точки Px и P (x + 1) и вычислите расстояние между ними.