Small Satellites

Home » Posts tagged 'Voronoi Diagram'

Tag Archives: Voronoi Diagram

Voronoi Road Map, Path Planing

clc;close all;clear all;

Input Map

RGB = imread('Map.png');
figure('Position',[100 0 600 700],'color','k');
imagesc(RGB);
axis image
title('Input Map','color','w');
axis off
set(gcf, 'InvertHardCopy', 'off');
hold off;

voron_01

Convert to binary image matrix and inverse matrix values

I = rgb2gray(RGB);
binaryImage = im2bw(RGB, 0.3);
sz  = size(binaryImage);

Inital pose

xs = 225; ys = 355;
% Goal Pose
xg = 50; yg = 50;
% Pose Matrix
pose = zeros(sz(1),sz(2));
pose(ys,xs) = 1;
pose(yg,xg) = 1;

Voronoi Road Map

figure('Position',[100 0 600 700],'color','k');
hold on;
set(gcf, 'InvertHardCopy', 'off');
sk = 1;
for i = 1:sz(1)
    for j = 1:sz(2)
         if(binaryImage(i,j) == 1 )
     xv(sk) = j;
     yv(sk) = i;
     sk = sk+1;
         end
    end
end
[vrx,vry]  = voronoi(xv,yv);
set(gca,'YDir','Reverse');
plot(xv,yv,'y.',vrx,vry,'b-');
axis tight
%axis([1 sz(2) 1 sz(1) ]) ;
axis image
title({'Voronoi Road Map';
'* - Represents Starting and Goal Position '},'color','w');
axis off
spy(pose,'*r');

voron_02

Robot Path

x = xs; y = ys;
indk = 1;
while (abs(x - xg) > 5)||(abs(y - yg)> 5)
path(:,indk) = [x y];
dist = sqrt((vrx - x).^2+(vry - y).^2);
goal = sqrt((xg - x).^2+(xg - y).^2);
% Find closest vertices of the Voronoi edges
[mn ind] = min(dist(:));
xt = vrx(ind);
yt = vry(ind);
goalj = sqrt((xg - xt).^2+(xg - yt).^2);
if (goalj < goal )
x = xt;
y = yt;
vrx(ind) = 1E6;
vry(ind) = 1E6;
indk = indk +1;
else
vrx(ind) = 1E6;
vry(ind) = 1E6;
end
end
path(:,indk) = [xg yg];
plot(path(1,:),path(2,:),'-r');
title({'Voronoi Road Map and Robot Path';
'* - Represents Starting and Goal Position '},'color','w');

voron_03

 

Advertisements

Voronoi diagram of Prime Spiral

Contents

Ulam’s Prime Spiral

To generate a Ulam’s prime spiral the positive integers are arranged in a spiral pathern and prime numbers are highlighted in some way along the spiral. For example we used blue pixels to represent primes and white pixels for composite numbers. The code below uses built in Matlab function to generate the Ulam spiral.

close all;
clc
clear all
sz  = 101; % Size of the NxN square matrix
mat = spiral(sz);
k =1;
for i =1:sz
    for j=1:sz
        if isprime(mat(i,j)) % Check if the number is prime
            % saving indices of primes
            y(k) = i;
            x(k) = j;
            k = k+1;
        end
    end
end
figure('Position',[0 0 800 800]);
hold on;
colormap bone;
scatter(x,y,'.b');
axis([1 sz  1 sz ]);
axis off;
set(gca,'YDir','Reverse');

VaranoiUlam_01

Now lets construct Varanoi diagram for the prime numbers (higlighted points in blue) in Ulam spiral.

figure('Position',[0 0 800 800]);
hold on;
xy = [x',y'];
[v,c] = voronoin(xy);
for i = 1:length(c)
  patch(v(c{i},1),v(c{i},2),'w');
end
axis([1 sz  1 sz ]); axis off;
set(gca,'YDir','Reverse');
scatter(x,y,'.b');

VaranoiUlam_02

Cells in Voronoi diagram of the Ulam Prime Spiral

