lsz - 7 months ago 48

C Question

I would like to fill a plane with randomly placed points, check whether any of them overlap (and if they do, move one of them to empty place) and then calculate the average distance between them. Later I plan on extending that to 3D so that it is kind of having particles in a box.

I know there must be better ways of doing it but here's what I came up with. For placing random points in a plane:

`int pos[NUMBER][2]; /* Creates an array of NUMBER amount of points with x and y coordinate */`

int a, b;

srand( time(NULL) );

for(a=0;a<NUMBER;a++)

for(b=0;b<2;b++)

pos[a][b]=rand()%11; /* Using modulus is random enough for now */

The next stage is finding points that over lap:

`for(a=0;a<NUMBER-1;a++)`

for(b=a+1;b<NUMBER;b++)

if( pos[a][0] == pos[b][0] && pos[a][1] == pos[b][1])

printf("These points overlap:\t", pos[a][0], pos[a][1]);

Now when I identify which points overlap I have to move one of them, but when I do the point in new position might overlap with one of the earlier ones. Is there any accepted way of solving this problem? One way is infinite while(true) loop with breaking condition but that seems very inefficient especially when system gets dense.

Thank you!

Answer

Here's a sketch of a solution that I think could work:

Your point generation algorithm is good, can be left as is.

The correct time to check for overlap is already when the point is generated. We simply generate new points until we generate one that doesn't overlap with any previous.

To quickly find overlap, use a hash table such as the one from '''glib'''. The key could be two int32_t packed into a int64_t union:

`typedef union _Point { struct { int32_t x; int32_t y; }; int64_t hashkey; } Point;`

Use the "iterate over all keys" functionality of your hash table to build the output array.

I haven't been able to test this but it should work. This assumes that the plane is large in relation to the number of points, so that overlaps are less likely. If the opposite is true, you can invert the logic: start with a full plane and add holes randomly.

Average complexity of this algorithm is O(n).