I have set of latitude and latitude of a specific region which has the mobile towers deployed and now I want to know the best possible location to deploy new mobile towers to overcome the coverage issues, which algorithm or what will be best way to ?

Having set of latitude and longitude which corresponds to the existing location of mobile towers at a region in surat.

As we are facing coverage issues, we want to find a best possible locations to deploy new mobile towerd and overcome the mobile coverage issue in the same region.

How do i get to the soluton?

Which algorithm or what should be done to get some new points to locate new mobile towers or say optimal location/solution by already using the location of exisitng mobilw towers?

Answer 1

[Are Mjaavatten]

Obviously, optmal locations will depend on many factors, such as topography and signal interference risk. But as a first approximation, you could try the points that are farthest away from existing towers in a given region. Voronoi diagrams may be a good tool for this. My File Exchange entry remotest may be what you need, or maybe you can use this as a starting point for a more taylored approach.

[Simran Sandhu]

Thank you Sir, will try to use voronoi diagrams.

[Simran Sandhu]

% Demo of remotest
% generate input and call remotest:
boundary = [[21.1563791,21.168868,21.168177,21.1642294,21.1644141]',[72.7779792,72.788624,72.786243,72.7939752,72.7774434]'];
x = rand(30,1)*1.5;y = rand(30,1)*1.5;
in = inpolygon(x,y,boundary(:,1),boundary(:,2));
x=x(in);y=y(in);
points = [x,y];
[xfar,yfar,distance,polygons] = remotest(points,boundary);
% Plot results:
figure;hold on;
for i = 1:length(x)
    plot(x(i),y(i),'.b')
    plot(polygons{i}(1:end,1),polygons{i}(1:end,2),'color',[0.7,0.7,0.7]);
end
xbound = [boundary(:,1);boundary(1,1)];
ybound = [boundary(:,2);boundary(1,2)];    
h = plot(xbound,ybound,'k');
set(h,'LineWidth',2)
plot(xfar,yfar,'or','MarkerFaceColor','r')
title(sprintf('Most remote spot: (%5.3f, %5.3f). Distance: %5.3f', ...
    xfar,yfar,distance));
axis([min(boundary(:,1)),max(boundary(:,1)), ...
    min(boundary(:,2)),max(boundary(:,2))])
hold off

[Simran Sandhu]

Error using DelaunayTri

The coordinates of the input points must be finite values; Inf and NaN are not permitted.

Error in remotest (line 54)

DT = DelaunayTri(X);

Error in try1 (line 8)

[xfar,yfar,distance,polygons] = remotest(points,boundary)

[Are Mjaavatten]

From your example I see that my remotest function lacks some flexibility. For few boundary points, the farthest point tends to be on the boundary rather than inside. This is probably not what you want in your case. I have therefore updated my entry to take a third input: inner, If this is set to true, only points inside the boundary are considered.

The help text did not specify that the boundary points must be entered in order (clockwise or anticlockwise). This has now been changed.

None of the test points in your code are inside the boundary. This is the cause of your error message. (I should include a test, so that the user gets a more intelligible error message in this case!)

I have modified your example so that it gives sensible results:

% Demo of remotest
% generate input and call remotest:
original = [[21.1563791,21.168868,21.168177,21.1642294,21.1644141]',[72.7779792,72.788624,72.786243,72.7939752,72.7774434]'];
% Order boundary points in clockwise manner;
boundary = original([1,4,2,3,5],:);
figure;
hold on;
plot(boundary(:,1),boundary(:,2))
for i = 1:5
  text(original(i,1)+5e-5,original(i,2),num2str(i))
end

% Create test points so that many fall inside the boundary:
xmax = max(boundary(:,1));
xmin = min(boundary(:,1));
ymax = max(boundary(:,2));
ymin = min(boundary(:,2));
x = xmin + (xmax-xmin)*rand(30,1);
y = ymin + (ymax-ymin)*rand(30,1);
plot(x,y,'*')
hold off

in = inpolygon(x,y,boundary(:,1),boundary(:,2));
x=x(in);y=y(in);
points = [x,y];
[xfar,yfar,distance,polygons] = remotest(points,boundary,true);
% Plot results:
figure;hold on;
for i = 1:length(x)
    plot(x(i),y(i),'.b')
    plot(polygons{i}(1:end,1),polygons{i}(1:end,2),'color',[0.7,0.7,0.7]);
end
xbound = [boundary(:,1);boundary(1,1)];
ybound = [boundary(:,2);boundary(1,2)];    
h = plot(xbound,ybound,'k');
set(h,'LineWidth',2)
plot(xfar,yfar,'or','MarkerFaceColor','r')
title(sprintf('Most remote spot: (%5.3f, %5.3f). Distance: %5.3f', ...
    xfar,yfar,distance));
axis([min(boundary(:,1)),max(boundary(:,1)), ...
    min(boundary(:,2)),max(boundary(:,2))])
hold off

[Simran Sandhu]

Thank you so so much sir, you saved me ..

Got the sensible result, and as kind of desired

[Simran Sandhu]

title(sprintf('Most remote spot: (%5.3f, %5.3f). Distance: %5.3f', ...
    xfar,yfar,distance));

why is this not being displayed in result?

[Are Mjaavatten]

The script creates two figures. Capture.png shows the first plot, which I included just to show the numbering of the boundary points and the position of the test points relative to the boundary, The the title is found on the second plot (from line 28 onwards).

[Simran Sandhu]

Error using remotest

Too many input arguments.

Error in try1 (line 26)

[xfar,yfar,distance,polygons] = remotest(points,boundary,true);

This error is coming and the second image is not coming

[Are Mjaavatten]

I upgraded remotest.m with the changes I described. You need to download the latest version (2.2.0) from the File Exchange.

[Simran Sandhu]

yes now all the required results are displayed.. Thank you so much.

One more ques can we do this thing with any algorithm like PSO (Particle swarm optimization )

Genetic algorithm ??

[Are Mjaavatten]

My routine maximizes the distance from neihgboring towers and thus may give you a starting point for placing your tower. But most likely you must take into account several other factors like topography, population distribution, making sure that major roads get good coverage, and so on.

You may be able to formulate an optimization criterion that handles some of these factors. You may have to add constraints, e.g. avoid areas that are not suited (lakes, nature reserves,...) Given the criterion and constraints, you must find a suitable solver, Some such methods are available in the Matlab optimization toolbox. Particle swarm optimization and genetic algorithms are available in the global optimization toolbox. However, solving complex optimization problems may be quite challenging and require some level of expertise.

Unless you have access to such expertise, it may be simpler to use trial and error in combination with common sense and your professional knowledge.

[Simran Sandhu]

Thank you so much sir for your guidance to begin my work here, I hope I reach the desired solution soon.

thank you