Algorithm for Determining Point Position on Line Segment Using Vector Operations

Geometric Problem Background and Definition

In two-dimensional plane geometry, given two points a and b that define a line segment, determining whether a third point c lies on this segment is a fundamental yet important computational geometry problem. This problem has wide applications in computer graphics, geographic information systems, and game development.

Core Mathematical Principles

The key to solving this problem lies in vector operations. Let vector ab = b - a and vector ac = c - a. The determination process consists of two steps:

Collinearity Detection

First, it must be determined whether point c is collinear with points a and b. This can be achieved by calculating the cross product of vectors ab and ac. In two-dimensional space, the absolute value of the cross product represents the area of the parallelogram spanned by these two vectors. When the cross product is zero, it indicates that the two vectors are collinear, meaning the three points are collinear.

crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)

For floating-point calculations, due to precision issues, comparison with a small threshold epsilon is typically required:

if abs(crossproduct) > epsilon:
    return False

Positional Relationship Determination

Even if three points are collinear, point c might lie on the extension of line segment ab. Therefore, further checking is needed to determine whether point c is actually between a and b. This can be accomplished through dot product operations.

The dot product dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y) * (b.y - a.y) reflects the projection length of vector ac in the direction of vector ab. If the dot product is less than 0, it indicates point c is before point a; if the dot product is greater than the square of the length of vector ab, it indicates point c is after point b. Only when the dot product is between 0 and the square of the length of vector ab does point c lie on the segment.

squaredlengthba = (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y)
if dotproduct < 0 or dotproduct > squaredlengthba:
    return False

Complete Algorithm Implementation

Based on the above principles, here is the complete Python implementation:

def is_between(a, b, c, epsilon=1e-10):
    """
    Determine whether point c lies on line segment ab
    :param a: Starting point with x and y attributes
    :param b: Ending point with x and y attributes
    :param c: Point to be determined with x and y attributes
    :param epsilon: Floating-point comparison threshold
    :return: True if c is on segment ab, otherwise False
    """
    # Calculate cross product for collinearity detection
    crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)
    if abs(crossproduct) > epsilon:
        return False
    
    # Calculate dot product to check positional relationship
    dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y) * (b.y - a.y)
    if dotproduct < 0:
        return False
    
    squaredlengthba = (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y)
    if dotproduct > squaredlengthba:
        return False
    
    return True

Method Comparison and Discussion

Besides the vector operation-based method described above, other determination methods exist, each with limitations.

Distance Summation Method

An intuitive approach is to check whether distance(a,c) + distance(c,b) == distance(a,b) holds. Theoretically, if point c lies on the segment, this equality holds. However, due to floating-point precision issues, direct equality comparison is generally unreliable and requires tolerance. Additionally, this method requires three square root operations, resulting in lower computational efficiency.

Coordinate Range Checking Method

Another method involves verifying that point c's coordinates fall within the range of points a and b after confirming collinearity. This method works for integer coordinates but faces precision challenges with floating-point numbers. Special handling is needed to avoid division by zero errors when the segment is parallel to coordinate axes.

Numerical Stability Considerations

In practical applications, especially when dealing with floating-point coordinates, numerical stability is crucial. Cross product and dot product calculations may be affected by rounding errors. By introducing an epsilon threshold, misjudgments caused by minor errors can be avoided. The choice of threshold should be adjusted based on the precision requirements of specific application scenarios.

Application Scenarios and Extensions

This algorithm is not only applicable to two-dimensional planes but can also be extended to three-dimensional space. In three dimensions, the cross product is used to detect whether a point lies on a line, while the comparison of dot product and squared vector length still applies. Furthermore, the algorithm can be optimized, such as by precomputing and caching values related to vector ab to improve performance when multiple determinations on the same segment are needed.

In summary, the vector operation-based method using cross product and dot product provides an efficient and stable way to determine whether a point lies on a line segment. By understanding its mathematical principles and properly handling numerical precision issues, this geometric determination problem can be reliably solved in various practical applications.