Fast way to find the intersection of a set of discrete positions.
12 views (last 30 days)
Show older comments
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!
0 Comments
Answers (1)
Image Analyst
on 11 May 2016
Steve Eddins discussed that in his image processing blog last month: http://blogs.mathworks.com/steve/2016/04/12/intersecting-curves-that-dont-intersect/
2 Comments
Image Analyst
on 12 May 2016
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
See Also
Categories
Find more on Mathematics and Optimization in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!