Finding the closest point to (x1,y1) in array of [x1,y1,z1,x2...
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
[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 ~
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
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
Â©hâ‚¬ck Ã¸ut Âµy stuÆ’Æ’ Ã¥t ragdollsoft.com
New game in development Rubber Ninjas  Mac Games Downloads
Also not quite sure what you are after exactly. Do you mean that you would be dropping the zcoordinate 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
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.
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?
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 ~
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:but without a regular gridI 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 ~
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?
~ Bring a Pen ~
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.
But how would that help me? My grid is not vertexordered.
~ Bring a Pen ~
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)
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
Najdorf: That is a good idea, but i already have an array of verts. Why make another? I might make another...
~ Bring a Pen ~
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
Well, turning it into a regular grid would be tricky and timeconsuming, 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.
Najdorf:
I am both time and memory concious. Maybe more than need be, but this is a good habit IMO.
~ Bring a Pen ~
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
finding a training center  Heeeelp  Glauter  1  4,412 
Dec 26, 2011 12:30 PM Last Post: zenkimoto 

Finding an object by name  markhula  2  5,941 
Mar 29, 2011 08:08 AM Last Post: markhula 

Kind of a noob question  finding artwork within my .app??  Nethfel  2  4,122 
Mar 8, 2010 08:00 AM Last Post: AndyKorth 

Finding the height of a point on a given list of vertexes?  mikey  10  7,946 
Jan 4, 2010 05:36 AM Last Post: mikey 

Finding Outer Vertices of Shapes  Nick  18  12,273 
Nov 27, 2006 07:01 AM Last Post: Nick 