Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Merge line segments

Subject: Merge line segments

From: Peter Bone

Date: 11 Feb, 2013 15:19:27

Message: 1 of 5

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

Subject: Merge line segments

From: Bruno Luong

Date: 11 Feb, 2013 16:23:26

Message: 2 of 5

% 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

Subject: Merge line segments

From: Peter Bone

Date: 11 Feb, 2013 16:34:08

Message: 3 of 5

"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.

Subject: Merge line segments

From: Bruno Luong

Date: 11 Feb, 2013 17:38:21

Message: 4 of 5

"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

Subject: Merge line segments

From: Peter Bone

Date: 12 Feb, 2013 16:07:18

Message: 5 of 5

"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.

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us