Эффективный способ Matlab сокращения 2D сегментов?

Question

Мне нужно написать функцию, чтобы упростить набор сегментов. В частности:

С учетом набора 2D-сегментов (координаты x и y)

• Сохранять только одну реплику в случае перекрывающихся (или почти перекрывающихся) сегментов
• Для каждой сохраняемой части храните счет того, сколько на ней присутствовало перекрытий.

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

Пример ввода показан на этом графике Matlab

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

Я не эксперт, работающий с сегментами и геометрическими проблемами. Что было бы наиболее эффективным способом решения такой проблемы? Я использую Matlab, но поможет пример кода на любом языке высокого уровня. Спасибо!

РЕДАКТИРОВАТЬ В соответствии с запросом здесь также приведен пример набора данных, вы можете получить его по этой ссылке Google Drive https://drive.google.com/open?id=1r2hkG7gI0qhzfP-Mmn8HzIil1o47Z2nA

Вход CSV с 276 кабель Сегменты Выходные данные представляют собой CSV с 58 сегментами кабеля (сокращенные сегменты) + дополнительный столбец, содержащий количество оставшихся перекрывающихся кабелей для каждого сегмента.

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

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

Answer 1

Matlab, вероятно, не самый подходящий язык для геометрических манипуляций. PostgreSQL / PostGIS был бы лучшим инструментом, но если у вас нет выбора, вот одно из решений для получения скелета строки:

% Random points
P = [0 0; 
1 1; 
2 1; 
1.01 1.02; 
0.01 0.01];
% positive buffer followed by a negative buffer   
pol = polybuffer(polybuffer(P,'lines',0.25,'JointType','miter'),-0.249,'JointType','miter');
plot(P(:,1),P(:,2),'r.','MarkerSize',10)
hold on
plot(pol)
axis equal
% Drop the duplicate with uniquetol (with a tolerance of 0.005) to get the centerline
utol = uniquetol(pol.Vertices,0.005,'ByRows',true) 
hold off; 
plot(utol(:,1),utol(:,2),'b')

Результат:

И центральная линия: