# PHP Developers Network

A community of PHP developers offering assistance, advice, discussion, and friendship.

 It is currently Mon Feb 24, 2020 10:07 pm

 All times are UTC - 5 hours

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Navigating a 3D Cartesian coord. systemPosted: Sun Aug 28, 2011 8:49 am
 Forum Commoner

Joined: Mon Jan 11, 2010 9:28 pm
Posts: 28
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

Top

 Post subject: Re: Navigating a 3D Cartesian coord. systemPosted: Mon Aug 29, 2011 4:58 pm
 DevNet Master

Joined: Wed Jun 27, 2007 9:44 am
Posts: 4313
Location: Sofia, Bulgaria
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.

_________________
There are 10 types of people in this world, those who understand binary and those who don't

Top

 Post subject: Re: Navigating a 3D Cartesian coord. systemPosted: Tue Aug 30, 2011 2:31 am
 DevNet Master

Joined: Wed Jun 27, 2007 9:44 am
Posts: 4313
Location: Sofia, Bulgaria
<?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

Top

 Post subject: Re: Navigating a 3D Cartesian coord. systemPosted: Sat Sep 03, 2011 1:01 pm
 Forum Commoner

Joined: Mon Jan 11, 2010 9:28 pm
Posts: 28
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

Top

 Post subject: Re: Navigating a 3D Cartesian coord. systemPosted: Sat Sep 03, 2011 3:53 pm
 DevNet Resident

Joined: Sun Jun 14, 2009 3:13 pm
Posts: 1146
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.

Top

 Post subject: Re: Navigating a 3D Cartesian coord. systemPosted: Sun Sep 04, 2011 2:55 pm
 DevNet Master

Joined: Wed Jun 27, 2007 9:44 am
Posts: 4313
Location: Sofia, Bulgaria

_________________
There are 10 types of people in this world, those who understand binary and those who don't

Top

 Post subject: Re: Navigating a 3D Cartesian coord. systemPosted: Sun Sep 04, 2011 6:44 pm
 Forum Commoner

Joined: Mon Jan 11, 2010 9:28 pm
Posts: 28

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: Google [Bot] and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

 Jump to:  Select a forum ------------------ General    General Discussion    Site News    PHPDN Suggestions    Tutorials Programming    PHP - Code    PHP - Security    PHP - Theory and Design    PHP - Frameworks    Javascript    Miscellaneous    Testing    Regex    Code Snippets    Coding Critique Design    HTML, CSS and other UI Design Technologies    Graphics    UI Design/Usability System    Databases    Linux    Installation and Configuration Business    The Enterprise    Job Hunt    Volunteer Work PHPDN Member Forums    PHPDN    PHPGD.com    Swift Mailer    Microsoft Open Q&A