Description
In programming assignment 1, problem 2, you wrote a program that took a polygon P as input
and found a polygon Q that was the midpoints of all the sides of P. In this assignment you will
invert that process; that is, you will write a program that takes the midpoints Q and either returns
a polygon P such that Q is the midpoints of the sides of P, or reports that no such polygon exists.
That is, given a sequence of k points in the plane ~q1 . . . ~qk, find a sequence ~p1 . . . ~pk such that
~q1 is the midpoint of ~p1 and ~p2.
~q2 is the midpoint of ~p2 and ~p3.
. . .
~qk−1 is the midpoint of ~pk−1 and ~vk.
~qk is the midpoint of ~pk and ~p1.
Write a Matlab function InvertMidpoints(Q) which takes as argument a polygon Q, represented
in the form used in programming assignment 1, and returns a pair of values [FOUND, P]. If there is
a solution, then FOUND is true and P is a 2 × k matrix where P[:,i] is the x- and y- coordinates of
the ith vertex of P. If there is no solution then FOUND is false and P is the 2 × k zero matrix.
Thus, for example, if Q is the array
Q =
1 3 1 2 3
4 4 3 6 3
then InvertMidpoint(Q) should return FOUND=true and
P =
0 2 4 −2 6
0 8 0 6 6
If
Q =
1 3 1 −1
4 4 3 3
then InvertMidpoint(Q) should return FOUND=true and
P =
0 2 4 −2
0 8 0 6
1
If
Q =
1 3 1 −1
4 4 3 6
then InvertMidpoint(Q) should return FOUND=false and
P =
0 0 0 0
0 0 0 0
First hint: First, notice that the x and y coordinates in this problem are completely decoupled.
That is, if we write ~qi = hxi
, yii, and ~pi = hai
, bii, then we have
x1 = (a1 + a2)/2.
x2 = (a2 + a3)/2.
. . .
xk−1 = (ak−1 + ak)/2.
xk = (ak + a1)/2.
and the identical equations relates the y’s to the b’s. Thus, for example, for k = 5, the 5-dimensional
vectors ~x, ~y, ~a,~b satisfy the equations ~x = C~a, ~y = C~b where C is the matrix of coefficients,
C =
1/2 1/2 0 0 0
0 1/2 1/2 0 0
0 0 1/2 1/2 0
0 0 0 1/2 1/2
1/2 0 0 0 1/2
So if there exists a solution you can find it by solving this system of equations separately in for the
x- and the y-coordinates and then putting those solutions together.
(Do NOT write code to solve systems of linear equations; use the built in Matlab solver.)
Second hint: As you will see in problem set 3, the matrix C is always of rank k if k is odd and of
rank k − 1 if k is even. So if k is odd then you can just construct the above matrix and solve the
problem. If k is even, then Matlab won’t allow you to do that, even if there is a solution. Rather
you have to (a) throw out one of the equations; (b) solve the remaining set of k − 1 equations in k
unknowns; (c) check to see whether the solution you have found satisfies the last equation (i.e. to
within some error tolerance ǫ which you can take to be 10−8
.)
Problem 2
Note: This problem is long, but the code is actually very short; perhaps 20 lines in total.
Suppose that A and B are electrically charged objects, located at points pA and pB with charges
QA and QB. Then the force F~A(B) that B exerts on A is the vector
F~A(B) = QA · QB
|pA − pB|
2
·
pA − pB
|pA − pB|
2 CSCI 1180
In the above product, the first factor is the magnitude of the force, which is the product of the
charges divided by the distance squared; the second factor is the direction of the force, which is the
direction from B to A.
If there are several objects B1 . . . Bk exerting a force on A, then the total force on A is the sum of
the forces:
F~A({B1 . . . Bk}) = X
k
i=1
F~A(Bi)
If the charge on A and the position of all the charges is fixed, then the net force is a linear function
of vector of charges hQ~ = Q1 . . . Qki.
For instance, in two dimensions, we could have the following situation, illustrated in the picture.
Object Location Charge |pA − pB| Magnitude of F~A(B) F~A(B)
A h0, 1i 1 — —
B1 h4, 4i 50 5 50/25 = 2 2 · h−4, −3i/5 = h−1.60, −1.20i
B2 h−3, 1i 36 3 36/9 = 4 4 · h3, 0i/3 = h4.00, 0.00i
B3 h1, 0i −6
√
2 −6/2 = −3 −3 · h−1, 1i/
√
2 = h2.12, −2.12i
Total h4.52, −3.32i
A
B1
B2
B3
Total
Force from B2
Force from B3
force from B1
3 CSCI 1180
Problem 2.A (2.5 points)
Write a function function F = ForceMatrix(PA,PB) where
• PA is a 2-dimensional column vector of the coordinates of object A of charge 1.
• PB is a 2 × k matrix, where the ith column, PB[:,i] is the coordinates of object Bi
.
• F, the value returned, is the 2 × k matrix with the property that for any vector of charges ~Q,
the value F · ~Q is the net force on A.
For instance, in the above example, we could call
> PA = [0;1];
> PB = [4,1,-3; 4,0,1];
> F = ForceMatrix(PA,PB)
F =
-0.0320 -0.3536 0.1111
-0.0240 0.3536 0
> QB = [50; -6; 36];
> F*QB
ans =
4.5213
-3.3213
Problem 2.B: 0.5 points
Write the following two functions: function TF = TotalForce(PA,PB,QB) and C = PossibleCharge(PA,PB,TF).
In both of these PA, PB are the same as in problem 1. In TotalForce, the input QB is a column
vector of the charges on B and the value returned TF is the total force on A, a column vector. In
PossibleCharge, TF is the total force as a column vector and the value returned C is a possible
charge vector that would give rise to that force. If k > 2 then there are multiple possible answers
but your code only has to return one of these. For example, using the same values of PA,PB,QB we
could write,
> TF = TotalForce(PA,PB,QB)
TF =
4.5213
-3.3213
> C = PossibleCharge(PA,PB,TF)
0
-9.3941
10.8000
>> TotalForce(PA,PB,C)
ans =
4.5213
-3.3213
4 CSCI 1180
Having done problem 2.A, each of these functions should consist of one quite simple line of MATLAB.
The code for TotalForce should always work, unless A is at the same position as one of the Bi
’s.
If all the points, are collinear, then there may not exist any solution for PossibleCharge.
Problem 2.C: 2 points
Suppose as before there are k fixed charges B1 . . . Bk in the plane. You know the locations, but not
the value of the charges, and you want to find out the value of the charges. A way to do this is
as follows: You take an object A with charge 1, you put it at various points in the plane, and you
measure the net force on it.
Write a function function C = FindCharges(PA,PB,TF) where
• PA is a 2 × w matrix, where the ith column, PA[:,i] is the coordinates of the ith placement
of the test charge A. The dimension w is the number of different placements you try.
• PB is the locations of the charges B1 . . . Bk, as above.
• F is a 2 × q matrix, where the ith column F[:,i] is the total force on A in its ith placement.
• The value returned C is the k-dimensional column vector of charges on the Bi
.
Hint: Look up the Matlab reshape function.
For instance, in the above example, we could call
> PA = [0,2;1,0];
> PB = [4,1,-3; 4,0,1];
> TF(:,1) = TotalForce(PA(:,1),PB,QB);
> TF(:,2) = TotalForce(PA(:,2),PB,QB);
> C = FindCharges(PA,PB,TF)
C =
50.0000
-6.0000
36.0000
5 CSCI 1180
