В настоящее время я работаю над проектом, который пытается сгруппировать трехмерные точки из набора данных, определяя связность как минимальное евклидово расстояние. Мой алгоритм прямо сейчас - просто трехмерная адаптация наивного заполнения потока.

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

Где этот фрагмент кода запускается снова для нового начального числа, а _img.queryRadius () - это поиск с фиксированным радиусом с помощью библиотеки 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;
}

Моя проблема с этим кодом состоит в том, что он работает waaaaaaaaaaaaaaaay слишком медленно для больших наборов данных. Если я не ошибаюсь, этот код будет выполнять поиск для каждой отдельной точки, и поиск будет O (NlogN), что дает временную сложность (N ^ 2 * log (N)).

В дополнение к этому, удаление, если я помню, прямо из деревьев KD, является относительно дорогим, но не удаление точек создает проблемы в том, что каждую точку можно искать сотни раз, каждый сосед, находящийся рядом с ней.

Итак, мой вопрос, есть ли лучший способ сделать это? Особенно таким образом, что он будет расти линейно с набором данных?

Спасибо за любую помощь, которую вы можете оказать

РЕДАКТИРОВАТЬ Я попытался использовать простой отсортированный список, как сказал dash-tom-bang, но результат оказался даже медленнее, чем то, что я использовал раньше. Я не уверен, что это была реализация, или просто слишком медленно повторять каждую точку и проверять евклидово расстояние (даже при использовании квадратного расстояния).

Есть ли у людей другие идеи? Я честно тупой прямо сейчас.