Разбиение набора точек на подмножества на основе сегментов линии

Question

У меня есть набор точек и набор отрезков. Я хотел бы разбить набор точек на подмножества или кластеры на основе этих сегментов. В конечном итоге я смотрю на выпуклый корпус для каждого подмножества (оранжевый многоугольник, показанный на рисунке справа). Хотя сегменты линии в приведенном ниже примере связаны друг с другом, это не всегда так. Я предполагаю, что метод должен построить выпуклую оболочку из всех точек (оранжевый многоугольник, показанный слева), а затем разбить выпуклую оболочку в точке пересечения с отрезками линии и как-то включить «внутренние» точки в новой выпуклой корпусов (т. е. точек 1,2,3 и 4 в примере ниже).

points = [-0.1325 -2.2267; -0.1525 -2.2267; -0.5319 1.0698; -1.3628 -0.1296; 1.7438 1.3784; 1.5770 0.9458; 0.5147 -2.6114; 0.8169 -2.2797; -1.0244 2.7143; -0.4422 2.8257; -1.7421 -2.4453; -2.4492 -0.4012] 
linesegments = [-1.1258 -4.2270 -0.7196 -3.9662; -0.7196 -3.9662 0.4347 -0.4873; -2.3293 1.4275 -3.3717 2.2654; -2.3293 1.4275 0.4347 -0.4873; 1.3579 3.1700 3.3566 0.5079; 3.3566 0.5079 0.4347 -0.4873] % Each row is line with format [x1 y1 x2 y2]; 

В этом примере есть 12 очков и 6 отрезков. Точки 1 и 2 расположены достаточно близко, но точка 2 немного влево, а точка 1 немного вправо. Выпуклая оболочка каждого подмножества:

ch1 = [9 10 5 6 3 9]; 
ch2 = [12 4 2 11 12]; 
ch3 = [1 8 7 1]; 

Answer 1

Построить линии между каждой парой точек. Найдите пересечение между этими линиями и отрезками (ниже я использовал lineSegmentIntersect). Не учитывайте пары точек, которые пересекают любой из сегментов линии. Построить неориентированный граф из остальных пар точек. Найти connected components на неориентированном графике (ниже я использовал conncomp, который основан на Разложение Dulmage-Mendelsohn). И, наконец, вычислить выпуклую оболочку из точек в каждой компоненте связности.

Эта функция Matlab convhullc(points, linesegments) найдет координаты каждой выпуклой оболочки.

function C = convhullc(pp, ll)  
    np = size(pp,1); % Number of points 

    % Create line between all pairs of points 
    combi = nchoosek(1:np, 2); 
    ppxy = [pp(combi(:,1),:) pp(combi(:,2),:)]; 

    % Intersection between all lines and all line segments 
    intersectpl = lineSegmentIntersect(ppxy, ll) 
    % Pairs of points that do not intersect a line segment 
    nointersect = (sum(intersectpl.intAdjacencyMatrix,2) == 0); 

    % Creating adjacency matrix of points with no intersect 
    adj = sparse(combi(nointersect,1), combi(nointersect,2), 1, np, np); 
    % Create undirected graph 
    adj = adj + adj.'; %' 
    % Find the connected components 
    [nch, bin] = conncomp(adj); 

    % Find the convex hulls 
    ch = cell(nch,1); 
    for i=1:nch 
     if(sum((bin==i)) > 2) 
      ppx = pp((bin==i),1); 
      ppy = pp((bin==i),2); 
      K = convhull(ppx, ppy); 
      ch{i} = [ppx(K) ppy(K)]; 
     end 
    end 
    ch = ch(~cellfun('isempty',ch)); 

    C = ch; 
end 

Answer 2

Начать с любого пункта. Ярлык как A. Итерация над всеми соседями. Если вы можете связаться со соседом, отметьте его как A. Выполните следующую точку с надписью A (если она не находится точно в строке). После того как вы обработали все точки A, эта часть будет завершена. Запустите B в немеченной точке.

Вычислить выпуклые оболочки после этого.