Есть ли возможность сгруппировать совпадающие линии для оценки «плотности» линий?

Question

Цель

Начиная с линейного супа со многими вышележащими линиями. Сгруппируйте эти совпадающие строки и суммируйте количество строк. Разделите эту сумму на наибольшую сумму в сборке, чтобы получить относительную сумму. Используйте это относительное количество в качестве измерения для плотности линии.

Состояние работы

Одна возможность, которая приходит мне в голову, - это создать класс "Line" (или используйте shapely LineString), чтобы вычислить расстояние между парами линий. В совпадающем случае P_1 и P_2 line_i находятся на line_j. Для применения потребуется небольшой допуск для совпадения. В этом подходе грубой силы нужно сделать много циклов, которые могут вызвать проблемы с производительностью (я полагаю) для больших сборок. Целевой диапазон номеров линий составляет 50 000 - 150 000.

Проблема

В настоящее время отсутствует умный подход для выполнения этой задачи, либо

• Определите совпадающие пары линий
• И создайте интеллектуальную структуру, содержащую эту информацию, чтобы сократить количество линий до наиболее значимых с измеренным значением плотности

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

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

Ниже приведен пример сегмента процесса. У меня есть приблизительный многоугольник, представленный несколькими линиями. Я хочу получить только самые «важные», чтобы перестроить «самый важный» многоугольник из него. На рисунке видно, что l6 и l7 присутствуют только один раз, поэтому l8 / l2 являются предпочтительными.

Answer 1

Представляет линии, используя уравнение тхота.

dx = x2 - x1  
dy = y2 - y1
L = Sqrt(dx*dx+dy*dy)
Dis = dx*y1 - dy*x1
SD = Sign(Dis)
rho = SD * Dis / L   // always poitive
theta = atan2(-SD*dx, SD*dy)  

Заполнить 2D-таблицу, содержащую некоторый дискретный набор углов и таких как Hough Transform аккумулятор.

Например, сделайте шаг угла 1 °, чтобы 360 строк и несколько сотен столбцов соответствовали разумному диапазону. Для каждого значения приращения строки A[theta][rho] с использованием округления до ближайших целочисленных индексов.

Затем проверьте, какая ячейка имеет наибольшее количество голосов - в описывается набор закрытых строк.

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