function roads = UR_gen_roads_rand(n,min_dist,max_x)
% UR_gen_roads_rand - generate random road network
% On input:
%     n (int): number of vertexes
%     min_dist (float): minimum distance between two vertexes
%     max_x (float): maximum x or y value (min is 0)
% On output:
%     roads (road struct): describes roads
%       .vertexes (nx2 array): 2D vertexes of roads
%       .edges (kx2 array): edges (as road vertex pairs)
% Call:
%     roads = UR_gen_roads_rand(20,2.5);
% Author:
%     T. Henderson
%     UU
%     Fall 2019
%

min_pt_dist = 10;

x = max_x*rand(n,1);
y = max_x*rand(n,1);
num_pts = n;
done = 0;
while done==0
    p1 = 0;
    found = 0;
    while p1<num_pts&found==0
        p1 = p1 + 1;
        p2 = p1 + 1;
        while p2<num_pts&found==0
            p2 = p2 + 1;
            if norm([x(p1),y(p1)]-[x(p2),y(p2)])<min_pt_dist
                found = 1;
            end
        end
    end
    if found==1
        x = [x(1:p1-1);x(p1+1:num_pts)];
        y = [y(1:p1-1);y(p1+1:num_pts)];
        num_pts = num_pts - 1;
    else
        done = 1;
    end
end
n = num_pts;

tri = delaunay(x,y);
nei = zeros(n,n);
dists = zeros(n,n);
num_tri = length(tri(:,1));
for t = 1:num_tri
    nei(tri(t,1),tri(t,2)) = 1;
    nei(tri(t,2),tri(t,3)) = 1;
    nei(tri(t,1),tri(t,3)) = 1;
    nei(tri(t,2),tri(t,1)) = 1;
    nei(tri(t,3),tri(t,2)) = 1;
    nei(tri(t,3),tri(t,1)) = 1;
end
edges = [];
for n1 = 1:n-1
    for n2 = n1+1:n
        if nei(n1,n2)==1&norm([x(n1),y(n1)]-[x(n2),y(n2)])>min_dist
            edges = [edges; n1,n2];
        end
        dists(n1,n2) = norm([x(n1),y(n1)]-[x(n2),y(n2)]);
    end
end
vertexes = [x,y,zeros(n,1)];
roads.vertexes = vertexes;
roads.edges = edges;

tch = 0;
