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:
Line Intersection given Column Vectors - HELP!

Subject: Line Intersection given Column Vectors - HELP!

From: Adam Hall

Date: 31 Mar, 2010 22:25:05

Message: 1 of 7

This comes from Introduction to Scientific Computing by Charles Van Loan...
I forget the edition, but the question is this:

% Implement the following function
% function [u,v] = Lines(a,b,c,d)
%
% a,b,c and d are column n-vectors with the property that for i=1:n, the
% lines
%
% x(t1) = a(i) + t1(b(i) - a(i)) -inf < t1 < inf
% y(t2) = c(i) + t2(d(i) - c(i)) -inf < t2 < inf
%
% intersect. The points of intersection (u(i),v(i)) are returned in column
% n-vectors u and v.
%
% Your implementation should use Gaussian Elimination with partial pivoting
% to solve for the intersection points. It should be fully vectorized. (No loops necessary.)

I'm completely lost as to how to solve this. I know how to do it by hand, but writing a function that does it is proving a little more difficult.
Can anyone lead me in the right direction?

Subject: Line Intersection given Column Vectors - HELP!

From: Nathan

Date: 31 Mar, 2010 22:31:52

Message: 2 of 7

On Mar 31, 3:25 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> This comes from Introduction to Scientific Computing by Charles Van Loan...
> I forget the edition, but the question is this:
>
> % Implement the following function
> % function [u,v] = Lines(a,b,c,d)
> %
> % a,b,c and d are column n-vectors with the property that for i=1:n, the
> % lines
> %
> % x(t1) = a(i) + t1(b(i) - a(i))     -inf < t1 < inf
> % y(t2) = c(i) + t2(d(i) - c(i))     -inf < t2 < inf
> %
> % intersect. The points of intersection (u(i),v(i)) are returned in column
> % n-vectors u and v.
> %
> % Your implementation should use Gaussian Elimination with partial pivoting
> % to solve for the intersection points. It should be fully vectorized. (No loops necessary.)
>
> I'm completely lost as to how to solve this. I know how to do it by hand, but writing a function that does it is proving a little more difficult.
> Can anyone lead me in the right direction?

First off, it doesn't hurt to write it by hand!
Write it out step by step as you would (by hand), and show us what you
have come up with.
Translating from hand written "code" to actual matlab code is easier
than poofing your solution into existence.

-Nathan

Subject: Line Intersection given Column Vectors - HELP!

From: Adam Hall

Date: 31 Mar, 2010 23:38:20

Message: 3 of 7

Nathan <ngreco32@gmail.com> wrote in message <10f6f7d7-2053-40b5-923e-cd480ed8751f@u31g2000yqb.googlegroups.com>...
> On Mar 31, 3:25 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> > This comes from Introduction to Scientific Computing by Charles Van Loan...
> > I forget the edition, but the question is this:
> >
> > % Implement the following function
> > % function [u,v] = Lines(a,b,c,d)
> > %
> > % a,b,c and d are column n-vectors with the property that for i=1:n, the
> > % lines
> > %
> > % x(t1) = a(i) + t1(b(i) - a(i))     -inf < t1 < inf
> > % y(t2) = c(i) + t2(d(i) - c(i))     -inf < t2 < inf
> > %
> > % intersect. The points of intersection (u(i),v(i)) are returned in column
> > % n-vectors u and v.
> > %
> > % Your implementation should use Gaussian Elimination with partial pivoting
> > % to solve for the intersection points. It should be fully vectorized. (No loops necessary.)
> >
> > I'm completely lost as to how to solve this. I know how to do it by hand, but writing a function that does it is proving a little more difficult.
> > Can anyone lead me in the right direction?
>
> First off, it doesn't hurt to write it by hand!
> Write it out step by step as you would (by hand), and show us what you
> have come up with.
> Translating from hand written "code" to actual matlab code is easier
> than poofing your solution into existence.
>
> -Nathan

Well, I know that we have two functions:
f(x) = a(i) + x*(b(i)-a(i))
g(x) = c(i) + x*(d(i)-c(i))
And the intersection would be found by setting f(x) = g(x) and solving for x for each value of i. Each of the SOLVED x values [x1, x2, x3... xi] would be put into the vector u, and then v would be [f(x1), f(x2), f(x3)... f(xi)]

