Point crossing path

Question

I have a problem in which i need to alert when a point (obviously in movement) had crossed a line-path, a line path is complex collection of lines (y=ax+b).

Postulation -

• I do not know from which side the "Point" will cross the line.
• The line-path can be very complex and contain many lines.

For example -

1. What is the best approach to this problem?
2. Does anyone know if there is algorithm for that?

Answer 1

Finding line / path intercept

There is no simple solution if you consider that the line can come from any direction and that the line segments in the path can be any configuration. You will need to check each path segment against the line

The image below shows three lines AD, BD, and CD. Lines AD and CD intercept the path at 3 locations and BD at one.

For each line segment the point closest to the start of the line segment is the point you are looking for.

To find these points we must first define a point and line segment.

// point
p.x = ?
p.y = ?

// line segment contains start and end points p1, p2
l.p1 = {x, y}
l.p2 = {x, y}

Finding smallest unit dist on line segment

Compute the unit distance on the line segment that each path segment intercepts if any. The path segment that intercepts the line segment at the smallest unit distance >= 0 will be the first point of intercept. The one you are looking for.

Pseudo-code

The following shows the steps required. Checking each path segment against the line segment. First check if the path is not parallel to the line segment. If so check if the intercept is on the path segment. If so check if the intercept is on the line segment and is the closest intercept to the line start so far found.

// l is line segment   
interceptFound = false   // Semaphore to indicate point found
minUnitDist = 1          // unit dist of intercept
ix = 0                   // intercept point
iy = 0 
pathSeg                  // if needed the path segment that intercepted 

vx1 = l.p2.x - l.p1.x    // vector of line segment
vy1 = l.p2.y - l.p1.y

for each pathSegment           // p path segment
    vx2 = p.p2.x - p.p1.x      // vector of path segment
    vy2 = p.p2.y - p.p1.y
    crossProd = vx1 * vy2 - vy1 * vx2
    if crossProd != 0          // Check lines are not parallel    
        vx3 = l.p1.x - p.p1.x  // Vector from start of l to start of p
        vy3 = l.p1.y - p.p1.y
        unit = (vx1 * vy3 - vy1 * vx3) / crossProd     // unit dist on path segment 
        if unit >= 0 && unit <= 1                      // Code Point A. 
            unit = (vx2 * vy3 - vy2 * vx3) / crossProd // unit dist on line segment
            if unit >= 0 && unit <= minUnitDist        // Is the intercept closest to start
                interceptFound = true
                minUnitDist = unit 
                pathSeg = p                            // store intercepting path segment



if interceptFound  // Was a intercept found
    ix = l.p1.x + vx1 * minUnitDist  // Calculate intercept point
    iy = l.p1.y + vy1 * minUnitDist

You can pre-compute the vector for each path segment vx2, vy2 in the above example to save a little time (if the path does not change over time)

You could also exit the loop early if the minUnitDist is zero

This is relatively quick and does not need complex data structures. Most path segments will be culled at // Code Point A

AABB check

Axis Aligned Bounding Box check

If the number of path segments are very high you can perform an AABB to avoid some of the math in the above example. This will only be a benefit if the path points do not change over time and that you calculate the bounding box once at the start for each path segment

Pseudo-code AABB check

// l is a line segment
l.left   = min(l.p1.x, l.p2.x)
l.right  = max(l.p1.x, l.p2.x)
l.top    = min(l.p1.y, l.p2.y)
l.bottom = max(l.p1.y, l.p2.y)

Then to check if two segments may intercept

// l and p are line segs with bounding boxes calculated
if l.left > p.right || l.right < p.left || l.top > p.bottom || l.bottom < p.top
    // line segments do not intercept
else 
    // Line segments may intercept

More bounding boxes and Quad trees

If you still find that the solution is too slow you can divide the path segments into related (close together connected) groups and do the AABB test against each group before checking the path segments in the group.

Further you could consider using a quad tree to store path segments to further reduce the number of path segments you need to test the line against.