Solved

Store Array of x,y coordinate elements

Posted on 2004-03-22
28
513 Views
Last Modified: 2010-04-15
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
Comment
Question by:XPUSR
  • 9
  • 8
  • 4
  • +2
28 Comments
 
LVL 45

Expert Comment

by:Kdo
ID: 10648820
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
 
LVL 9

Accepted Solution

by:
ankuratvb earned 39 total points
ID: 10649201
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
 

Author Comment

by:XPUSR
ID: 10649253
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
 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 37 total points
ID: 10649282
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
 
LVL 45

Expert Comment

by:Kdo
ID: 10649334
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
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10649381
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
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10649397
Kent,sorry for that.
Didnt refresh the page so didnt see ur last post.
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10649413
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
 

Author Comment

by:XPUSR
ID: 10650429
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
 

Author Comment

by:XPUSR
ID: 10650587
When realloc is called it seems to erase all previous elements in the array????
0
 
LVL 10

Assisted Solution

by:Mercantilum
Mercantilum earned 37 total points
ID: 10650601
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
 

Author Comment

by:XPUSR
ID: 10650631
Working now!!

Thank Mercantilum
0
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
LVL 45

Expert Comment

by:Kdo
ID: 10650940
Hi XPUSR,

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

Good Catch, Mercantilum.


Kent
0
 

Author Comment

by:XPUSR
ID: 10651858
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
 
LVL 10

Expert Comment

by:Mercantilum
ID: 10651901
If you have only 40 maybe it's ok - or you have to think of a more complex algorithm, sorting the coords.
0
 

Author Comment

by:XPUSR
ID: 10652213
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
 
LVL 45

Expert Comment

by:Kdo
ID: 10652443
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
 

Author Comment

by:XPUSR
ID: 10652476
"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
 
LVL 45

Expert Comment

by:Kdo
ID: 10652531
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
 

Author Comment

by:XPUSR
ID: 10652643
kent,
how could I improve on the bsearch()?

0
 
LVL 45

Expert Comment

by:Kdo
ID: 10652863
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
 

Author Comment

by:XPUSR
ID: 10652982
thanks,

Q. what is idx?

Q. if i have only 5 coordinates in the array is it worth using the above algorithm.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 10653570
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
 
LVL 8

Assisted Solution

by:ssnkumar
ssnkumar earned 37 total points
ID: 10655294
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
 
LVL 8

Expert Comment

by:ssnkumar
ID: 11356839
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

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now