Vfrdtyky

I have many rays, all whose start points are on a sphere in 3D, and whose direction vectors point inwards. Some of the rays are pointing towards a point A, others are pointing towards a point B, etc, with some noise (i.e. the rays don't perfectly intersect each other at their corresponding point A, B, etc).

Is there an algorithm that will allow me to determine how many points A,B, etc there are? Or even better, where those points are located? I don't know the locations of points A, B, etc, only the start points and direction vectors of the rays.

For example, is a sample setup, but in 2D, and I don't know which rays are pointing to which point (i.e. I don’t know which rays are red or blue). How would I find the number of points they’re pointing towards (two, in this example) or the locations of the points they're pointing towards?

I’ve tried a few different algorithms suggested in my earlier question, but they all seem to lose accuracy in identifying the locations of the points when the points are located close to each other. My first priority is just identifying the number of points with a high degree of accuracy even when they are located close together. Would that be possible, even if I have to sacrifice accuracy in locations?

Edit: If we let the radius of the sphere be 1000 units, then the error in the direction vector is about 10-20 units, while the min distance that the points can be apart for the algorithm to work currently is around 50 units. I don’t think this seems insurmountable, but I may very well be wrong.

I suggest that you treat this as a changing variant of the point-clustering problem.

First, make a set of points. Choose an approach threshold: how close should two rays come before you suspect that they refer to the same point? For each pair of rays that satisfies this threshold, insert a point at the midpoint of the segment of their closest approach. This is simple (?) 3D linear algebra.

Now, use your favorite cluster-counting algorithm to determine the quantity of clusters you have among these points. Your approach threshold will be highly significant in discriminating nearby points (see my comment).

Edit: thanks for the update in your question. The 50-unit separation in your data, compared to the 10-20 unit error, should allow you to discriminate "near" centroids using a density-sensitive clustering algorithm. Perhaps one of the spectral clustering methods will do the job for you.

You now have `k' identified clusters. Adapt the k-means clustering algorithm.

1. Choose the midpoint of each cluster as the centroid.


2. Delete all the "closest approach" points you made in the previous iteration. Keep the centroids.


3. Determine the cluster to which each ray belongs: your distance function is the closest approach of the ray to each of the centroids.


4. As you classify each ray, add to that cluster the point of that ray's closest approach to the centroid.

Repeat steps 1-4 until you've converged according to whatever epsilon criterion you have. The centroids are your targe points (A, B, etc.)

• If you have any outliers, suspect that you are short a centroid.


• If the centroids are too close (by whatever nearness criterion you can extract), then merge them.