Skip to content

Distance Functions

Common metrics and distances from a point to a line or segment appear in clustering, physics, and geometry problems.

Euclidean

\[ d(p,q) = \sqrt{(p_x - q_x)^2 + (p_y - q_y)^2} \]

For only comparing distances, compare squared distances to avoid sqrt.

#include <cmath>
struct Point { double x, y; };

double dist2(const Point& a, const Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

double distEuclid(const Point& a, const Point& b) {
    return std::sqrt(dist2(a, b));
}

Manhattan (L1)

\[ d(p,q) = |p_x - q_x| + |p_y - q_y| \]
#include <cmath>
double distManhattan(const Point& a, const Point& b) {
    return std::fabs(a.x - b.x) + std::fabs(a.y - b.y);
}

Point to infinite line

Line through \(a, b\). Distance from \(p\):

\[ \frac{|\text{cross}(b-a,\, p-a)|}{|b-a|} \]
double distPointLine(const Point& p, const Point& a, const Point& b) {
    double cr = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
    double len = std::sqrt(dist2(a, b));
    return len < 1e-12 ? distEuclid(p, a) : std::fabs(cr) / len;
}

Point to segment \(ab\)

Clamp the projection of \(p\) onto the line onto the segment, then Euclidean distance to that clamped point.

double distPointSegment(const Point& p, const Point& a, const Point& b) {
    double dx = b.x - a.x, dy = b.y - a.y;
    double len2 = dx * dx + dy * dy;
    if (len2 < 1e-18) return distEuclid(p, a);
    double t = std::max(0.0, std::min(1.0,
        ((p.x - a.x) * dx + (p.y - a.y) * dy) / len2));
    Point proj{a.x + t * dx, a.y + t * dy};
    return distEuclid(p, proj);
}