Finding the closest point to (x1,y1) in array of [x1,y1,z1,x2...

Member
Posts: 281
Joined: 2009.04
Post: #1
OK I'm working on a physics function and I have an array of the following for the map:

[x1,y1,z1,x2,y2,z2,...]

And so on (The first nine items specify a triangle).

Considering I have an x and a z value, how would I find the closest point to these?

Thanks

~ Bring a Pen ~
Quote this message in a reply
⌘-R in Chief
Posts: 1,265
Joined: 2002.05
Post: #2
If you only have two coordinates, you're looking at a line. Several points could be equally close to that line.

The distance is easily calculated by "the distance formula."

http://en.wikipedia.org/wiki/Distance
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #3
I dont understand the problem exactly, but you might be interested in this http://softsurfer.com/Archive/algorithm_...m_0106.htm

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #4
Also not quite sure what you are after exactly. Do you mean that you would be dropping the z-coordinate when searching? Is this a case where you have a number of objects on the screen in 3D space and are trying to find the one clicked on after projecting it to the 2D screen?

If performance is not an issue (you aren't doing this thousands of times per frame with thousands of points), then simply do a linear search for the closest point.

Something like this:
Code:
closest_dist = dist(point, points[0])
closest_index = 0

for(int i=1; i<number_of_points; i++){
  d = dist(point, points[i])
  if(d < closest_dist){
    closest_dist = d
    closest_index = i
  }
}

For more information on better, but more complicated algorithms:
http://en.wikipedia.org/wiki/Nearest_neighbor_search

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #5
I was using it for a collision detection/physics function:

Finds the nearest vertex on the map to the players (x,z) then sets the players y to the y of the vertex. See?

Skorche's answer is really what I'm wanting, but performance is kind of an issue. I have a large (v and f) map. I was wondering also if I could somehow find out which points it's definetly not out of the array and don't do the test on those. Like if the player is at 0,0 there is no point checking mapw,mapy?

~ Bring a Pen ~
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #6
Oooohhhh. So it's like a heightfield for a terrain, but without a regular grid? In that case I would turn your heightfield into a regular grid and just interpolate the height values.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #7
Quote:but without a regular grid
I think I know what you mean, and the main map is a regular grid (From the top it's a grid) but the trees, walls, and houses are not.

Quote:just interpolate the height values.
But from what? I have the normals/faces as an array too.

~ Bring a Pen ~
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #8
Just set up some space partitioning for the static triangles, eg an octree or something similar.
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #9
What's space partitioning, and how would I use an octree?

~ Bring a Pen ~
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #10
mikey Wrote:What's space partitioning, and how would I use an octree?

Wikipedia is always a good place to start:
http://en.wikipedia.org/wiki/Space_partitioning

Spatial partitioning lets you split up your world into smaller chunks and organize them in such a way that you can query the objects in a space efficiently. There are a number of different data structures and algorithms to do this with different benefits. For a large scale game, it's pretty much mandatory to use some sort of partitioning in order to get efficient realtime collision detection and drawing.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #11
But how would that help me? My grid is not vertex-ordered.

~ Bring a Pen ~
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #12
A simple idea is to make an 2 dimensional array of squares, squares[100,100], so in squares [0,0] you will put the list of points with 0<x<1 and 0<z<1 , in squares[a,b] the list of points with a<x<a+1 and b<z<b+1 etc.

Then to find points close to x1,y1 you would first look only in squares[int(x1), int(y1)] and the squares around it (you'll need to figure out exactly which squares you must check to be sure that the closest point you found is indeed the closest)

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #13
Najdorf: That is a good idea, but i already have an array of verts. Why make another? I might make another...

~ Bring a Pen ~
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #14
You make another to reduce the time you need to compute the closest point, doh!

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #15
Well, turning it into a regular grid would be tricky and time-consuming, and may increase the vertex count by a large amount.

Najdorf:

I am both time and memory concious. Maybe more than need be, but this is a good habit IMO.

~ Bring a Pen ~
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  finding a training center - Heeeelp Glauter 1 3,079 Dec 26, 2011 12:30 PM
Last Post: zenkimoto
  Finding an object by name markhula 2 4,681 Mar 29, 2011 08:08 AM
Last Post: markhula
  Kind of a noob question - finding artwork within my .app?? Nethfel 2 2,921 Mar 8, 2010 08:00 AM
Last Post: AndyKorth
  Finding the height of a point on a given list of vertexes? mikey 10 5,545 Jan 4, 2010 05:36 AM
Last Post: mikey
  Finding Outer Vertices of Shapes Nick 18 8,855 Nov 27, 2006 07:01 AM
Last Post: Nick