Actualmente, estoy trabajando en un proyecto que intenta agrupar puntos 3D de un conjunto de datos especificando la conectividad como una distancia euclidiana mínima. Mi algoritmo en este momento es simplemente una adaptación en 3D del ingenuo relleno de inundación.

size_t PointSegmenter::growRegion(size_t & seed, size_t segNumber) {
    size_t numPointsLabeled = 0;

    //alias for points to avoid retyping
    vector<Point3d> & points = _img.points;
    deque<size_t> ptQueue;
    ptQueue.push_back(seed);
    points[seed].setLabel(segNumber);
    while (!ptQueue.empty()) {
        size_t currentIdx = ptQueue.front();
        ptQueue.pop_front();
        points[currentIdx].setLabel(segNumber);
        numPointsLabeled++;
        vector<int> newPoints = _img.queryRadius(currentIdx, SEGMENT_MAX_DISTANCE, MATCH_ACCURACY);
        for (int i = 0; i < (int)newPoints.size(); i++) {
            int newIdx = newPoints[i];
            Point3d &newPoint = points[newIdx];
            if(!newPoint.labeled()) {
                newPoint.setLabel(segNumber);
                ptQueue.push_back(newIdx);
            }
        }
    }

    //NOTE to whoever wrote the other code, the compiler optimizes i++ 
    //to ++i in cases like these, so please don't change them just for speed :)
    for (size_t i = seed; i < points.size(); i++) {
        if(!points[i].labeled()) {
            //search for an unlabeled point to serve as the next seed.
            seed = i;
            return numPointsLabeled;
        }
    }
    return numPointsLabeled;
}

Donde este fragmento de código se ejecuta nuevamente para la nueva semilla, y _img.queryRadius () es una búsqueda de radio fijo con la biblioteca ANN:

vector<int> Image::queryRadius(size_t index, double range, double epsilon) {
    int k = kdTree->annkFRSearch(dataPts[index], range*range, 0);
    ANNidxArray nnIdx = new ANNidx[k];
    kdTree->annkFRSearch(dataPts[index], range*range, k, nnIdx);
    vector<int> outPoints;
    outPoints.reserve(k);
    for(int i = 0; i < k; i++) {
        outPoints.push_back(nnIdx[i]);
    }
    delete[] nnIdx;
    return outPoints;
}

Mi problema con este código es que se ejecuta waaaaaaaaaaaaaaaay demasiado lento para grandes conjuntos de datos. Si no me equivoco, este código hará una búsqueda de cada punto, y las búsquedas son O (NlogN), dándole una complejidad de tiempo de (N ^ 2 * log (N)).

Además de eso, las eliminaciones son relativamente caras si no recuerdo mal de los árboles KD, pero no eliminar puntos crea problemas porque cada punto puede ser buscado cientos de veces, por cada vecino cercano.

Entonces mi pregunta es, ¿hay una mejor manera de hacer esto? ¿Especialmente de una manera que crecerá linealmente con el conjunto de datos?

Gracias por cualquier ayuda que pueda brindar.

EDITAR Intenté usar una lista ordenada simple como dijo dash-tom-bang, pero el resultado fue aún más lento que lo que estaba usando antes. No estoy seguro de si fue la implementación, o simplemente fue demasiado lento para recorrer cada punto y verificar la distancia euclidiana (incluso cuando solo se usa la distancia al cuadrado.

¿Hay alguna otra idea que la gente pueda tener? Honestamente estoy perplejo en este momento.