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.

• DirkT: What is $n$ in Your application? Did You mean to write $(a+b)/2$ instead of $(a-b)/2$?
• Makogan: $n$ is the dimension of the problem and yes I made a typo there, thank you.
• D.W.: Please edit the question to incorporate all relevant information, including the definition of $n,ドル so people don't have to read the comments to understand what is being asked. Thank you.

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.