Detect when a 2D moving object crosses its own path?

Question

How can I detect when a 2D moving object has crossed its own path? enter image description here

I store the path as an array of points based on the plane's previous positions.
Pseudo-code or any programming language can be used to describe a solution.

Here's my code I've tried already - it detects a full 360 loop. I think I need a different approach.

    CGFloat angleDiff = angleCurr - lastAngleRecorded;
    lastAngleRecorded = angleCurr;

    // Ensure -180 < angleDiff < 180
    angleDiff = angleDiff > M_PI ? angleDiff - (M_PI*2) : angleDiff;
    angleDiff = angleDiff < -M_PI ? angleDiff + (M_PI*2) : angleDiff;

    // Reset tracking of the loop of the plane's angle exceeds (turns too sharply) or falls below the limits

    if(fabsf(angleDiff) < angleDiffMinAllowed || fabsf(angleDiff) > angleDiffMaxAllowed) {
        if(++ringFaultCount >= ringFaultCountMax) {
            [self resetTracking];
            return;
        }
    }

    ringFaultCount = 0;

    // Add plane position to ring polygon
    [ringPoints addObject:[NSValue valueWithCGPoint: ccp(targetPlane.position.x, targetPlane.position.y)]];


    // Add angleDiff to angleTotal
    angleTotal += angleDiff;

    // Completed loop?
    if(fabsf(angleTotal) >= M_PI * 2.f) {

        [self resetTracking];

        if(isRingJoined){
            CCLOG(@"%@ RING COMPLETE", NSStringFromSelector(_cmd));
        }

        return;
    }

I've tried measuring the angle of the plane as it flies, to detect a full loop when 360 degrees is reached... — invisible squirrel, Dec 13 '12 at 19:55
@dene simply looking at angle won't work if object is eg. spiraling. — Nicu Stiurca, Dec 13 '12 at 20:15
I store the path as an array of points based on the plane's previous positions. — invisible squirrel, Dec 13 '12 at 20:16
It would help if you posted sample code of what you have tried. As written, the question is very vague. — Aaron Kurtzhals, Dec 13 '12 at 20:19
Think of two points as a line segment, you can then check if any set of two line segments (four adjacent points) intersect.... for the math see http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect — renab, Dec 13 '12 at 20:22
Hm, brute force, assuming the path is a collection of points, through which we for simplicity's sake draw straight lines, it's detecting wether any line-segment `(x(n),y(n))-(x(n+1),y(n+1))` crosses a line-segment `(x(m),y(m))-(x(m+1),y(m+1))`. Then it's [some calculation](http://www.mathopenref.com/coordintersection.html). It does not seem very optimal though. — Wrikken, Dec 13 '12 at 20:23
@Wrikken, while it may not be optimal, there are things you can do to optimize, for example: `if (x11 and x12) < (x21 and x22) then no intersection` and you could do the same to the y values to avoid running the two segments through the algorithm to determine intersection. Also if any one point from one segment has the same position as a point from the other segment, you know there is an intersection. — renab, Dec 13 '12 at 20:40
Hm, indeed, some optimization can be done on it.[wikipedia seems to advocate](http://en.wikipedia.org/wiki/Line_segment_intersection) the `Shamos–Hoey algorithm`, which I have yet to find an example of... — Wrikken, Dec 13 '12 at 20:56
[an extension to the Shamos-Hoey](http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm) algorithm appears to do just what @dene needs... run the algorithm each time you move the plane to detect if there is an intersection — renab, Dec 13 '12 at 21:06

score 1 · Accepted Answer · answered Jan 20 '13 at 18:20

I also had the problem, I solved it by making a straight line in a coordinate system:

y = mx+q±tolerance

Let me explain: The line is the tangent of the curve at the point you check if there is a collision this is the line the "aircraft" followed in that point. The tolerance will make the line move a litlle bit up and also one a little bit down. so you get 2 parralel lines witch can be seen as boundarys. you also have to make a tolerance on the x-axis

The m is the direction of the line, its: tan(angle), the angle is the angle with the x-axis.

If all that is setup than you have to do this:

if(y_point < mx+q+tolerance && y_point> mx+q-tolerance && x_points > x-tolerance && x_point< x+tolerance
{
// some code
}

Detect when a 2D moving object crosses its own path?

1 Answers1