% We observe various poligons with  n-sides such as triangles, quadrangles, pentagons, etc...
% Lets call
% A3 = a sequence of prime numbers which has a Triangular Voronoi cell in Voronoi diagram of the Ulam Prime Spiral
% A4 = a sequence of prime numbers which has a Quadrilateral Voronoi cell in Voronoi diagram of the Ulam Prime Spiral
% A5 = a sequence of prime numbers which has a Pentagonal Voronoi cell in Voronoi diagram of the Ulam Prime Spiral
% A6 = 6 sides
% A7 = 7 sides
% An = n sides
% Q1: What is the maximum value for n, n_max ? In other words is there an uper bound ?
% Q2: If yes, What are the primes whic has a n_max side poligon cells in Voronoi diagram of the Ulam Prime Spiral
% The code below is used to calculate An
k3 = 1; k4 = 1; k5 = 1; k6 = 1; k7 = 1; k8 = 1;
for i = 1:length(c)
  szv = size(v(c{i},1));
  polyN(i) = szv(1);
  switch polyN(i)
    case 3
        A3(k3) = mat(y(i),x(i));
        k3 = k3+1;
        A3xy(k3,:)= [x(i),y(i)];
    case 4
        A4(k4) = mat(y(i),x(i));
        k4 = k4+1;
        A4xy(k4,:)= [x(i),y(i)];
    case 5
        A5(k5) = mat(y(i),x(i));
        k5 = k5+1;
        A5xy(k5,:)= [x(i),y(i)];
    case 6
        A6(k6) = mat(y(i),x(i));
        k6 = k6+1;
        A6xy(k6,:)= [x(i),y(i)];
    case 7
        A7(k7) = mat(y(i),x(i));
        k7 = k7+1;
        A7xy(k7,:)= [x(i),y(i)];
    case 8
        A8(k8) = mat(y(i),x(i));
        k8 = k8+1;
        A8xy(k8,:)= [x(i),y(i)];
  end
end
%
% First 15 terms
A3 = sort(A3);
fprintf('A3 = ');
fprintf('%i, ',A3(1:15));
fprintf('\n');
A4 = sort(A4);
fprintf('A4 = ');
fprintf('%i, ',A4(1:15));
fprintf('\n');
A5 = sort(A5);
fprintf('A5 = ');
fprintf('%i, ',A5(1:15));
fprintf('\n');
A6 = sort(A6);
fprintf('A6 = ');
fprintf('%i, ',A6(1:15));
fprintf('\n');
A7 = sort(A7);
fprintf('A7 = ');
fprintf('%i, ',A7(1:15));
fprintf('\n');
A8 = sort(A8);
fprintf('A8 = ');
fprintf('%i, ',A8(1:15));
fprintf('\n');
A3 = 313, 389, 1283, 1399, 1669, 1787, 2087, 2143, 2713, 2801, 3469, 4091, 4787, 4789, 4903, 
A4 = 23, 31, 47, 59, 71, 73, 79, 131, 139, 167, 173, 181, 229, 239, 251, 
A5 = 2, 3, 11, 13, 17, 19, 29, 37, 53, 83, 97, 101, 103, 107, 109, 
A6 = 5, 7, 41, 43, 89, 127, 179, 193, 233, 263, 283, 317, 379, 383, 397, 
A7 = 61, 157, 199, 311, 349, 409, 463, 509, 557, 601, 641, 691, 727, 757, 823, 
A8 = 67, 491, 613, 1013, 1117, 1201, 1249, 1301, 1373, 1543, 1753, 1907, 2017, 2339, 2411, 
% Plotting
% The color code used
% n = 3, Triangle yellow
% n = 4, Tetragon green
% n = 5, Pentagon magenta
% n = 6, cyan
% n = 7, red
% n = 8, yellow

figure('Position',[0 0 800 800]);
hold on;
xy = [x',y'];
[v,c] = voronoin(xy);
for i = 1:length(c)
  patch(v(c{i},1),v(c{i},2),'w');
end
axis([1 sz  1 sz ]); axis off;
set(gca,'YDir','Reverse');
scatter(A3xy(:,1),A3xy(:,2),'.k');
scatter(A4xy(:,1),A4xy(:,2),'.g');
scatter(A5xy(:,1),A5xy(:,2),'.m');
scatter(A6xy(:,1),A6xy(:,2),'.c');
scatter(A7xy(:,1),A7xy(:,2),'.r');
scatter(A8xy(:,1),A8xy(:,2),'.y');
% Note that the last terms can be wrong. They corespond to the points on the outer
% edges of the spiral which might be altered when considering a larger spiral.

