## 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 ~
⌘-R in Chief
Posts: 1,277
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
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
Sage
Posts: 1,487
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   } }```

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.
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 ~
Sage
Posts: 1,487
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.
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 ~
Moderator
Posts: 869
Joined: 2003.01
Post: #8
Just set up some space partitioning for the static triangles, eg an octree or something similar.
Member
Posts: 281
Joined: 2009.04
Post: #9
What's space partitioning, and how would I use an octree?

~ Bring a Pen ~
Sage
Posts: 1,487
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.
Member
Posts: 281
Joined: 2009.04
Post: #11
But how would that help me? My grid is not vertex-ordered.

~ Bring a Pen ~
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
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 ~
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
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 ~