distance.md

   1 # Distance
   2
   3 Distance is a [measure](metric.md) of how far away from each other two [points](point.md) are. Most commonly distance refers to physical separation in space, e.g. as in distance of planets from the Sun, but more generally distance can refer to any kind of parameter space and in any number of [dimensions](dimension.md), e.g. the distance of events in time measured in seconds (1D distance) or distance of two text strings as the amount of their dissimilarity ([Levenshtein distance](levenshtein_distance.md)). Distances are very important in [computer science](compsci.md) and [math](math.md) as they allow us to do such things as [clustering](clustering.md), path searching, physics simulations, various comparisons, [sorting](sort.md) etc.
   4
   5 Distance is similar/related to [length](length.md), the difference is that distance is computed between two points while length is the distance of one point from some implicit origin. I.e. distance is computed between two [vectors](vector.md) while length is computed from just one vector.
   6
   7 There are many ways to define distance within given space. Most common and implicitly assumed distance is the **[Euclidean distance](euclidean_distance.md)** (basically the "straight line from point A to point B" whose length is computed with [ Euclidean Theorem](euclidean_theorem.md)), but other distances are possible, e.g. the [taxicab distance](taxicab_distance.md) (length of the kind of perpendicular path taxis take between points A and B in Manhattan, usually longer than straight line). Mathematically a space in which distances can be measured are called [metric spaces](metric_space.md), and a distance within such space can be any [function](function.md) *dist* (called a *distance* or *metric* function) that satisfies these [axioms](axiom.md):
   8
   9 1. *dist(p,p) = 0* (distance from identical point is zero)
  10 2. Values given by *dist* are never negative.
  11 3. *dist(p,q) = dist(q,p)* ([symmetry](symmetry.md), distance between two points is the same in both directions).
  12 4. *dist(a,c) <= dist(a,b) + dist(b,c)* (triangle inequality)
  13
  14 ## Approximations
  15
  16 Computing Euclidean distance requires multiplication and most importantly [square root](sqrt.md) which is usually a pretty slow operation, therefore many times we look for simpler [approximations](approximation.md). Note that a possible approach here may also lead through computing the distance normally but using a fast approximation of the square root.
  17
  18 Two very basic and rough approximations of Euclidean distance, both in 2D and 3D, are [taxicab](taxicab.md) (also Manhattan) and [Chebyshev](chebyshev.md) distances. Taxicab distance
  19 simply adds the absolute coordinate differences along each principal axis (*dx*, *dy* and *dz*) while Chebyshev takes the maximum of them. In [C](c.md) (for generalization to 3D just add one coordinate of course):
  20
  21 ```
  22 int distTaxi(int x0, int y0, int x1, int y1)
  23 {
  24   x0 = x1 > x0 ? x1 - x0 : x0 - x1; // dx
  25   y0 = y1 > y0 ? y1 - y0 : y0 - y1; // dy
  26
  27   return x0 + y0;
  28 }
  29
  30 int distCheb(int x0, int y0, int x1, int y1)
  31 {
  32   x0 = x1 > x0 ? x1 - x0 : x0 - x1; // dx
  33   y0 = y1 > y0 ? y1 - y0 : y0 - y1; // dy
  34
  35   return x0 > y0 ? x0 : y0;
  36 }
  37 ```
  38
  39 Both of these distances approximate a circle in 2D with a square or a sphere in 3D with a cube, the difference is that taxicab is an upper estimate of the distance while Chebyshev is the lower estimate. For speed of execution ([optimization](optimization.md)) it may also be important that taxicab distance only uses the operation of addition while Chebyshev may result in [branching](branch.md) (*if*) in the max function which is usually not good for performance.
  40
  41 A bit more accuracy can be achieved by averaging the taxicab and Chebyshev distances which in 2D approximates a circle with an 8 segment polygon and in 3D approximates a sphere with 24 sided [polyhedron](polyhedron.md). The integer-only [C](c.md) code is following:
  42
  43 ```
  44 int dist8(int x0, int y0, int x1, int y1)
  45 {
  46   x0 = x1 > x0 ? x1 - x0 : x0 - x1; // dx
  47   y0 = y1 > y0 ? y1 - y0 : y0 - y1; // dy
  48
  49   return (x0 + y0 + (x0 > y0 ? x0 : y0)) / 2;
  50 }
  51 ```
  52
  53 { The following is an approximation I came up with when working on [tinyphysicsengine](tpe.md). While I measured the average and maximum error of the taxi/Chebyshev average in 3D at about 16% and 22% respectively, the following gave me 3% and 12% values. ~drummyfish }
  54
  55 Yet more accurate approximation of 3D Euclidean distance can be made with a 48 sided [polyhedron](polyhedron.md). The principle is following: take absolute values of all three coordinate differences and order them by magnitude so that *dx >= dy >= dz >= 0*. This gets us into one of 48 possible slices of space (the other slices have the same shape, they just differ by ordering or signs of the coordinates but the distance in them is of course equal). In this slice we'll approximate the distance linearly, i.e. with a [plane](plane.md). We do this by simply computing the distance of our point from a plane that goes through origin and whose normal is approximately {0.8728,0.4364,0.2182} (it points in the direction that goes through the middle of space slice). The expression for the distance from this plane simplifies to simply *0.8728 * dx + 0.4364 * dy + 0.2182 * dz*. The following is an integer-only implementation in [C](c.md) (note that the constants above have been converted to allow division by 1024 for possible [optimization](optimization.md) of division to a bit shift):
  56
  57 ```
  58 int32_t dist48(
  59   int32_t x0, int32_t y0, int32_t z0,
  60   int32_t x1, int32_t y1, int32_t z1)
  61 {
  62   x0 = x1 > x0 ? x1 - x0 : x0 - x1; // dx
  63   y0 = y1 > y0 ? y1 - y0 : y0 - y1; // dy
  64   z0 = z1 > z0 ? z1 - z0 : z0 - z1; // dz
  65
  66   if (x0 < y0) // order the coordinates
  67   {
  68     if (x0 < z0)
  69     {
  70       if (y0 < z0)
  71       { // x0 < y0 < z0
  72         int32_t t = x0; x0 = z0; z0 = t;
  73       }
  74       else
  75       { // x0 < z0 < y0
  76         int32_t t = x0; x0 = y0; y0 = t;
  77         t = z0; z0 = y0; y0 = t;
  78       }
  79     }
  80     else
  81     { // z0 < x0 < y0
  82       int32_t t = x0; x0 = y0; y0 = t;
  83     }
  84   }
  85   else
  86   {
  87     if (y0 < z0)
  88     {
  89       if (x0 < z0)
  90       { // y0 < x0 < z0
  91         int32_t t = y0; y0 = z0; z0 = t;
  92         t = x0; x0 = y0; y0 = t;
  93       }
  94       else
  95       { // y0 < z0 < x0
  96         int32_t t = y0; y0 = z0; z0 = t;
  97       }
  98     }
  99   }
 100
 101   return (893 * x0 + 446 * y0 + 223 * z0) / 1024;
 102 }
 103 ```
 104
 105 A similar approximation for 2D distance is (from a 1984 book *Problem corner*) this: *sqrt(dx^2 + dy^2) ~= 0.96 * dx + 0.4 * dy* for *dx >= dy >= 0*. The error is <= 4%. This can be optionally modified to use the closest power of 2 constants so that the function becomes much faster to compute, but the maximum error increases (seems to be about 11%). C code with fixed point follows (commented out line is the faster, less accurate version):
 106
 107 ```
 108 int dist2DApprox(int x0, int y0, int x1, int y1)
 109 {
 110   x0 = x0 > x1 ? (x0 - x1) : (x1 - x0);
 111   y0 = y0 > y1 ? (y0 - y1) : (y1 - y0);
 112
 113   if (x0 < y0)
 114   {
 115     x1 = x0; // swap
 116     x0 = y0;
 117     y0 = x1;
 118   }
 119
 120   return (123 * x0 + 51 * y0) / 128; // max error = ~4%
 121   //return x0 + y0 / 2;              // faster, less accurate
 122 }
 123 ```
 124
 125 TODO: this https://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml
 126
 127 ## See Also
 128
 129 - [freedom distance](freedom_distance.md)