Point Bw Points

Here’s another short post on a problem I solved today. Suppose you have a point and want to see if it’s between two other points. If you’re working in a 2D space, you can use a solution along the lines of this one from Bryce Boe, but it’s not obvious how it would generalize to higher dimensions.

So I thought I’d take a different approach: what do we mean when we say a point is “between two points?” It can help to visualize the set of points between, say, (0,0) and (1,1):

INEQ1

We can see here how “between two points” is equivalent to “between two lines”, or, more generally, “between two hyperplanes.” Further, both of these hyperplanes are defined by the same normal vector: the one that runs between the two ’endpoints’ we’re checking! So, we want to define a linear inequality $\min(f(l), f(r)) < f(x) < \max(f(l), f(r))$, where $l$ and $r$ are our endpoints, and $f$ is somehow derived from our difference vector.

Fortunately, we can actually derive $f$ by inspection if we remember from algebra class that plane ineqalities can be easily defined by their normals! For instance, if your normal vector is $(1,2)$ or $x + 2y$, then the plane inequality is $c_{min} < x + 2y < c_{max}$. We can find the values for $c_{min}$ and $c_{max}$ by just plugging in the endpoints. So we arrive at a very simple method:

import numpy as np

def is_between(x, endpts):
	l, r = endpts
	diff = r - l
	cl, cr = np.dot(l, diff), np.dot(r, diff)
	f_x = np.dot(x, diff)
	if cl < cr:
		return cl < f_x < cr
	else:
		return cr < f_x < cl

But we can actually do better by taking advantage of the identity:

$$\cos(\angle(a, b)) = \dfrac{a \cdot b}{|a||b|}$$

If the cosine of the angle between the vectors from each endpoint to:

1. The other endpoint
2. The point of interest

Is positive, then the point of interest is between the endpoints! Since we only care whether it’s positive, we can actually drop the denominator and get an ultra-minimal:

import numpy as np

def is_between(x, endpts):
	l, r = endpts
	x = np.asarray(x)
	l, r = np.asarray(l), np.asarray(r)
	return np.dot(x-l, r-l) > 0 and np.dot(x-r, l-r) > 0

Not only did we make this way shorter, we also dropped a call to np.dot! We did this at the expense of up to 3 additional subtractions, but subtraction is way cheaper than multiplication.