Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 531
  • Last Modified:

Store Array of x,y coordinate elements

I have a function that takes an x an y coordinate as parameters

void storecoords(float x, floaty)
{
float Array[][2];
}  


I need to store a number of x,y coordinates in an array such that:

Array [x1 ][x2][x3][x4][x5] ...
         [y1 ][y2][y3][y4][y5] ...

i.e.
As the x y coordinates are recieved by the function I need to
1) check if the coordinates are in the array.
2) if if the coordinates are do nothing.
3) if the coordinates are not in the array: add the coordinates to the array.

n.b the array must be able to grow dynamically as more and more coordinates are added?

Any suggestions appreciated?
Thanks,



0
XPUSR
Asked:
XPUSR
  • 9
  • 8
  • 4
  • +2
4 Solutions
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

If the array must be able to grow, you cannot define it as static data, or heap data with 'float Array[][2]'.  You'll have to use malloc(), calloc(), and/or realloc() to grow the array.

It really is a piece of cake to put into effect.  In fact, if you can live with a singly dimensioned array this is almost trivial, and it will certainly be "standard C".  A singly dimensioned array would put the X,Y pairs into consecutive locations.  For any pair (N) that is in the array, X is at location (X * 2) and Y is at (X * 2 + 1).


Kent
0
 
ankuratvbCommented:
You can also use 2 different dynamically allocated arrays,one for x ,one for y:

float *x;
float *y;

x=malloc(n*sizeof(float));
y=malloc(n*sizeof(float));

then,x[i] and y[i] refer to one pair.
0
 
XPUSRAuthor Commented:
o.k thanks,

but if i store it dynamically,

how can I seach this array (as efficient as possible(real time based app)) to find if the co-ordinate  is present or not.

do i have to search through each element of the array looking for (x,y) or can this be achieved any faster?
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

Regarding my earlier post, my fingers simply didn't tap out what my head was thinking.  The last line should read, "For any pair (N) that is in the array, X is at location (N * 2) and Y is at (N * 2 + 1)".

Ankuratvb's suggestion of separate x[] and y[] arrays is also good advice.


If you've got C++ available to you, I suggest that you look seriously into using it.  The class structure would allow you to create a "DataPair" class that would automatically expand the arrays as you add items to them and prevent your program from ever over-indexing an array.  Dynamic arrays fit the tools of C++ extremely well.



Kent
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

Is the data sorted?  If so, you can do a binary search on it just as you would any other array.  An array of 1,000,000 entries is then searched with only 20 tests.

If not, you'd have to sequentially search the array just as you would any other array.

Here's an example of using a single array to contain all of the data would add an entry.


float *MyData = NULL;
int   MyDataLength = 0;


AddDataPair (float X, float Y)
{
  MyData = (float *)realloc (MyData, 2*(MyDataLength+1));
  MyData[MyDataLength*2] = X;
  MyData[MyDataLength*2+1] = Y;
  MyDataLength++;
}



Here's the same technique using separate X and Y arrays:

float *MyDataX = NULL;
float *MyDataY = NULL;
int   MyDataLength = 0;


AddDataPair (float X, float Y)
{
  MyDataX = (float *)realloc (MyDataX, (MyDataLength+1));
  MyDataY = (float *)realloc (MyDataY, (MyDataLength+1));
  MyDataX[MyDataLength] = X;
  MyDataX[MyDataLength] = Y;
  MyDataLength++;
}


Search functions would use any/all of these arrays in similar fashion.
Kent
0
 
ankuratvbCommented:
The speed of retrieval would depend on how u store the data.

For e.g. if the array values are stored sorted(keep storing in sorted order),checking for presence can be done using Binary search which is much faster than Linear Search.

0
 
ankuratvbCommented:
Kent,sorry for that.
Didnt refresh the page so didnt see ur last post.
0
 
ankuratvbCommented:
Even if the data is not sorted,
U have to take a decision as to whether the frequency of u checking for presence of co-ordinates is high enough
for u to keep the array sorted or sorting the list regularly.
0
 
XPUSRAuthor Commented:
hi Kdo,

I have compiled & executed your code it works somewhat but there seems to be  a bug with

 MyData = (float *)realloc (MyData, 2*(MyDataLength+1));

It seems that realloc is not allocation enough space. When I change it to
MyData = (float *)realloc (MyData, 2*(MyDataLength+10)); it works again,

until such time as I call the AddDataPair (float X, float Y) function more that say 6 or 7 times.
then it carshes again. But if i change it to MyData = (float *)realloc (MyData, 2*(MyDataLength+1000)); it works again,

do you understand why this is happening?

 
0
 
XPUSRAuthor Commented:
When realloc is called it seems to erase all previous elements in the array????
0
 
MercantilumCommented:
Sounds like the size of the type is missing ... :)

AddDataPair (float X, float Y)
{
  MyData = (float *)realloc (MyData, 2 * sizeof(float) * (MyDataLength+1));
  MyData[MyDataLength*2] = X;
  MyData[MyDataLength*2+1] = Y;
  MyDataLength++;
}
0
 
