Найти медиану координат для построения дерева kd (2D) - C++

Question

У меня проблема с ближайшим соседом в двумерной задаче, и я узнал, что kd-деревья - лучшее решение. Я не мог найти готовой реализации для структуры, с которой я работаю, поэтому решил создать свой собственный.

Структура Я работаю с это:

struct Point{ 
    int id; 
    double x; 
    double y; 
}; 

У меня есть около 100000 точек, на мой вопрос: Как поступить, чтобы найти к срединной точке каждый раз, когда я хочу разделить мои очки, и как определить левой и правой частей в одно и то же время?

Другой вопрос: был ли более эффективный способ продолжения? (Меньшее время может потребоваться).

Answer 1

Как вычислить медианную? Есть ли более эффективный способ?

дам один ответ на оба вопроса: Вы можете использовать std::nth_element, например:

std::vector<float> v;         // data vector (global) 
bool myfunction (int i,int j) { return (v[i]<v[j]); } 

int find_median(std::vector<int> &v_i) 
{ 
    size_t n = v_i.size()/2; 
    nth_element(v_i.begin(), v_i.begin()+n, v_i.end(), myfunction); 
    return v_i[n]; 
} 

Вы также можете проверить мой question больше.

---

как определить левые и правые разделы в то же время?

Каждое значение, меньшее от медианы, будет принадлежать левому разделу, а каждое значение, большее, чем медианное, будет принадлежать правому разделу.

Это зависит от вас, чтобы решить, где будет равное значение медианной. Просто выберите слева или справа и запомните свое решение.