Euflorium: The Eufloria Community

Eufloria => Eufloria Classic => Eufloria Classic Mods => Topic started by: annikk.exe on May 25, 2012, 06:23:24 PM

Title: Find the distance between two 3D coordinates
Post by: annikk.exe on May 25, 2012, 06:23:24 PM

This is something that I need to understand thoroughly in order to implement the 3D engine, so I'm gonna spit ball about this to straighten things out in my head.


As I recall, you can basically just use Pythagoras to do this, which makes it super easy.
Pythagoras is the rule that allows you to find the length of the third side of a right-angled triangle, if you know the length of the first two sides.
The fomula is a^2 + b^2 = c^2

c is the hypotenuse - the longest side of the triangle, and the side opposite the 90 degree right-angle.
a and b are the other sides.

So if we want to find c, we're going to need to do a little algebra.
We have:

c^2 =

We need:

c =


In order to transform c^2 into c, we take the square root.  But if we do it to one side of the equation, we must do it to the other too:

a^2 + b^2

becomes:

math.sqrt(a^2 + b^2)


So, rewritten, we have:



c = math.sqrt(a^2 + b^2)



So how do we use this to calculate the distance between 3D coordinates?


We start by getting our coords:



P0 = (1,2,3)
P1 = (7,9,5)


Now we work out the difference between the two coordinates in a component-wise fashion, producing three lengths:

dx = P1.x - P0.x
dy = P1.y - P0.y
dz = P1.z - P0.z


Now we have 3 lengths.
Lets take the first two, dx and dy, and these will be the two sides of our triangle:

c = math.sqrt(dx^2 + dy^2)


Now c represents a new side of a new triangle, the other side of it is dz.

So...

distance = math.sqrt(c^2 + dz^2)


Distance is now equal to the distance between the coordinates.


So to write that up in full code form:

Code: [Select]

function DistanceBetweenCoords(x0, y0, z0, x1, y1, z1)
dx = x1 - x0
dy = y1 - y0
dz = z1 - z0
c = math.sqrt(dx^2 + dy^2)
distance = math.sqrt(c^2 + dz^2)
return distance
end

Immediately we can see that it's possible to optimise this by removing the first square root, and keeping c in squared form for the subsequent calculation:

Code: [Select]

function DistanceBetweenCoords(x0, y0, z0, x1, y1, z1)
dx = x1 - x0
dy = y1 - y0
dz = z1 - z0
c = dx^2 + dy^2
distance = math.sqrt(c + dz^2)
return distance
end

For hilarity, we can compress the calculation to a single line:

Code: [Select]

function DistanceBetweenCoords(x0, y0, z0, x1, y1, z1)
distance = math.sqrt(((x1- x0)^2 + (y1-y0)^2) + (z1 - z0)^2)
return distance
end




Questions for anyone who bothered to read this:
1) Does this thing work the way I think it does..?
2) Any way to improve the efficiency?

Title: Re: Find the distance between two 3D coordinates
Post by: annikk.exe on May 25, 2012, 07:04:13 PM

Code: [Select]

function DistanceBetweenCoords(x0, y0, z0, x1, y1, z1)
dx = x1 - x0
dy = y1 - y0
dz = z1 - z0
c = dx^2 + dy^2
distance = math.sqrt(c + dz^2)
return distance
end
P0 = (1,2,3)
P1 = (7,9,5)

x0 = 1
y0 = 2
z0 = 3
x1 = 7
y1 = 9
z1 = 5


dx = x1 - x0 = 7 - 1 = 6
dy = y1 - y0 = 9 - 2 = 8
dz = z1 - z0 = 5 - 3 = 2

dx = 6
dy = 8
dz = 2

c = math.sqrt(6^2 + 8^2)
c = math.sqrt(36 + 64)
c = math.sqrt(100)
c = 10

distance = math.sqrt(c^2 + dz^2)
distance = math.sqrt(10^2 + 2^2)
distance = math.sqrt(100 + 4)
distance = math.sqrt(104)
distance = 10.198


Sounds about right...


Lets try an easy one, where the correct answer is obvious:


(4,4,4)
(4,4,8)

distance between them is going to be 4, yea?


Here goes:

dx = 0
dy = 0
dz = 4

c = math.sqrt(0^2 + 0^2)
c = 0

distance = math.sqrt(c^2 + dz^2)
distance = math.sqrt(0^2 + 4^2)
distance = math.sqrt(16)
distance = 4


Correct. :>

Title: Re: Find the distance between two 3D coordinates
Post by: Lost Seedling on May 25, 2012, 07:24:23 PM

1. Yes
2. Not that I see.

Title: Re: Find the distance between two 3D coordinates
Post by: annikk.exe on May 25, 2012, 07:33:57 PM

Sweet

Thanks for checking my work! :>

I think this problem is sorted.. onto the next problem.

Title: Re: Find the distance between two 3D coordinates
Post by: Pilchard123 on May 26, 2012, 01:14:39 AM

1. As has been said, yes.
2. That depends. If you just want to compare two distances C1 and C2, you can leave it a (C1)^2 and (C2)^2. If yuo actually want the distance, then I don't think there is a way.

Title: Re: Find the distance between two 3D coordinates
Post by: annikk.exe on May 26, 2012, 01:58:15 AM

Actually you might be onto something there Pilchard.  If I recall correctly, this function only needed to check which was closer.  It's not necessary to know the actual distance.

So I could leave it as a square.. :>

Code: [Select]

function DistanceBetweenCoords(x0, y0, z0, x1, y1, z1)
dx = x1 - x0
dy = y1 - y0
dz = z1 - z0
distancesquared = dx^2 + dy^2 + dz^2
return distancesquared
end

A distance comparison without a square root.  Awesome. :>

Title: Re: Find the distance between two 3D coordinates
Post by: annikk.exe on May 26, 2012, 03:05:59 AM

Implemented, works.  Is probably marginally faster.