VaranoiUlam_03

Triangular Cells with Integer Area

k3 = 1;
k3i = 1;
fprintf('Prime, Cell Area, Perimeter \n');
for i = 1:length(c)
  szv = size(v(c{i},1));
  polyN(i) = szv(1);
    if(polyN(i) == 3)
       % Sides of a triangle
         A = v(c{i}(1, 1),:) - v(c{i}(1, 2),:);
         B = v(c{i}(1, 1),:) - v(c{i}(1, 3),:);
         C = v(c{i}(1, 2),:) - v(c{i}(1, 3),:);
        % Perimeter of a triangle
         pv = norm(A)+ norm(B)+ norm(C);
         P3(k3) = pv;
        % Area of a triangle
        AB = cross([A,0], [B,0], 2);
        S3(k3) =  1/2 * sum(sqrt(sum(AB.^2, 2)));
        A3(k3) = mat(y(i),x(i));
        fprintf('%i %4.4f %4.4f \n',A3(k3), S3(k3),P3(k3))
        %  Primes with triangle Voronoi cells with integer area
        if S3(k3)== round(S3(k3)) % check if area is integer
            A3i(k3i) = mat(y(i),x(i));
            k3i = k3i +1;
        end
            k3 = k3+1;
    end
end
% Primes with triangular Voronoi cells with integer area
fprintf('\n A3i = ');
A3i = sort(A3i);
fprintf('%i, ',A3i);
Prime, Cell Area, Perimeter 
8999 9.0000 14.4853 
9001 9.0000 14.4853 
8627 4.5000 10.2426 
10093  NaN  Inf 
6869 8.0000 13.6569 
9419 6.0000 11.4049 
5867 6.0000 11.4049 
3469 6.0000 11.4049 
2801 6.0000 11.4049 
1669 4.5000 10.2426 
9439 4.5000 10.2426 
4787 6.0000 11.4049 
4789 6.0000 11.4049 
2143 4.5000 10.2426 
1787 4.5000 10.2426 
4933 6.0000 11.4049 
313 6.0000 11.4049 
389 6.0000 11.4049 
1399 6.0000 11.4049 
2713 4.5000 10.2426 
1283 6.0000 11.4049 
2087 4.0000 9.6569 
4091 6.0000 11.4049 
4903 6.2500 12.0711 
8111 6.0000 11.4049 
6037 6.2500 12.0711 
10007  NaN  Inf 
9929  NaN  Inf 

 A3i = 313, 389, 1283, 1399, 2087, 2801, 3469, 4091, 4787, 4789, 4933, 5867, 6869, 8111, 8999, 9001, 9419,

 

Voronoi Diagram, Capitals of Every Country

clear all; clc;close all;

load CapLatLon
lat = CapLatLon(:,1);
lon = CapLatLon(:,2);
sz = size(lon);
for i =1:sz(1)
if lon(i) <= 0
lon(i) = lon(i)+360;
end
end
fig = figure('Position',[0 0 800 800]);
hold on;
xy = [lon,lat];
ind =1;
[v,c] = voronoin(xy);
figure(1);
col = colormap(pink);
for i = 1:length(c)
    if ind >= 24
        ind = 1;
    end
   p = patch(v(c{i},1),v(c{i},2), col(35+ind,:) ); % use color i.
   set(p,'EdgeColor','w')
   ind = ind + 4;
end
Map Configuration
xwidth = 820;
ywidth = 420;
hFig = figure(1);
 set(gcf,'PaperPositionMode','auto')
 set(hFig, 'Position', [100 100 xwidth ywidth])
hold on;
axis([0 360 -90 90]);
load('topo.mat','topo','topomap1');
contour(0:359,-90:89,topo,[0 0],'.k')
axis equal
box on
set(gca,'XLim',[0 360],'YLim',[-90 90], ...
    'XTick',[0 60 120 180 240 300 360], ...
     'Ytick',[-90 -60 -30 0 30 60 90]);
colormap(topomap1);
ylabel('Latitude [deg]');
xlabel('Longitude [deg]');
title('Voronoi Diagram, Capitals of Every Country');
scatter(lon,lat,'.r');
print(fig,'filename','-djpeg','-r600');

Voronoi Diagram Capitals

% Capitals of Every Country

