Atualmente, estou trabalhando em um projeto que está tentando agrupar pontos 3D de um conjunto de dados, especificando a conectividade como uma distância euclidiana mínima. Meu algoritmo agora é simplesmente uma adaptação 3D do preenchimento de inundação ingênuo.

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;
}

Onde esse trecho de código é executado novamente para a nova semente, e _img.queryRadius () é uma pesquisa de raio fixo na 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;
}

Meu problema com esse código é que ele roda muito lento para conjuntos de dados grandes. Se não me engano, esse código fará uma pesquisa para todos os pontos, e as pesquisas serão O (NlogN), dando a isso uma complexidade de tempo de (N ^ 2 * log (N)).

Além disso, as exclusões são relativamente caras, se bem me lembro das árvores KD, mas também não excluir pontos cria problemas, pois cada ponto pode ser pesquisado centenas de vezes, por todos os vizinhos próximos a ele.

Então, minha pergunta é: existe uma maneira melhor de fazer isso? Especialmente de uma maneira que crescerá linearmente com o conjunto de dados?

Obrigado por qualquer ajuda que você possa fornecer

EDITAR Tentei usar uma lista classificada simples, como disse dash-tom-bang, mas o resultado foi ainda mais lento do que o que eu estava usando antes. Não tenho certeza se foi a implementação ou simplesmente foi muito lento para percorrer todos os pontos e verificar a distância euclidiana (mesmo quando apenas usando a distância ao quadrado).

Existem outras idéias que as pessoas possam ter? Estou honestamente perplexo agora.