Complex Counting
I have a math/algorithmic challenge.
I have a simulation where I have a number of point objects grouped on the surface of a sphere. Now I have a number of these spheres programmticaly determined and each with a different number of points that comprise each sphere.
What I wish to do is count the number of points which make up these objects. I.e. so that for example I count 34 points for sphere A, 40 for sphere B, 45 for sphere 50. They are not exact spheres and the points can be thought of as molecules/atoms making a structure. Therefore I wish to calculate the aggregation number of the spheres.
I store positions of the atoms (points) in 3 D space and I also have a cell indexing architecture - working on a nearest neighbour cell basis. In otherwords given an atom one can determine the atoms in neighbouring cells. One can adjust the finetuning of the cell size.
My question thus relates to how I can count the number of atoms in each sphere given the fact that there is no ordering to the atoms in the spheres. Obviously if the spheres are seperated by some large distance then I can do this without too much trouble. However does anyone have any idea of how best to cope with cases where spheres are seperate but are close together such that the neighbour list of one atom will bring in those on another sphere.
Thanks
Not exactly sure of meaning of your question.
Are you primarily interested in cluster analysis, the assignment of an individual point to one or another sphere? i.e. given a set of points you partition into N disjoint sets, where each partition is a set of points that are all approximately on the surface of a single sphere?
If that is the problem, do you know anything about the locations of the spheres, like are they allowed to intersect? Are they allowed to nest?
Wouldnt it make sense to store all points for each sphere in some kind of reference object for each sphere?
class point{
x int;
y int;
z int;
...
}
class Sphere{
Vector points;
....
}
int numOfPoints = points.size();
I dont know if this works in your situation. Hope it helps
> If that is the problem, do you know anything about the> locations of the spheres, like are they allowed to intersect?> Are they allowed to nest?In addition to these questions, are there reasonably tight bounds on their radii?
It is very difficult for me to imagine what exactly you are trying to do. But as far as I can tell, it depends mainly on how the dot clouds were built in the first time, and what relations they possess to each other.
Does a sphere know, which points are related to it? Do the "atoms" know ALL surrounding atoms, or just the ones that belong to the current sphere?
My very first thought (although is still have no idea what you exactly want) was about a tree search, i.e. walking recursively every path from one "atom" on, count every step, and stop first when you only encounter paths that you already went through.
But I really think you have to tell us more, before we can come up with solutions.
The brute force way would be for every combination of 4 points, define the sphere defined by the four points. Then for every other point, calculate the distance to the surface of the sphere. If the calcuclated distance is within the threshold, then record that point as possibly belonging to that sphere.
This approach will be O(n^4) which won't do well for a large number of points.
Finding the center of a sphere:
http://www.google.ca/search?hl=en&q=find+the+center+of+a+sphere+given+4+points&meta=
