Hi, I'm working on a project that requires me to navigate a 3d cartesian coordinate system. Most of this stuff I learned back in high school, but it's been so long since I've taken a math class, I'm having to relearn a bunch of it.
Does anyone have any experience with this?
Here's what I'm currently trying to figure out.
Imagine the 3d graph (x,y,z). Grid lines are at each integer, though since the line uses real numbers, it can cross a grid line where it doesn't intersect with another. I'm calling each 1x1x1 square a sector such that if you're at (1.5,6.3,5.2), you're in sector (1,6,5)....basically, the adjacent point nearest the origin. I'm trying to identify where the line passes into the next sector. Or, more importantly, if I know two(2) points, I want to identify each sector the line passes through. I was thinking of identifying each integer between the two points for each of (x,y,z), and then solving for each (easy in 2 dimensions, but much tougher in 3). I was hoping there's a better method for doing this. Any ideas?
Thanks
Jason
Navigating a 3D Cartesian coord. system
Moderator: General Moderators
Re: Navigating a 3D Cartesian coord. system
By using the canonical formula (not sure that's the one in English) for a line with 2 points defined, you can calculate every point of the line.
After that you can "trace" the line by using integer numbers for one of the coordinates and round() for the other two.
After that you can "trace" the line by using integer numbers for one of the coordinates and round() for the other two.
There are 10 types of people in this world, those who understand binary and those who don't
Re: Navigating a 3D Cartesian coord. system
Code: Select all
<?php
class GridLine3D
{
protected $pointA;
protected $pointB;
const X_AXIS = 0;
const Y_AXIS = 1;
const Z_AXIS = 2;
function __construct($pointA, $pointB)
{
$this->pointA = $pointA;
$this->pointB = $pointB;
}
protected function calcCoefficient($value, $axis)
{
return ($value - $this->pointA[$axis]) / ($this->pointB[$axis] - $this->pointA[$axis]);
}
protected function calcAxisValue($axis, $coeff)
{
return $coeff * ( $this->pointB[$axis] - $this->pointA[$axis] ) + $this->pointA[$axis];
}
protected function getGridAlignedAxisValue($axis, $coeff)
{
return intval(round($this->calcAxisValue($axis, $coeff)));
}
/**
*
* @param int $value
* @param int $axis GridLine3D::X_AXIS | GridLine3D::Y_AXIS | GridLine3D::Z_AXIS
* @return array Point
*/
public function calcGridAlignedPoint($value, $axis)
{
$coeff = $this->calcCoefficient($value, $axis);
$x = $axis == self::X_AXIS ? $value : $this->getGridAlignedAxisValue(self::X_AXIS, $coeff);
$y = $axis == self::Y_AXIS ? $value : $this->getGridAlignedAxisValue(self::Y_AXIS, $coeff);
$z = $axis == self::Z_AXIS ? $value : $this->getGridAlignedAxisValue(self::Z_AXIS, $coeff);
return array
(
self::X_AXIS => $x,
self::Y_AXIS => $y,
self::Z_AXIS => $z,
);
}
}
$line3d = new GridLine3D(array(6, 9, 4), array(3, 7, 2));
for ($z = -10; $z < 11; $z++)
{
echo implode(', ', $line3d->calcGridAlignedPoint($z, GridLine3D::Z_AXIS)) . "\n";
}
There are 10 types of people in this world, those who understand binary and those who don't
Re: Navigating a 3D Cartesian coord. system
VladSun,
Thanks for the response. I tried it out, but with the example you give, the x & y values remain constant while z progresses with the for loop. I've been trying this myself, using trigonometry. Unfortunately, it's been 20 years since I've taken trig, so I'm having to relearn all of this.
My thought, however is to handle it as follows:
1. Break into 2 planes (x,y & x,z).
2. Determine the next axis cross, and at what point that ocurrs.
To do this, I'd calculate the length of the hypotenuse of the triangle formed on the xy plane, calculating where it crosses x and where it crosses y. Then, the same for the xz plane, where it crosses z.
3. Once I know this, I'd pick the shortest of the 3, and use that to calculate the next coordinate set.
4. I'd repeat step 2 until I reach the destination coordinates.
Hopefully I'll have time to tackle this this weekend. If you, or anyone else have any thoughts on how to tackle this, feel free to help me out.
Thanks
Jason
Thanks for the response. I tried it out, but with the example you give, the x & y values remain constant while z progresses with the for loop. I've been trying this myself, using trigonometry. Unfortunately, it's been 20 years since I've taken trig, so I'm having to relearn all of this.
My thought, however is to handle it as follows:
1. Break into 2 planes (x,y & x,z).
2. Determine the next axis cross, and at what point that ocurrs.
To do this, I'd calculate the length of the hypotenuse of the triangle formed on the xy plane, calculating where it crosses x and where it crosses y. Then, the same for the xz plane, where it crosses z.
3. Once I know this, I'd pick the shortest of the 3, and use that to calculate the next coordinate set.
4. I'd repeat step 2 until I reach the destination coordinates.
Hopefully I'll have time to tackle this this weekend. If you, or anyone else have any thoughts on how to tackle this, feel free to help me out.
Thanks
Jason
Re: Navigating a 3D Cartesian coord. system
Except for dividing the planes it sounds a bit like the 3d version of this algorithm used in graphic accelerators:
http://en.wikipedia.org/wiki/Bresenham% ... _algorithm
Maybe you could rewrite D to include the Z,Zo points and adjust the algorithm. Here's a C version of the 3D version of this algorithm:
http://www.luberth.com/plotter/line3d.c.txt.html
Or you might try rewriting the line in parametric form which allows to to sweep one variable.
http://en.wikipedia.org/wiki/Bresenham% ... _algorithm
Maybe you could rewrite D to include the Z,Zo points and adjust the algorithm. Here's a C version of the 3D version of this algorithm:
http://www.luberth.com/plotter/line3d.c.txt.html
Or you might try rewriting the line in parametric form which allows to to sweep one variable.
Re: Navigating a 3D Cartesian coord. system
Huh? Did my example usage give you the "x-y-constant" results? If no, I think your X,Y coordinates have much lower grow rate than your Z coordinate, thus the round function makes them "integer constants". You may try using the X or the Y, instead of Z in the loop.MythX wrote:VladSun,
Thanks for the response. I tried it out, but with the example you give, the x & y values remain constant while z progresses with the for loop.
There are 10 types of people in this world, those who understand binary and those who don't
Re: Navigating a 3D Cartesian coord. system
I think that was the problem. I ended up getting this done, but went a different route.VladSun wrote:Huh? Did my example usage give you the "x-y-constant" results? If no, I think your X,Y coordinates have much lower grow rate than your Z coordinate, thus the round function makes them "integer constants". You may try using the X or the Y, instead of Z in the loop.MythX wrote:VladSun,
Thanks for the response. I tried it out, but with the example you give, the x & y values remain constant while z progresses with the for loop.
I identified all the integers for each of x,y and z, then looped through each, using basic math (y=mx + b) to solve for the other 2 coordinates. Had to put some code in to kick out duplicates, and then sorted the array by distance to destination. Thought it would bog down, but actually performs quite well, plus keeps the precision such that every value is actually on the line, not just rounded to the nearest point where the grids intersect.
Thanks for all your help, I feel like I'm back in the 10th grade.......Math is fun.
Thanks
Jason