Fast way to find the intersection of a set of discrete positions.
12 次查看(过去 30 天)
显示 更早的评论
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 个评论
回答(1 个)
Image Analyst
2016-5-11
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 个评论
Image Analyst
2016-5-12
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
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Mathematics and Optimization 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!