2

I have a nearest neighbor problem in a 2D problem and I found out that kd-trees were the best solution. I couldn't find a ready implementation for the structure I am working with, so I decided to create my own.

The structure I work with is:

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

I have nearly 100000 points, my question is: How to proceed to find the median point each time I want to partition my points, and how to define the left and right partitions in the same time?

Another question would be: Is there a more efficient way to proceed ? (The less time consuming possible).

gsamaras
  • 71,951
  • 46
  • 188
  • 305
berserker
  • 29
  • 6
  • Do you need the median point as in the point that is closest to the mean? Because in a 2D system median point of x and y coordinates are different. – Cem Kalyoncu Aug 05 '15 at 16:01
  • I meant with it the point that separates all my point into two different partitions, with equal points (more or less). Yes, it depends every time on if we're using x or y. – berserker Aug 05 '15 at 16:31

1 Answers1

0

How to compute median? Is there a more efficient way to proceed?

I will give one answer for both questions: You can use std::nth_element, like this:

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

You can also check my question for more.

how to define the left and right partitions in the same time?

Every value less from the median, would belong in the left partition, while every value greater than the median, would belong in the right partition.

It's up to you to decide where the equal value to the median would go. Just pick left or right and remember your decision.

Community
  • 1
  • 1
gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • 1
    The point is I don't see any good way to use nth_element with coordinates. – berserker Aug 05 '15 at 16:07
  • That's up to your implementation. You asked which is the way to go, the way is `nth_element`. Hope this helps and good coding! :) @TahaBenabdallah – gsamaras Aug 05 '15 at 16:10
  • Thank you, I'll try to figure it out :) – berserker Aug 05 '15 at 16:25
  • @TahaBenabdallah that's the spirit. I upvoted you, so that you can have more reputation, if you need to post another question with your attempt that might have problems! Good luck! – gsamaras Aug 05 '15 at 16:26