根据线段将一组点拆分为子集

Question

我有一组点和一组线段。我想根据这些线段将点集分成子集或簇。最终，我正在寻找每个子集的凸包（右图中显示的橙色多边形）。尽管下例中的线段相互连接，但情况并非总是如此。我猜测该方法应该从所有点（左侧显示的橙色多边形）构造一个凸包，然后在与线段的交点处分割凸包，并以某种方式将 "inner" 点包含在新的凸包（即下面示例中的点 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

从任意一点开始。标记为 A。遍历所有邻居。如果您可以联系到邻居，也将其标记为 A。继续下一个标记为 A 的点（除非它恰好在一条线上）。处理完所有 A 点后，该部分就完成了。在未标记的点上开始 B。

之后计算凸包。

Answer 2

在每对点之间画线。找到这些线和线段的交点（下面我使用了lineSegmentIntersect). Disregard the pairs of points that intersect any of the line segments. Construct an undirected graph from the remaining pairs of points. Find the connected components in the undirected graph (below I used 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

根据线段将一组点拆分为子集

Splitting a set of points into subsets based on line segments

r

matlab

cluster-analysis

subset