XPUSRAuthor Commented:
Working now!!

Thank Mercantilum
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

As soon as I read your symptom I knew what I'd left off.  My apologies....

Good Catch, Mercantilum.


Kent
0
 
XPUSRAuthor Commented:
Hi,

Regarding "the check if coords are in array or not"

"U have to take a decision as to whether the frequency of u checking for presence of co-ordinates is high enough
for u to keep the array sorted or sorting the list regularly."

I am going to be checking this very frequently.
I will not have many co-ordinates in the array at most 30-40 (x,y).

So what do you think is the best way to seach

maybe something like the following?

//new coordinate check if it is in the array if not add it to the array
flag inarray=false;
Xcoord=21;
Ycoord=343;

for(i=0;i<sizeof(MyData);i=i+2)    //i=i+2  as we have a 1D array(every 2nd one) MyData[x][y][x][y][x][y][x][y]
{

    if(MyData[i]==Xcoord)//check if xcoord is in array
    {
         //check if y coord is next to the x coordinate
        if(MyData[i+1]==Ycoord)
          {
          printf("co-ordinate in array");
          }
     inarray=true;
    }
 
   if(inarray==false) addCoordArray(Xcoord,ycoord); //If not add call function to to add it to array
   
}


Can I make this any faster considering I have to test is the coord in the array frequently and the fact that there is only a max of
40 coordinates?

Thanks
0
 
MercantilumCommented:
If you have only 40 maybe it's ok - or you have to think of a more complex algorithm, sorting the coords.
0
 
XPUSRAuthor Commented:
Is sorting the coordinates the only method of speeding it up.
Is it woth sorting the coord given the fact that there are only 40?
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

The next question is how often will you be adding or deleting coordinates.

It may be beneficial to insert new coordinates into their sorted locations.


Kent
0
 
XPUSRAuthor Commented:
"The next question is how often will you be adding or deleting coordinates"

coordinates will be added when the program is executed and after that very very rarely...

"It may be beneficial to insert new coordinates into their sorted locations."
But how will sorting them help me increace my find time?
What way do i sort them?
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

Sort the array in ascending order.  Because the data rarely changes when the program is running, the sorting/inserting algorithm doesn't need to be particularly efficient.

The bsearch() function can be used to examine the array.  Because the array is so small, it might be worthwhile to write your own binary search routine that doesn't rely on the system provided algorithm.  The bsearch() function has to call your comparison routine every time through the loop.  If bsearch() proves too slow, writing your own (I can help with this, too) should drastically cut search times -- perhaps by as much as 50%.


Kent
0
 
XPUSRAuthor Commented:
kent,
how could I improve on the bsearch()?

0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

Writing your own is faster on such a small dataset.


bsearch (int Target)
{
  int LowIdx;
  int HighIdx;
  int MidIdx;
  int CompareValue;

    LowIdx = 0;
    HighIdx = idx-1;
    MidIdx = (LowIdx + HighIdx) / 2;
    while (LowIdx != HighIdx)
    {
      CompareValue = Target - X[idx];
      if (CompareValue < 0)
        HighIdx = MidIdx;
      else if (CompareValue > 0)
        LowIdx = MidIdx+1;
      else
        break;
      MidIdx = (LowIdx + HighIdx) / 2;
    }
  return MidIdx;
}


The system released bsearch is "general purpose" so you have to provide it some help, like the comparison function.  



Kent
0
 
XPUSRAuthor Commented:
thanks,

Q. what is idx?

Q. if i have only 5 coordinates in the array is it worth using the above algorithm.
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi XPUSR,

Sorry -- took the code from another application and didn't change that one variable.  :)  This was actually borrowed from an app that compared strings.  A "true" binary search doesn't have three conditions, as this one does.

idx is th number of items in the array.  If idx==1, then HighIdx becomes 0, meaning that the only item in the array is the correct one.


If you're searching a small dataset, a sequential search is just fine.  You might start there, and convert to a binary search only when you think that performance is a problem.



Kent
0
 
ssnkumarCommented:
For comparing float (or double) you will have to do it differently than int. The reason is, the float value may be same upto some decimal points and after that it can be different. So, you have to decide about the accuracy upto whch you want to compare and write a small function to do the comparison. Here is a sample code to do this:

typedef int8_t bool;
#define TRUE 1
#define FALSE 0
Bool EqualTo(double a, double b)
{
        double accuracy = 0.0001;

        if (fabs(a - b) <= accuracy ) return TRUE;
        else return FALSE;
}

0
 
ssnkumarCommented:
jmcg,

What you said is absolutely correct.
None of us tried to analyze in the way you have suggested!
It is very surprising....!!
We must start thinking about this and ....:-)

May be we would have reached those points if the discussion had continued:-)

Thanks for the suggestion....

-ssnkumar
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 9
  • 8
  • 4
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now