But this doesn't use Gaussian Elimination and would require a for loop, so it's not gonna work...

First I'm thinking we should get out line equations in a form we can use...
f(x) - (b(i) - a(i))*x = a(i)
g(x) - (d(i) - c(i)*x = c(i)

So in matrix form we have
Matrix 1 = [1 - (b(i) - a(i)); 1 - (d(i) - c(i))]
Matrix 2 = [a(i); c(i)]

And Matrix 1 * x = Matrix 2 where x is some unknown column vector

So maybe we could do something like:
Matrix 1\Matrix 2
Should give us x? And x would be a solution

Maybe:
function [u,v] = Lines(A,B,C,D)
E = [1,-(B(i)-A(i));1,-(D(i)-C(i)];
F = [A(i);C(i)];
x = E\F;

And now I'm stuck...

Subject: Line Intersection given Column Vectors - HELP!

From: Nathan

Date: 31 Mar, 2010 23:50:17

Message: 4 of 7

On Mar 31, 4:38 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> Nathan <ngrec...@gmail.com> wrote in message <10f6f7d7-2053-40b5-923e-cd480ed87...@u31g2000yqb.googlegroups.com>...
> > On Mar 31, 3:25 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> > > This comes from Introduction to Scientific Computing by Charles Van Loan...
> > > I forget the edition, but the question is this:
>
> > > % Implement the following function
> > > % function [u,v] = Lines(a,b,c,d)
> > > %
> > > % a,b,c and d are column n-vectors with the property that for i=1:n, the
> > > % lines
> > > %
> > > % x(t1) = a(i) + t1(b(i) - a(i))     -inf < t1 < inf
> > > % y(t2) = c(i) + t2(d(i) - c(i))     -inf < t2 < inf
> > > %
> > > % intersect. The points of intersection (u(i),v(i)) are returned in column
> > > % n-vectors u and v.
> > > %
> > > % Your implementation should use Gaussian Elimination with partial pivoting
> > > % to solve for the intersection points. It should be fully vectorized. (No loops necessary.)
>
> > > I'm completely lost as to how to solve this. I know how to do it by hand, but writing a function that does it is proving a little more difficult.
> > > Can anyone lead me in the right direction?
>
> > First off, it doesn't hurt to write it by hand!
> > Write it out step by step as you would (by hand), and show us what you
> > have come up with.
> > Translating from hand written "code" to actual matlab code is easier
> > than poofing your solution into existence.
>
> > -Nathan
>
> Well, I know that we have two functions:
> f(x) = a(i) + x*(b(i)-a(i))
> g(x) = c(i) + x*(d(i)-c(i))
> And the intersection would be found by setting f(x) = g(x) and solving for x for each value of i. Each of the SOLVED x values [x1, x2, x3... xi] would be put into the vector u, and then v would be [f(x1), f(x2), f(x3)... f(xi)]
>
> But this doesn't use Gaussian Elimination and would require a for loop, so it's not gonna work...
>
> First I'm thinking we should get out line equations in a form we can use...
> f(x) - (b(i) - a(i))*x = a(i)
> g(x) - (d(i) - c(i)*x = c(i)
>
> So in matrix form we have
> Matrix 1 = [1  - (b(i) - a(i)); 1 - (d(i) - c(i))]
> Matrix 2 = [a(i); c(i)]
>
> And Matrix 1 * x = Matrix 2 where x is some unknown column vector
>
> So maybe we could do something like:
> Matrix 1\Matrix 2
> Should give us x? And x would be a solution
>
> Maybe:
> function [u,v] = Lines(A,B,C,D)
> E = [1,-(B(i)-A(i));1,-(D(i)-C(i)];
> F = [A(i);C(i)];
> x = E\F;
>
> And now I'm stuck...

Just a note, that might help you:

For vectors A and B, as long as they are the same length,
you can subract corresponding elements just by doing A-B or B-A

C = A-B
is the same as:
for i=1:length(A)
C(i) = A(i)-B(i)
end

-Nathan

Subject: Line Intersection given Column Vectors - HELP!

From: Adam Hall

Date: 1 Apr, 2010 01:29:05

Message: 5 of 7

Nathan <ngreco32@gmail.com> wrote in message <344d07f6-2b34-47a1-8f79-95118f744362@q15g2000yqj.googlegroups.com>...
> On Mar 31, 4:38 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> > Nathan <ngrec...@gmail.com> wrote in message <10f6f7d7-2053-40b5-923e-cd480ed87...@u31g2000yqb.googlegroups.com>...
> > > On Mar 31, 3:25 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> > > > This comes from Introduction to Scientific Computing by Charles Van Loan...
> > > > I forget the edition, but the question is this:
> >
> > > > % Implement the following function
> > > > % function [u,v] = Lines(a,b,c,d)
> > > > %
> > > > % a,b,c and d are column n-vectors with the property that for i=1:n, the
> > > > % lines
> > > > %
> > > > % x(t1) = a(i) + t1(b(i) - a(i))     -inf < t1 < inf
> > > > % y(t2) = c(i) + t2(d(i) - c(i))     -inf < t2 < inf
> > > > %
> > > > % intersect. The points of intersection (u(i),v(i)) are returned in column
> > > > % n-vectors u and v.
> > > > %
> > > > % Your implementation should use Gaussian Elimination with partial pivoting
> > > > % to solve for the intersection points. It should be fully vectorized. (No loops necessary.)
> >
> > > > I'm completely lost as to how to solve this. I know how to do it by hand, but writing a function that does it is proving a little more difficult.
> > > > Can anyone lead me in the right direction?
> >
> > > First off, it doesn't hurt to write it by hand!
> > > Write it out step by step as you would (by hand), and show us what you
> > > have come up with.
> > > Translating from hand written "code" to actual matlab code is easier
> > > than poofing your solution into existence.
> >
> > > -Nathan
> >
> > Well, I know that we have two functions:
> > f(x) = a(i) + x*(b(i)-a(i))
> > g(x) = c(i) + x*(d(i)-c(i))
> > And the intersection would be found by setting f(x) = g(x) and solving for x for each value of i. Each of the SOLVED x values [x1, x2, x3... xi] would be put into the vector u, and then v would be [f(x1), f(x2), f(x3)... f(xi)]
> >
> > But this doesn't use Gaussian Elimination and would require a for loop, so it's not gonna work...
> >
> > First I'm thinking we should get out line equations in a form we can use...
> > f(x) - (b(i) - a(i))*x = a(i)
> > g(x) - (d(i) - c(i)*x = c(i)
> >
> > So in matrix form we have
> > Matrix 1 = [1  - (b(i) - a(i)); 1 - (d(i) - c(i))]
> > Matrix 2 = [a(i); c(i)]
> >
> > And Matrix 1 * x = Matrix 2 where x is some unknown column vector
> >
> > So maybe we could do something like:
> > Matrix 1\Matrix 2
> > Should give us x? And x would be a solution
> >
> > Maybe:
> > function [u,v] = Lines(A,B,C,D)
> > E = [1,-(B(i)-A(i));1,-(D(i)-C(i)];
> > F = [A(i);C(i)];
> > x = E\F;
> >
> > And now I'm stuck...
>
> Just a note, that might help you:
>
> For vectors A and B, as long as they are the same length,
> you can subract corresponding elements just by doing A-B or B-A
>
> C = A-B
> is the same as:
> for i=1:length(A)
> C(i) = A(i)-B(i)
> end
>
> -Nathan

It might help to know that I have access to the m-files in Chapter 6 of the book:
http://www.cs.cornell.edu/cv/Books/SCMV/Mfiles/chap6.htm#GEpiv
I think I need to use GEpiv, LTriSol and UTriSol
I just don't understand.
The teacher of the class doesn't really explain anything related to the projects he assigns...
It's kind of like a teacher who teaches you how to multiply variables and then assigns you problems that involve factoring quadratics and using the FOIL method when he never explained what FOIL was or how to factor a quadratic....
I'm about to give up...

Subject: Line Intersection given Column Vectors - HELP!

From: Roger Stafford

Date: 1 Apr, 2010 06:20:26

Message: 6 of 7

> > > > On Mar 31, 3:25 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> > > > > %
> > > > > % x(t1) = a(i) + t1(b(i) - a(i))     -inf < t1 < inf
> > > > > % y(t2) = c(i) + t2(d(i) - c(i))     -inf < t2 < inf
> > > > > %
> > > > > % intersect. The points of intersection (u(i),v(i)) are returned in column
> > > > > % n-vectors u and v.
> > > > > %
..........
> I'm about to give up...
---------------
  Are you sure you've copied that problem correctly, Adam? As it stands it makes absolutely no sense to me. If parameters t1 and t2 are kept equal to a common variable t, the equations

 x = a(i) + t(b(i) - a(i))
 y = c(i) + t(d(i) - c(i))

would represent a single line in the x,y plane for each given i as the t parameter varies over its infinite range. When t = 0 then (x,y) is the point (a(i),c(i)) and when t = 1, (x,y) is (b(i),d(i)), so this line would run through these two points. Where is there an intersection in this? There is only one line for each value of i. I can think of no reasonable interpretation of those two original equations that represents a pair of intersecting lines - not as you have given them.

  I think it is important that you get the description of a problem you pose to this group entirely accurate. Otherwise you may not receive any effective help. We may not solve your homework in its entirety for you, but you might receive some useful help on a problem if it is described correctly.

Roger Stafford

Subject: Line Intersection given Column Vectors - HELP!

From: Adam Hall

Date: 1 Apr, 2010 13:36:05

Message: 7 of 7

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hp1dva$3gb$1@fred.mathworks.com>...
> > > > > On Mar 31, 3:25 pm, "Adam Hall" <hal...@goldmail.etsu.edu> wrote:
> > > > > > %
> > > > > > % x(t1) = a(i) + t1(b(i) - a(i))     -inf < t1 < inf
> > > > > > % y(t2) = c(i) + t2(d(i) - c(i))     -inf < t2 < inf
> > > > > > %
> > > > > > % intersect. The points of intersection (u(i),v(i)) are returned in column
> > > > > > % n-vectors u and v.
> > > > > > %
> ..........
> > I'm about to give up...
> ---------------
> Are you sure you've copied that problem correctly, Adam? As it stands it makes absolutely no sense to me. If parameters t1 and t2 are kept equal to a common variable t, the equations
>
> x = a(i) + t(b(i) - a(i))
> y = c(i) + t(d(i) - c(i))
>
> would represent a single line in the x,y plane for each given i as the t parameter varies over its infinite range. When t = 0 then (x,y) is the point (a(i),c(i)) and when t = 1, (x,y) is (b(i),d(i)), so this line would run through these two points. Where is there an intersection in this? There is only one line for each value of i. I can think of no reasonable interpretation of those two original equations that represents a pair of intersecting lines - not as you have given them.
>
> I think it is important that you get the description of a problem you pose to this group entirely accurate. Otherwise you may not receive any effective help. We may not solve your homework in its entirety for you, but you might receive some useful help on a problem if it is described correctly.
>
> Roger Stafford

Just wanted to say Thanks to both you and Nathan for attempting to help me.
Yes the problem is written correctly, but I'm assuming that x and y would both represent the same f(x) function and t1 and t2 would both represent x...

As an example of what I think the problem wants, let's look at these vectors:

A=[1,2,3]
B=[3,5,2]
C=[2,3,1]
D=[1,1,8]

Then the equation of the lines would be:
f(x) = 2x + 1
g(x) = -1x + 2

f(x) = 3x + 2
g(x) = -2x + 3

f(x) = -1x + 3
g(x) = 7x + 1

And we can solve for the intersection points:

2x + 1 = -x + 2
3x = 1
x = 1/3
f(1/3) = 2(1/3) + 1 = 5/3

3x + 2 = -2x + 3
5x = 1
x = 1/5
f(1/5) = 3(1/5) + 2 = 13/5

-1x + 3 = 7x + 1
8x = 2
x = 1/4
f(1/4) = -1(1/4) + 3 = 11/4

And our u and v would be:

u = [ 1/3, 1/5, 1/4 ]
v = [ 5/3, 13/5, 11/4 ]

The deadline for this problem was midnight last night, but if you guys would still like to help me figure it out, I wouldn't mind. I don't like not being able to figure things out, especially when the problem shouldn't be as difficult as it is...

Tags for 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