There is 3D space, limited with a cube, with edge=2000.
The center of coordinate system is point (0; 0; 0), so the maximum/minimal coordinate value is 1000/-1000.
There are 10000 points generated with discrete uniform distribution inside of K spheres, located in the cube.
Radius (R) of each sphere is 250.
Centers of spheres are located at the distance of not less than 2*R.
It is required to determine which point related to which sphere.
Input: array of 10000 structures, like:
struct Point {
int number;
int x;
int y;
int z;
}
where number is unique id of the point, x,y,z - it's coordinates.
Output:
array of 10000 structures, like:
struct Point {
int number;
int cluster_id;
}
where cluster_id is unique cluster id of a sphere that point belongs to.
Initially I considered a following solution:
1) Find Euclidian distance for each point from center of coordinates (0;0;0) to point's coordinates.
2) Sort this array of distances in descending order.
3) Get the point from the sorted array of distances and put in a new Set of Cluster Maximals.
4) Compare following point from the array to each value from the Set of Cluster Maximals (initially 1 value).
If it's Euclidian distance less than or equal to 2*R, then
mark this point as belonging to Kth cluster (range=1..N), otherwise add the point to the Set of Cluster Maximals.
5) Repeat step 4.
Two concerns I have:
1) There is an issue that my algorithm would work only in case if Claster Maximals are located on the surface of the spheres.
2) Plus, according to the task requirements, there could be the case when 2 spheres can have 1 and only common point.
I think in case if point belongs to 2 spheres, it is ok to mark it with cluster_id of any of these 2 shperes.
Could you please provide a proper solution to the task?
