Programming Help

Web Development



What's Here?

  • Members: 136,190
  • Replies: 478,565
  • Topics: 74,535
  • Snippets: 2,566
  • Tutorials: 675
  • Total Online: 2,143
  • Members: 77
  • Guests: 2,066

Welcome to Dream.In.Code
Getting C++ Help is Easy!

Join 136,190 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 2,143 people online right now. Registration is fast and FREE... Join Now!




Nearest point to a given point in a plane

 
 Reply to this topicStart new topic

Nearest point to a given point in a plane, Algorithm Discussion
ajaymatrix
1 Aug, 2007 - 02:44 AM
Post #1

D.I.C Regular
Group Icon

Joined: 15 May, 2007
Posts: 389



Thanked: 1 times
Dream Kudos: 100
My Contributions
Problem Statement:
There are n points in a plane.. a1,a2.....an
Given a point a(k) find the point which lies closest to it..

My Approach...
Instead of the naive method of finding all distances between the remaining n-1 points,
I sorted the given points in the order of increasing x co-ordinates.

Now the left most point in the plane is the 1st elem in the array..

Now given a point a[k], I will check a[k+1] as well as a[k-1] and proceed accordingly...(probably moving further up and down the array..)

This is not a good algo as I never thought about what was happening to the y co-ordinate..

What could be a better approach?..

I guess the problem can be solved using graphs and data structures...

Can any one post a detailed algorithmic analysis of this problem...
User is offlineProfile CardPM
+Quote Post

imamkomc
RE: Nearest Point To A Given Point In A Plane
1 Aug, 2007 - 03:59 AM
Post #2

D.I.C Head
Group Icon

Joined: 9 May, 2007
Posts: 62


Dream Kudos: 225
My Contributions
Hi ajaymatrix,

If you guess the problem can be solved using graphs and data structures.
Why you doesn't try to code it.
User is offlineProfile CardPM
+Quote Post

Amadeus
RE: Nearest Point To A Given Point In A Plane
1 Aug, 2007 - 04:21 AM
Post #3

g++ -o drink whiskey.cpp
Group Icon

Joined: 12 Jul, 2002
Posts: 12,226



Thanked: 37 times
Dream Kudos: 25
My Contributions
He's asking for advice on the algorithm, not help in coding it.
User is offlineProfile CardPM
+Quote Post

ajaymatrix
RE: Nearest Point To A Given Point In A Plane
1 Aug, 2007 - 04:52 AM
Post #4

D.I.C Regular
Group Icon

Joined: 15 May, 2007
Posts: 389



Thanked: 1 times
Dream Kudos: 100
My Contributions
exactly..
I did not want to think on the conventional lines..(I hope my algo is pretty different,naturally not effective smile.gif )...

What I intend is a lively discussion on solving this problem,where members can probably come up with new algorithms of their own or probably use the existing ones to elegantly solve this problem...

Hope that the question and what I intend is pretty clear...
User is offlineProfile CardPM
+Quote Post

acetoline
RE: Nearest Point To A Given Point In A Plane
3 Aug, 2007 - 10:43 PM
Post #5

New D.I.C Head
*

Joined: 2 Aug, 2007
Posts: 8


My Contributions
Well, If your point is called p, one method could be to simply find the nearest point on that plane to p (call it p0, and it doesn't necessarily have to be one of your points) Then, just find the point on that plane that is closest to p0. You could do this by sorting them by their uv coordinates along with p0. You would get something like ...u1p0u2... and ...v1p0v2... , then just test u1,u2,v1,v2 for whichever is nearer. You'd just need to test 4 points.

The best part of the above algorithm is that if p changed, you wouldn't have to do all those calculations (sorting) all over again. So it's the best method if you need to do it multiple times for the same plane points.
User is offlineProfile CardPM
+Quote Post

smartC
RE: Nearest Point To A Given Point In A Plane
4 Aug, 2007 - 02:59 AM
Post #6

New D.I.C Head
*

Joined: 25 Jul, 2007
Posts: 18


My Contributions
The y coord is a component para for relative position. Ps (x0, y0) as start node, Pe (x1, y1) as end node. Other points are reachable from Ps, with the nearest at infinity from start. First, start point = Ps and end point = Pe = Ps. Of course this is 0 from Ps. It is easier when Ps is the reference point. while(calcultaion is on) if(Ps < Pe)
Pe = Ps;

That is all smile.gif
User is offlineProfile CardPM
+Quote Post

Reply to this topicStart new topic
Time is now: 12/2/08 01:26AM
Invision Power Board v2.1.7 © 2008  IPS, Inc.
Licensed to: MediaGroup1

Live C++ Help!

C++ Tutorials

Reference Sheets

C++ Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month