nearest neighbor

[Noori]

In this project you are asked to find K nearest neighbors of all points on a 2D space. The distance
metric that you are going to use is simply the Euclidean distance
example;

inputs:
10 2
3.57 3.18
84.91 27.69
93.40 4.62
67.87 9.71
75.77 82.35
74.31 69.48
39.22 31.71
65.55 95.02
17.12 3.44
70.60 43.87

Outputs:

1 9 7
2 10 3
3 2 4
4 2 3
5 6 8
6 5 10
7 10 9
8 5 6
9 1 7
10 2 6

[MiiNiPaa]

Please note, that this is not a homework site. We won't do your homework for you. However we are always willing to help solve problems you encountered, correct mistakes you made in your code and answer your questions.

We didn't see your attemts to solve this problem youself and so we cannot correct mistakes you didn't made and answer questions you didn't ask. To get help you should do something yourself and get real problems with something. If your problem is "I don't understand a thing", then you should go back to basics and study again. As it is impossible to find deriviative of function without knowledge in ariphmetics, you cannot do more complex tasks in programming without clear understanding of basics

[Noori]

dear brother,
I am trying to do it for sure, But the thing is that how i start it>
i never asked to give the whole code but an idea and opinion

[MiiNiPaa]

i never asked to give the whole code but an idea and opinion

You just dumped assigment without asking question.

Now for your program structure:
1) Create a structure to hold a point (2 coordinates) or use std::pair
2) Create a vector of your points
3) Read input in said vector.
4) For each point: sort vector by distance from said point.
5) Output K points starting from index [1] (in [0] there will be original point)

[Noori]

how to use vector in here?
i tried to add the x and y coordinates in a 2d array and saved them there,
but it didnt work out.

[MiiNiPaa]

1) Create a structure to hold a point (2 coordinates)

struct point
{
    double x;
    double y;
}

2) Create a vector of your points

std::vector<point> points;
//Read points and add them to vector one by one. 

[Noori]

thnks

[Noori]

struct point{
int x;
int y;


};
int main(){
vector<point> points(10);
point.x[]={1,2,3,4,5,6,7,8,9};
point.y[]={1,2,3,4,5,6,7,8,9};

cout<<point.x[1];

}
lets say that i have the points, but it gives me error

[MiiNiPaa]

1) your vector is called points, not point
2) You cannot assign points like that. Remember, vector can be threated as resizeable array. Use push_back() or initialization lists:

vector<point> points = {{1, 1}, {2, 2}, {3, 3}};
std::cout << points[0].x << ' ' << points[0].y

http://www.mochima.com/tutorials/vectors.html

[Smac89]

You guys heard of kdtrees?
http://en.wikipedia.org/wiki/K-d_tree

Not hard to implement, it is simply a binary search tree except it partitions points to make for easy access.

Nearest neighbour search algorithm included in the link:
http://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

[Noori]

tnks, but how can i now read this from the file and it to vector?

[Smac89]

That depends on what your inputs mean. What does everything here mean?
10 2
3.57 3.18
84.91 27.69
93.40 4.62
67.87 9.71
75.77 82.35
74.31 69.48
39.22 31.71
65.55 95.02
17.12 3.44
70.60 43.87

[Noori]

10 is the number of points in coordintates and 2 is the number nearest nieghbors that we are going to show.
did you got it?