Thread Subject:

Merge line segments

Given 2 line segments (4 points), I want to return a third which consists of the the 2 points that are furthest apart. I have a function that works, but is there are way to do it more efficiently (faster) as this is a bottleneck in my code?

% Return the 2 points that are furthest apart
% Input and output line indexing is l(endpoint, x/y(1/2))
function l = merge_lines(l1, l2)
len_max =(l2(1,1) - l1(1,1))^2 + (l2(1,2) - l1(1,2))^2;
l(1,:) = l1(1,:);
l(2,:) = l2(1,:);
len = (l2(1,1) - l1(2,1))^2 + (l2(1,2) - l1(2,2))^2;
if len > len_max
    len_max = len;
    l(1,:) = l1(2,:);
    l(2,:) = l2(1,:);
end
len = (l2(2,1) - l1(1,1))^2 + (l2(2,2) - l1(1,2))^2;
if len > len_max
    len_max = len;
    l(1,:) = l1(1,:);
    l(2,:) = l2(2,:);
end
len = (l2(2,1) - l1(2,1))^2 + (l2(2,2) - l1(2,2))^2;
if len > len_max
    len_max = len;
    l(1,:) = l1(2,:);
    l(2,:) = l2(2,:);
end
len = (l1(2,1) - l1(1,1))^2 + (l1(2,2) - l1(1,2))^2;
if len > len_max
    len_max = len;
    l = l1;
end
len = (l2(2,1) - l2(1,1))^2 + (l2(2,2) - l2(1,2))^2;
if len > len_max
    l = l2;
end

% Try this:

function l = merge_lines(l1, l2)
l = [l1; l2];
p = (l*l');
d = diag(p);
d2 = bsxfun(@plus,d,d')-2*p;
[~, k] = max(d2(:));
l = l([mod(k-1,4)+1 ceil(k/4)],:);
end

% Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kfb5tu$b93$1@newscl01ah.mathworks.com>...
> % Try this:
>
> function l = merge_lines(l1, l2)
> l = [l1; l2];
> p = (l*l');
> d = diag(p);
> d2 = bsxfun(@plus,d,d')-2*p;
> [~, k] = max(d2(:));
> l = l([mod(k-1,4)+1 ceil(k/4)],:);
> end
>
> % Bruno

Thanks. That's a nice method for minimising code and works fine, but it's around 6 times slower than mine on average.

"Peter Bone" <peterbone@hotmail.com> wrote in message <kfb6hv$dqb$1@newscl01ah.mathworks.com>...
>
> Thanks. That's a nice method for minimising code and works fine, but it's around 6 times slower than mine on average.

Next suggestion:
If you have a bunch of quadri-points to be processed, then vectorize your code rather than calling the function sequentially.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kfbaad$sur$1@newscl01ah.mathworks.com>...
> "Peter Bone" <peterbone@hotmail.com> wrote in message <kfb6hv$dqb$1@newscl01ah.mathworks.com>...
> >
> > Thanks. That's a nice method for minimising code and works fine, but it's around 6 times slower than mine on average.
>
> Next suggestion:
> If you have a bunch of quadri-points to be processed, then vectorize your code rather than calling the function sequentially.
>
> Bruno

Thanks, but I don't think that's possible. They have to be processed sequentially because the next line segment to be processed could merge with a line segment that has been previously merged.

I was hoping for something more algorithmic because I will be coding this in C++ eventually anyway. I was perhaps thinking there could be something more efficient by not having to compute the square distance between each each pair of points. Perhaps that isn't possible.