Capital Latitude Longitude
Kabul 34.53 69.17
Tirana 41.33 19.82
Algiers 36.75 3.04
Pago Pago -14.28 -170.7
Andorra la Vella 42.51 1.52
Luanda -8.84 13.23
The Valley 18.22 -63.06
St. John’s 17.12 -61.85
Buenos Aires -34.61 -58.38
Yerevan 40.18 44.51
Oranjestad 12.52 -70.03
Canberra -35.28 149.13
Vienna 48.21 16.37
Baku 40.38 49.89
Nassau 25.06 -77.34
Manama 26.22 50.58
Dhaka 23.71 90.41
Bridgetown 13.1 -59.62
Minsk 53.9 27.57
Brussels 50.85 4.35
Belmopan 17.25 -88.77
Porto-Novo 6.5 2.6
Hamilton 32.29 -64.78
Thimphu 27.47 89.64
Sucre -19.03 -65.26
Sarajevo 43.85 18.36
Gaborone -24.65 25.91
Brasília -15.78 -47.93
Diego Garcia 72.46 7.24
Road Town 18.42 -64.62
Bandar Seri Begawan 4.94 114.95
Sofia 42.7 23.32
Ouagadougou 12.37 -1.53
Bujumbura -3.38 29.36
Phnom Penh 11.56 104.92
Yaoundé 3.87 11.52
Ottawa 45.41 -75.7
Praia 14.93 -23.51
George Town 19.29 -81.37
Bangui 4.36 18.55
N’Djamena 12.11 15.04
Santiago -33.46 -70.65
Beijing 39.91 116.4
The Settlement -10.42 105.68
West Island -12.16 96.82
Bogotá 4.61 -74.08
Moroni -11.7 43.26
Avarua -21.21 -159.78
San José 9.93 -84.08
Zagreb 45.81 15.98
Havana 23.13 -82.38
Nicosia 35.17 33.37
Prague 50.09 14.42
Kinshasa -4.32 15.31
Copenhagen 55.68 12.57
Djibouti 11.59 43.15
Roseau 15.3 -61.39
Santo Domingo 18.5 -69.99
Dili -8.56 125.57
Quito -0.23 -78.52
Cairo 30.06 31.25
San Salvador 13.69 -89.19
Malabo 3.75 8.78
Asmara 15.33 38.93
Tallinn 59.44 24.75
Addis Ababa 9.02 38.75
Stanley -51.7 -57.85
Tórshavn 62.01 -6.77
Suva -18.14 178.44
Helsinki 60.17 24.94
Paris 48.85 2.35
Cayenne 4.93 -52.33
Papeete -17.53 -149.57
Libreville 0.39 9.45
Banjul 13.45 -16.58
Tbilisi 41.69 44.83
Berlin 52.52 13.41
Accra 5.56 -0.2
Gibraltar 36.14 -5.35
Athens 37.98 23.72
Nuuk (Godthåb) 64.18 -51.72
St. George’s 12.06 -61.75
Basse-Terre 16 -61.73
Hagåtña 13.48 144.75
New Guatemala 14.64 -90.51
St Peter Port 49.46 -2.54
Conakry 9.54 -13.68
Bissau 11.86 -15.6
Georgetown 6.8 -58.16
Port-au-Prince 18.54 -72.34
Tegucigalpa 14.08 -87.21
Hong Kong 22.29 114.16
Budapest 47.5 19.04
Reykjavík 64.14 -21.9
New Delhi 28.64 77.22
Jakarta -6.21 106.85
Tehran 35.69 51.42
Baghdad 33.34 44.4
Dublin 53.33 -6.25
Douglas 54.15 -4.48
Jerusalem 35.23 31.77
Rome 41.89 12.48
Yamoussoukro 6.82 -5.28
Kingston 18 -76.79
Edo 35.69 139.69
Saint Helier 49.19 -2.1
Amman 31.96 35.95
Astana 51.18 71.45
Nairobi -1.28 36.82
South Tarawa 1.33 172.98
Pristina 42.67 21.17
Kuwait City 29.37 47.98
Bishkek 42.87 74.59
Vientiane 17.97 102.6
Riga 56.95 24.11
Beirut 33.89 35.49
Maseru -29.32 27.48
Monrovia 6.3 -10.8
Tripoli 32.88 13.19
Vaduz 47.14 9.52
Vilnius 54.69 25.28
Luxembourg 49.61 6.13
Macao 22.2 113.55
Skopje 42 21.43
Antananarivo -18.91 47.54
Lilongwe -13.97 33.79
Kuala Lumpur 3.14 101.69
Malé 4.17 73.51
Bamako 12.65 -8
Valletta 35.9 14.51
Majuro 7.09 171.38
Fort-de-France 14.61 -61.07
Nouakchott 18.09 -15.98
Port Louis -20.16 57.5
Mamoutzou -12.78 45.23
Mexico City 19.43 -99.13
Palikir 6.92 158.16
Chişinău 47.01 28.86
Monaco 43.73 7.42
Ulan Bator 47.91 106.88
Podgorica 42.44 19.26
Plymouth 16.71 -62.21
Rabat 34.01 -6.83
Maputo -25.97 32.58
Nay Pyi Taw 19.75 96.13
Windhoek -22.56 17.08
Yaren 166.93 -0.54
Kathmandu 27.7 85.32
Amsterdam 52.37 4.89
Willemstad -68.92 12.1
Noumea -22.28 166.46
Wellington -41.29 174.78
Managua 12.13 -86.25
Niamey 13.51 2.11
Abuja 9.07 7.48
Alofi -19.06 -169.92
Kingston -29.05 167.97
Pyongyang 39.03 125.75
Saipan 15.21 145.75
Oslo 59.91 10.75
Muscat 23.61 58.59
Islamabad 33.72 73.04
Melekeok 7.5 134.62
East Jerusalem 35.23 31.77
Panama City 8.99 -79.52
Port Moresby -9.44 147.18
Asunción -25.3 -57.64
Lima -12.04 -77.03
Manila 14.6 120.98
Adamstown -25.07 -130.1
Warsaw 52.23 21.01
Lisbon 38.72 -9.13
San Juan 18.47 -66.11
Doha 25.28 51.52
Brazzaville -4.27 15.28
Saint-Denis -20.88 55.45
Bucharest 44.43 26.11
Moscow 55.75 37.62
Kigali -1.95 30.06
Gustavia 17.9 -62.85
Jamestown -15.94 -5.72
Basseterre 17.29 -62.73
Castries 14 -61.01
Marigot 18.07 -63.08
Saint-Pierre 46.78 -56.17
Kingstown 13.16 -61.22
Apia -13.83 -171.77
San Marino 43.94 12.45
São Tomé 0.34 6.73
Riyadh 24.69 46.72
Dakar 14.69 -17.44
Belgrade 44.8 20.47
Victoria -4.62 55.45
Freetown 8.48 -13.23
Singapore 1.29 103.85
Bratislava 48.15 17.11
Ljubljana 46.05 14.51
Honiara -9.43 159.95
Mogadishu 2.04 45.34
Pretoria -25.74 28.19
Grytviken -54.28 -36.51
Seoul 37.57 126.98
Madrid 40.42 -3.7
Colombo 6.93 79.85
Khartoum 15.55 32.53
Paramaribo 5.87 -55.17
Longyearbyen 78.22 15.64
Mbabane -26.32 31.13
Stockholm 59.33 18.06
Berne 46.95 7.45
Damascus 33.51 36.29
Taipei 25.05 121.53
Dushanbe 38.54 68.78
Dodoma -6.17 35.74
Bangkok 13.75 100.5
Lomé 6.14 1.21
Nukunonu -171.85 -9.2
Nuku’alofa -21.13 -175.2
Port of Spain 10.67 -61.52
Tunis 36.82 10.17
Ankara 39.92 32.85
Ashkhabad 37.95 58.38
Cockburn Town 21.46 -71.14
Funafuti -8.52 179.19
Charlotte Amalie 18.34 -64.93
Kampala 0.32 32.58
Kiev 50.45 30.52
Abu Dhabi 24.47 54.37
London 51.51 -0.13
Washington 38.9 -77.04
Montevideo -34.83 -56.17
Tashkent 41.26 69.22
Port Vila -17.73 168.32
Vatican 41.9 12.45
Caracas 10.49 -66.88
Hanoi 21.02 105.84
Mata-Utu -13.28 -176.17
El Aaiún 27.16 -13.2
Sanaa 15.35 44.21
Lusaka -15.41 28.29
Harare -17.83 31.05
%d bloggers like this: