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

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

I dont understand the problem exactly, but you might be interested in this http://softsurfer.com/Archive/algorithm_...m_0106.htm

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:

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

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?

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.

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.

Just set up some space partitioning for the static triangles, eg an octree or something similar.

What's space partitioning, and how would I use an octree?

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.

But how would that help me? My grid is not vertex-ordered.

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)

Najdorf: That is a good idea, but i already have an array of verts. Why make another? I might make another...

You make another to reduce the time you need to compute the closest point, doh!

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.