Dado: Dado un conjunto de N puntos en el plano 2D (coordenadas xey), y un conjunto de N radios correspondientes a cada punto. Nos referiremos al disco de un punto como el disco centrado en el punto con su radio.clúster de 2d puntos
Problema: Agrupa los puntos. Un grupo de puntos es tal que cada punto CUALQUIERA cae dentro del disco de al menos otro punto del grupo O al menos otro punto del grupo cae dentro de su disco. Los clústeres de puntos individuales no cuentan como grupos.
Necesito un algoritmo para calcular esto de manera eficiente (preferiblemente sin recurrir a complicadas técnicas de hash espacial como kd-trees). Puedo conformarme con O (N^2) tiempo de ejecución pero definitivamente no más que O (N^3). Siento que esto debería ser simple, pero estoy atrapado en la naturaleza no recíproca de mi condición de agrupamiento.
En esencia, estoy buscando llenar el prototipo de la función C:
int cluster_points(
size_t n,
point_t *pt, // length n list of points
double *radius, // length n list of radii for each point
int *cluster, // length n list of cluster indexes; -1 if not clustered
size_t *ncluster // number of clusters (number of distinct non -1 entries in cluster)
);
Ésta no es la tarea. Lo necesito como parte de un algoritmo de matriz para agrupar números complejos.
En el paso 2ab, ¿no tienes que seguir yendo a todos los puntos agregados y mirar el resto de los puntos sin asignar hasta que no se asigne nada nuevo? –
@VictorLiu: No lo creo. Con este método, una vez que haya establecido el grupo 1 (y se haya movido al grupo 2), el grupo 1 contiene todos los puntos que se ajustan a los criterios y que alguna vez pertenecerán a este grupo. Al definir el grupo 1, cada vez que le agrega un punto, barre todos los otros puntos para ver si ahora pueden estar en el grupo. No hay posibilidad de que, por ejemplo, tengas que unirte al grupo 1 y al grupo 2, una vez que se haya establecido el grupo 1. – tom10