Fast way to find the intersection of a set of discrete positions.

I have a 2xN matrix containing the x- and z-positions (first row is x-positions and second row is z-positions) for a wavefront at time "t". Occasionally the wavefront may cross itself, as shown in the figure. When this happens, I need to delete all of the points that trail behind the primary wavefront (i.e. i need to delete points 5-8 in my figure). Note that in general there might be more than one of these "crossings" along the wavefront.

If I had an analytical expression (e.g. a parametric equation) for the wavefront then the solution would be relatively simple: just find where the parametric curve crosses itself, and delete the points in between the crossings. Unfortunately I do not have a parametric equation and am limited to dealing only with discrete data points. Currently the best method I can think of is to do something like this:

np = ... % number of points
for ip = 2:np
    % Step 1: Create a straight line between point 'ip' and 'ip-1'
    for IP = 2:np
        % Step 2: Create a straight line between point 'IP' and 'IP-1'
        if % check if the lines from step 1 & 2 intersect
            % Step 3: Delete all points in the matrix occuring between the intersection of the 2 lines
        end
    end
end

I think this method will work. However, I will need to do this procedure many times (tens of thousands of times, with 500+ data points on each wavefront) and I am worried that my approach may be too time consuming. Is there any built-in functions or more efficient approaches for solving my problem?

Thanks!

Answer 1

[Image Analyst]

Steve Eddins discussed that in his image processing blog last month: http://blogs.mathworks.com/steve/2016/04/12/intersecting-curves-that-dont-intersect/

[Landon Chad]

This doesn't really help with my problem. His problem has the data spaced regularly on a grid, and aims to find the intersection of 2 different curves. My problem has irregularly spaced data, and I am trying to find the intersection of a single curve with itself.

My problem essentially boils down to finding the intersection of a parametric curve with itself. However, the equation of my parametric curve is unknown and cannot be estimated. All that I have is the position of the parametric curve at a finite number of locations (and I know the order at which those points fall along the curve).

[Image Analyst]

If it's parametric you should have parameters. If you don't, then it's just a curve of digital data and I think Steve's solution should apply, even if you have only a few vertex points and have to join them with the Bresenham Line Algorithm