No JavaScript → no output and no interactivity.

Point distance: hypot — Smooth CoffeeScript

This literate program is interactive in its HTML5 form. Edit a CoffeeScript segment to try it. You can see the generated JavaScript as you modify a CoffeeScript function by typing ‘show name’ after its definition.

Point distance algorithm

Warning! This snippet is about calculating the distance between two points — not something you would normally worry about. It is a fundamental calculation that can be used in other algorithms such as ‘nearest neighbor’.

A point is any object that implements x and y properties. Here defined as a class.

class Point
constructor: (@x, @y) ->
draw: (ctx) -> ctx.fillRect @x, @y, 1, 1
toString: -> "(#{@x}, #{@y})"

Euclidean distance

The euclidean distance between two points is (x1-x2)2+(y1-y2)2. Which can be written as a2+b2 where a=x1-x2 and b=y1-y2.

euclidean = (p1, p2) ->
[a, b] = [p1?.x - p2?.x, p1?.y - p2?.y]
Math.sqrt Math.pow(a, 2) + Math.pow(b, 2)

This is a classical algorithm based on the Pythagorean theorem.

Source

 

Improved precision calculation

Mathematically the euclidean calculation is correct and in normal use it will work. However for very large and very small numbers its results are imprecise — more imprecise than they have to be. This is a consequence of the difference between numbers in mathematics and computer floating point numbers. The precision of the results are limited due to the square of the differences, the square causes overflow or underflow to occur at the square root of the machine precision. Fortunately some clever person found that expressing the calculation in another way can improve upon this situation, see Wikipedia hypot.

a2+b2 = a2(1+(ba)2) = a1+(ba)2

hypot = (a, b) ->
if a is 0
Math.abs b
else
Math.abs(a) * Math.sqrt 1 + Math.pow b/a, 2
hypotenuse = (p1, p2) ->
[a, b] = [p1?.x - p2?.x, p1?.y - p2?.y]
hypot a, b

Polar coordinates

As described in Wikipedia hypot, the hypot function can also be used to convert to polar coordinates.

polar = (p) ->
[x, y] = [p.x, p.y]
r = hypot x, y
θ = Math.atan2 y, x
[r, θ]
show 'Distance from (0, 0), angle in 2π radians'
show polar new Point 1, 1

Edge case tests

Testing with some exceptional values is a good way to check that the function behave as intended.

show "euclidean vs hypotenuse"
p1 = p2 = undefined
show "#{euclidean p1, p2} vs #{hypotenuse p1, p2}"

p1 = new Point 0, 0
p2 = new Point 0, 0
show "#{euclidean p1, p2} vs #{hypotenuse p1, p2}"

p1 = new Point 1e-200, 1e-200
p2 = new Point 2e-200, 2e-200
show "#{euclidean p1, p2} vs #{hypotenuse p1, p2}"

p1 = new Point 1e200, 1e200
p2 = new Point 2e200, 2e200
show "#{euclidean p1, p2} vs #{hypotenuse p1, p2}"

QuickCheck

More comprehensive testing can be performed with QuickCheck. It is a test method where the properties of a function are described and data is generated to see if the properties hold. It is suitable for testing algorithms (in game logic and graphics) and is introduced in Smooth CoffeeScript Functions. There is also an interface reference.

How to

You can find some support code in the solution below. It can be used with qc.js to run QuickCheck with the standalone CoffeeScript compiler.

Source

Test cases

This test says that the hypot function is expected to return the same result as the euclidean. The euclidean is assumed to be correct for the usually generated arbInt numbers.

declare 'same results for normal range numbers',
[arbInt, arbInt, arbInt, arbInt],
(c, x1, y1, x2, y2) ->
p1 = new Point x1, y1
p2 = new Point x2, y2
d1 = euclidean p1, p2
d2 = hypotenuse p1, p2
diff = d1 - d2
epsilon = 1e-10
c.assert -epsilon < diff < epsilon

The next tests say that the hypot function is expected to return different results for large numbers. There are different ways of doing so.

arbBig = arbRange 1e155, 1e165
declare 'different results for big range numbers',
[arbBig, arbBig, arbBig, arbBig],
(c, x1, y1, x2, y2) ->
p1 = new Point x1, y1
p2 = new Point x2, y2
d1 = euclidean p1, p2
d2 = hypotenuse p1, p2
diff = Math.abs d1 - d2
epsilon = 1e-10
c.assert diff > epsilon
declare 'different results for large numbers',
[arbInt, arbInt, arbInt, arbInt, arbInt, arbInt],
(c, x1, y1, e1, x2, y2, e2) ->
p1 = new Point x1*Math.pow(10, e1), y1*Math.pow(10, e1)
p2 = new Point x2*Math.pow(10, e2), y2*Math.pow(10, e2)
d1 = euclidean p1, p2
d2 = hypotenuse p1, p2
diff = Math.abs d1 - d2
c.guard diff > 1
exp = 9
c.assert e1 < -exp or e1 > exp or e2 < -exp or e2 > exp

The results will vary on each run as the data is generated. The floating point precision is implementation dependent.

do test

Formats CoffeeScript Markdown PDF HTML

License Creative Commons Attribution Share Alike by autotelicum © 2554/2011