cell planning problem
i have a number of problems-- but will start with this one first:
1) first. imagine there is 2-d surface that is 15 kilometers x 15 kilometers. there are "points" ( reception test points for anyone familiar with cellular communicadtion ) placed every 100 meters on this 2-d surface. So a 15 x 15 kilometer area has 22,801 "points." these points are labeled in order from 0 to 22,800.
now, suppose that we place a "mast" at a random x, y location on this 2-d surface. for example, it could be placed at x, y location 1500, 10000. this "mast" has a transmisson range of 5 kilometers ( for example ). thus, it will "cover" (or subsume) a large number of the "points" originally placed on this surface.
the first question: what is the most efficient means for determing which points the circle subsumes?
i am currently using the following formula... is there anything better?
for( j = 0; j < 22801; j++ ){
// the xCoordinate is the x location of each "point" in turn
// (e.g., they are at 0,0; 100,0; 200,0;...15000,15000)
// while the mastXlocation is the location of the mast in
// question; the same is true for y.
int mathX = ( xCoordinates[ j ] - mastsXLocation );
int mathY = ( yCoordinates[ j ] - mastxYLocation );
int inOrOnCircle = ( mathX * mathX ) + ( mathY * mathY ) -( range * range );
if( inOrOnCircle <= 0 )
{
// this array stores whether the mast covered a specific
// "point" and is used in later calculations
whichMastsCover[ j ] = j;
}
}
Instead of testing every point in your domain, you can narrow the domain to a much smaller square:
5km 5km
V-V-V
.....................
.....................
.....###########..... <
.....###########..... |
.....###########..... |
.....###########..... | 5km
.....###########..... |
.....#####O#####..... <
.....###########..... |
.....###########..... | 5km
.....###########..... |
.....###########..... |
.....###########..... <
.....................
.....................
.....................
. = a point
# = a point whose dx,dy is between (-5,-5) and (5,5)
O = the station
Now you can just iterate over all of the # points, using the same test you were using before.
For extra credit: Approximately what percent of tested stations will come up negative?
JN_ at 2007-7-7 2:00:48 >
yes... JN... that is a good idea in theory, but i have
tried it in practice and it ends up being slower than
iterating through all the test points. that is, to do
what you are suggesting, you need to store the locations
of each test point in a double array: e.g., coordinates[ x ][ y ],
so that you can determine the coordinates in the "smaller square"
that you need to search. to accomplish the same bit of code above,
it starts to look like this:
// this bit of code determines the coordinates of your
// "smaller square"
int startx = tempX - range; // minmum value x can be
int stopx = tempX + range; // maximum value x can be
int starty = tempY - range; // minimum value y can be
int stopy = tempY + range; // maximum value y can be
// this ensures the value is never less than 0
if( startx < 0 )
startx = 0;
if( stopx < 0 )
stopx = 0;
if( starty < 0 )
starty = 0;
if( stopy < 0 )
stopy = 0;
// this ensures the value never goes beyond the
// area
if( startx > side1 )
startx = side1;
if( stopx > side1 )
stopx = side1;
if( starty > side1 )
starty = side1;
if( stopy > side1 )
stopy = side1;
// rtpSeparation is 100 meters in this case... but could
// be a different value... and sometimes is to increase speed
for( int i = startx; i <= stopx; i+=rtpSeparation )
{
for( int j = starty; j <= stopy; j+=rtpSeparation )
{
int mathX = ( i - tempX );
int mathY = ( j - tempY );
int inOrOnCircle = ( mathX * mathX ) + ( mathY * mathY ) - ( range * range );
if( inOrOnCircle <= 0 && RTPCoordinates[( i / rtpSeparation )][( j / rtpSeparation )] != 0 )
{
whichMastsCoverWhichRTParrayDynamic[( i / rtpSeparation )][ ( j / rtpSeparation )] = 1;
}
}
}
this ends up being slower than increasing the size of
the separation between the "points" from say every 100 meters
to every 200 meters or 300 meters alone... which does
dramatically reduce the number of "points" that need to be
iterated through. E.g., a 15 x 15 square kilometer surface
with "points" every 100 meters has 22801 "points", whereas the
same size surface with points every 300 meters has 2601 points.
you have already earned yourself 1 point for a good first
attempt... but speed is of the essence here... as i do deal with
60 x 60 square kilometer surfaces as well!
You have an algorithm that maps the point number to its (x,y) coordinates, namely those two arrays. To make better use of JN's suggestion you need the reverse algorithm, namely one that maps the (x,y) coordinates to the point number. If you arrange your point numbers correctly that algorithm might be as simple as "j = 151*x + y".
That is a good suggestion DrClap, and is worth a Duke Dollar on merit alone; i.e., that it made me think about my data structures/algorithms more deeply than I had before. Let me just make sure I understood what you were saying...
In other words, I am trying to find a function that, given an x coordinate of a "point" and a y coordinate of a "point", uniquely identifies that "point". For example, if I have 28001 points, the function must take in the coordinates of each point and ensure that each point is uniquely identified.
For example, the function j = 3 * x + y would not work, because the "point" at 200, 100 would yield 700 (3 + 200 + 100), as would the "point" at 100, 400 (3 * 100 + 400). However, the function j = 151 * x + y would work in that case, as 151 x 200 + 100 = 30300, and 151 x 100 + 400 = 15500. The trick here is ensuring that each "point" is and always will be uniquely identified by the function.
If successful, I would then be able to use a single array instead of a double array again, and still be able to test coordinates within the "smaller square" mentioned by JN.
As this new way of computing things affects other structures not mentioned here, it may take me a few days to test concretely whether this works for my program... but I am definitely going to give it a try and will report back. If what I have said in this post is incorrect, please correct me.
Update:
The function j = ( 751 * x + y ) produces unique numbers for 15km x 15km, 30km x 30km, 45km x 45km, 60km x 60km with "point" separations of 100, 200, and 300 meters. So this is a good first step.
Just to let you know, the function j = ( 151 * x + y ) produces unique numbers at all variations of 15km x 15km, but at 30km x 30km it produced only 45601 out of 90601 unique numbers at a 100 meter separation.
However, the "151" hint did help a lot... as I just kept increasing the value by 100 until "751" provided the "ticket to ride."
On to the next step... which is trying to implement it... **sweats**
If this topic is still actual for its author: there are simple algorithm for drawing circles without using floating-point arithmetics (used for raster screens with integer point coordinates, your case with discrete coordinates of points is similar) -- the Bresenham's algorithm (maybe I'm wrong in its author's name, sorry, English is not my native language) it can be found in any book on computer graphics.
It can iteratively compute integer coordinates of the points laying on the "quarter" of circle where "quarter" is the set of points which coordinates is not less than the center coordinates on every axis (for example for circle with center in (xc, yc) one quarter is all the points (x, y) laying on the circle having x >= xc and y >= yc).
You can build your own algorithm based on the above which will compute coordinates of points laying on or inside the circle by reflecting the point coordinates of the "quarters" around the center and limiting it with an array borders (because you can get an intersection of them and the circle).
Hope this helps.
to: i am neuron... i had a quick look at the algorithm you suggested, but it seemed more about drawing circles, which is not what i am really doing here... but thanks for the thought.
to: DrClap and Ns...back to the program... i tried the method but, again, they were slower than the original brute force method. this is what the modified program looked like, perhaps there is still something wrong in it:
for( int i = startx; i <= stopx; i+=rtpSeparation )
{
for( int j = starty; j <= stopy; j+=rtpSeparation )
{
int mathX = ( i - tempX );
int mathY = ( j - tempY );
int inOrOnCircle = ( mathX * mathX ) + ( mathY * mathY ) - ( range * range );
// method 1 used an ArrayList and was terribly slow
/*
if( inOrOnCircle <= 0 )
{
int q = RTPCoord1.indexOf( new Integer( 751 * i + j ) );
whichMastsCoverWhichRTParrayDynamic[ q ] = 1;
}
*/
// method 2 used a sequential search; again, not as slow, but still slower than the brute force
boolean continue1 = true;
if( inOrOnCircle <= 0 && continue1 == true )
{
int temp = 751 * i + j;
int q = 0;
while( continue1 == true )
{
if( RTPCoord[ q ] == temp )
{
// 1 indicates that an rtp is covered, 0 (default) is not covered
whichMastsCoverWhichRTParrayDynamic[ q ] = 1;
continue1 = false;
}
q++;
}
}
//***//
} }
in any case, i know this is not an easy problem to resolve, but i really do appreciate the help i have received. even if i am still using the original code, i have still learned a few tricks along the way which may at some time improve my programs, and approach to them. if you, or anyone else, has any further ideas, people do not hesitate to suggest them. i will gladly award the rest of the points.
To JN and DrClap... Thank you both for helping me to improve my program. I have finally resolved all my conundrums with the piece of code you find below. I will award the rest of my points to you both, as this whole question has now been answered. Thank you for putting up with my poor attempts at code, but I am still a bit of a green-horn.
Thanks again, the program now runs remarkably faster! And I don't even need the coordx[ ] or coord[ y ] arrays any more. It took me a while to get my head around that as I had lived with this code for a few months already.
if( inOrOnCircle <= 0 )
{
int answer = ( ( ( i / rtpSeparation ) * 51 ) +
( ( j / rtpSeparation ) + 1 ) );
whichMastsCoverWhichRTParrayDynamic[ answer ] = 1;
}
