Fast measurement of distance from point to mid segment?

Question

Say you have a segment defined by 2 points $a,b$ and a third point $p$. You want to know the distance from $p$ to the midpoint of the edge.

This is very straightforward:

$$d = \|\frac{a + b}{2} - p\|$$

I am wondering if it is possible to do this faster. Asymptotically you cannot do better than $O(n)$, where $n$ is the dimension in which the points are embedded, but I wonder if it is possible to reduce the constant in the complexity by reducing the amount of arithmetic computations needed to be done.

Answer 1

If you use an under-/overflow-safe euclidean norm implementation along the lines of LAPACK's dnrm2, your line-to-point distance function will look something like the following Scala code:

def linePointDistance( a: Array[Double], b: Array[Double], p: Array[Double] ): Double =

  require(a.length == b.length && a.length == p.length)

  var sum,mag = 0.0

  for i <- a.indices do
    var x = abs( p(i) - 0.5*(a(i) + b(i)) )
    if  x > mag then
      val s = mag/x
      sum *= s*s
      sum += 1
      mag  = x
    else if x != 0 then
      x /= mag
      sum += x*x
    end if
  end for

  if mag.isFinite then mag * sqrt(sum) else mag

end linePointDistance

You can see that for each of the $n$ dimensions You have:

• 1 division
• 1 multiplication
• A few additions/subtractions
• 1 shift (Division by 2)

A division is usually more expensive than a multiplication. A multiplication is more expensive than an addition/subtraction. Even an integer division is relatively cheap compared to a memory read (see itHare.com). This means that, arithmetically speaking, linePointDistance is already fairly efficient.

Pre-computing the mid-points of each line will reduce memory access by 1/3 and remove 1 addition, 1 subtraction and 1 shift operation. This may result in a small performance improvement, maybe ~5% to 15%.

Your best chance for performance improvement might be vectorization. With Java's experimental Vector API, You could vectorize the Scala code as follows:

import jdk.incubator.vector.DoubleVector
import jdk.incubator.vector.VectorOperators.{ADD, MAX}


def linePointDistanceVectorized( a: Array[Double], b: Array[Double], p: Array[Double] ): Double =

  val n = a.length
  require(n == b.length && n == p.length)

  val vSpec = DoubleVector.SPECIES_PREFERRED
  var vMag  = DoubleVector.zero(vSpec)
  val vLen = vSpec.length

  // Find Magnitude
  // --------------
  var   i = 0
  while i <= n-vLen do
    val ai = DoubleVector.fromArray(vSpec, a,i)
    val bi = DoubleVector.fromArray(vSpec, b,i)
    val pi = DoubleVector.fromArray(vSpec, p,i)
    val ci = ai.add(bi).mul(0.5).sub(pi).abs
    i += vLen
    vMag = vMag.max(ci)
  end while

  var mag = vMag.reduceLanes(MAX)

  while i < n do
    val ci = abs( p(i) - 0.5*(a(i) + b(i)) )
    mag = max(mag,ci)
    i += 1
  end while

  if mag == 0 || ! mag.isFinite then return mag

  // Compute Squared Sum
  // -------------------
  var vSum = DoubleVector.zero(vSpec)

  i = 0
  while i <= n - vLen do
    val ai = DoubleVector.fromArray(vSpec, a, i)
    val bi = DoubleVector.fromArray(vSpec, b, i)
    val pi = DoubleVector.fromArray(vSpec, p, i)
    val ci = ai.add(bi).mul(0.5).sub(pi).div(mag)
    i += vLen
    vSum = ci.mul(ci).add(vSum)
  end while

  var sum = vSum.reduceLanes(ADD)
  while i < n do
    var ci = p(i) - 0.5 * (a(i) + b(i))
    ci /= mag
    i += 1
    sum += ci*ci
  end while

  if mag.isFinite then sqrt(sum)*mag else mag

end linePointDistanceVectorized

According to my quick and dirty benchmarks, the vectorized code is up to 2x faster on a machine with AVX2 support. You might be able to gain another 2x-4x by using black assembly code magic, but it will be very time consuming, error prone and result in code that is unreadable, hard to port and not future proof.

Using other information about your specific application may allow for further, more frugal optimizations. If you perform many nearest point to line queries, for example, You could use spatial data structure, like a KD-Tree to massively improve performance.