Returns the point on a line segment nearest to a given point

nearest_point_on_line_segment_to_point.go

// NearestPointOnLineSegmentToPoint returns the point on a segment closest to a given point.
// |------------- o ------|
// P1             |       P2
//                .P3
// The equation of a line defined through two points P1 (x1,y1) and P2 (x2,y2) is P = P1 + u (P2 - P1)
// The point P3 (x3,y3) is closest to the line at the tangent to the line which passes through P3,
// that is, the dot product of the tangent and line is 0, thus (P3 - P) dot (P2 - P1) = 0
// Substituting the equation of the line gives [P3 - P1 - u(P2 - P1)] dot (P2 - P1) = 0
// Solving this gives the value of u:
// u = (x3 - x1)(x2 - x1) + (y3 - y1)(y2 - y1) / ||p2 - p1|| ^ 2
// Substituting this into the equation of the line gives the point of intersection (x,y) of the tangent as
// x = x1 + u (x2 - x1)
// y = y1 + u (y2 - y1)
func NearestPointOnLineSegmentToPoint(p3 point, segment segment) (point, error) {
	p1, p2 := segment.getEndpoints()
	
	xDelta := p2.X - p1.X
	yDelta := p2.Y - p1.Y

	if xDelta == 0 && yDelta == 0 {
		return point{}, errors.New("end points cannot be coincident")
	}

	u := ((p3.X-p1.X)*xDelta + (p3.Y-p1.Y)*yDelta) / (xDelta*xDelta + yDelta*yDelta)

	var nearestPoint point
	if u < 0 {
		nearestPoint = p1
	} else if u > 1 {
		nearestPoint = p2
	} else {
		nearestPoint = point{
			X: p1.X + u*xDelta,
			Y: p1.Y + u*yDelta,
		}
	}

	return point{X: nearestPoint.X, Y: nearestPoint.Y}, nil
}

type point struct {
	X float64
	Y float64
}

type segment struct {
	p1 point
	p2 point
}

func (s segment) getEndpoints() (point, point) {
	return s.p1, s.p2
}