Connecting random points in MATLAB without intersecting lines

Question

I need help with solving this problem. I have randomly generated points (example on Picture #1) and I want to connect them with lines (example on Picture #2). Lines can't be intersected and after connection, the connected points should look like an irregular area.

%Generating random points
xn = randi([3 7],1,10);
yn = randi([3 6],1,10);

%Generated points
xn = [6,3,7,7,6,6,6,4,6,3];
yn = [5,3,4,3,3,6,5,4,6,3];

Picture #1:

Result should be like this: Picture #2:

Any idea how to solve this?

Answer 1

I suppose for the general case it can be very difficult to come up with a solution. But, assuming your points are scattered "nicely" there is quite a simple solution.

If you sort your points according to the angle above the x axis of the vector connecting the point and the center of the point cloud then:

P = [xn;yn]; %// group the points as columns in a matrix
c = mean(P,2); %// center point relative to which you compute the angles
d = bsxfun(@minus, P, c ); %// vectors connecting the central point and the dots
th = atan2(d(2,:),d(1,:)); %// angle above x axis
[st si] = sort(th); 
sP = P(:,si); %// sorting the points

And that's about it. To plot the result:

sP = [sP sP(:,1)]; %// add the first point again to close the polygon
figure;plot( sP(1,:), sP(2,:), 'x-');axis([0 10 0 10]);

This algorithm will fail if several points has the same angle w.r.t the center of the point cloud.

An example with 20 random points:

P = rand(2,50);

Answer 2

You could adapt the code from another answer I gave for generating random simple polygons of an arbitrary number of sides. The difference here is you already have your set of points chosen and thus implicitly the number of sides you want (i.e. the same as the number of unique points). Here's what the code would look like:

xn = [6,3,7,7,6,6,6,4,6,3];  % Sample x points
yn = [5,3,4,3,3,6,5,4,6,3];  % Sample y points
[~, index] = unique([xn.' yn.'], 'rows', 'stable');  % Get the unique pairs of points
x = xn(index).';
y = yn(index).';
numSides = numel(index);
dt = DelaunayTri(x, y);
boundaryEdges = freeBoundary(dt);
numEdges = size(boundaryEdges, 1);

while numEdges ~= numSides
    if numEdges > numSides
        triIndex = vertexAttachments(dt, boundaryEdges(:,1));
        triIndex = triIndex(randperm(numel(triIndex)));
        keep = (cellfun('size', triIndex, 2) ~= 1);
    end
    if (numEdges < numSides) || all(keep)
        triIndex = edgeAttachments(dt, boundaryEdges);
        triIndex = triIndex(randperm(numel(triIndex)));
        triPoints = dt([triIndex{:}], :);
        keep = all(ismember(triPoints, boundaryEdges(:,1)), 2);
    end
    if all(keep)
        warning('Couldn''t achieve desired number of sides!');
        break
    end
    triPoints = dt.Triangulation;
    triPoints(triIndex{find(~keep, 1)}, :) = [];
    dt = TriRep(triPoints, x, y);
    boundaryEdges = freeBoundary(dt);
    numEdges = size(boundaryEdges, 1);
end

boundaryEdges = [boundaryEdges(:,1); boundaryEdges(1,1)];
x = dt.X(boundaryEdges, 1);
y = dt.X(boundaryEdges, 2);

And here's the resulting polygon:

patch(x,y,'w');
hold on;
plot(x,y,'r*');
axis([0 10 0 10]);

Two things to note:

• Some sets of points (like the ones you chose here) will not have a unique solution. Notice how my code connected the top 4 points in a slightly different way than you did.
• I made use of the TriRep and DelaunayTri classes, both of which may be removed in future MATLAB releases in favor of the delaunayTriangulation class.