## Chapter 8: Exercises

1. ¤U¦CÁp¥ß¤èµ{¦¡¦³µL½a¦h²Õ¥æÂI¡G $$\left\{ \begin{array}{l} y = 1/x\\ y = sin(x) \end{array} \right.$$
1. °²³]³o¨Ç¥æÂI¥i¥Hªí¥Ü¦¨ $(x_1, y_1), (x_2, y_2), (x_3, y_3), \cdots$, ¦Ó¥B $x_1 < x_2 < x_3 < \cdots$¡C½Ð¥Î fzero «ü¥O¡A§ä¥X $x_1, x_2, x_3$¡C
2. ½Ðµe¥X¥Nªí¤W­z¨â­Ó¤èµ{¦¡ªº¦±½u¡A¨Ã¥Î¤p¶ê°é¼Ð¥Ü¥X $(x_1, y_1), (x_2, y_2), (x_3, y_3)$ ªº¦ì¸m¡A¥HÅçÃÒ§A¦b«e¤@¤pÃDªºµª®×¡C
2. Find a point to minimize distance difference: Given two set of points A and B on a 2D space, find a point (x,0) on the X-axis such that the sum of distance to all points in A is equal to to sum of distance to all points in B. In other words, you need to write a function equalDistance.m with the following usage:
x = equalDistance(A, B);
where
• A is a matrix of 2 by m, representing m points in a 2D plane
• B is a matrix of 2 by n, representing n points in a 2D plane
• x is the returned output
Note that you can simply assume the solution of x always exists.

Here is a test example:

1. Example 1: 08-¤@¯ë¼Æ¾Ç¨ç¼Æªº³B²z»P¤ÀªR/equalDistance01.mA=[1.02425546496901 1.25358084802804 1.17951024589869 1.67572050678079 1.36894578489338 1.6749531972447 1.72228602412244 1.57044649311883 1.13258989974403 1.90017865546025; 1.50659089719153 1.83620274208373 1.54085325182511 1.7648613516281 1.53236552752797 2.00265451589403 1.63189442288142 1.52571664681234 1.61703687407616 1.82597937814431]; B=[-0.364218237058624 -0.627935085190556 -0.435555596054787 -0.97890906944334 -0.368512531286445 -0.558137538884114 -0.254487941788666 -0.300780054401997 -0.61814596238125 -0.570864465939227 -0.683820512711681 -0.471135644946428; -0.820567174888604 -0.905539415326849 -0.726200531441377 -0.995112554677464 -0.343980731337428 -0.332428485029845 -0.977633932802877 -0.584977211064341 -0.966664915591615 -0.556292501691081 -0.519141532920073 -0.964541521774489]; x=equalDistance(A, B); format long; x % Plotting plot(A(1,:), A(2,:), 'o', B(1,:), B(2,:), 'o'); grid on; axis image line(x, 0, 'marker', 'o', 'color', 'k'); legend('Set A', 'Set B', 'x', 'location', 'northOutside', 'orientation', 'horizontal'); title(['x =', mat2str(x)]); x = 0.793334860502017

Hint
• You need to use the function fzero.m.
• You can modify irrFind.m to make things easier.

3. Find a line to minimize distance difference: Given a set of points A on a 2D space, find a line y=alpha*x such that the sum of distance to all points above the line is equal to to sum of distance to all points below the line. In other words, you need to write a function equalDistanceFromLine.m with the following usage:
alpha = equalDistanceFromLine(A);
where
• A is a matrix of 2 by m, representing m points in a 2D plane
• alpha is the slope of the separating line
Note that you can simply assume the solution of alpha always exists.

Test cases

• A = [0.669615828536535 1.37831002494;0.255156313573849 0.700802957390634] ==> alpha = 0.46679388774826

• A = [1.0459613413713 1.64836240385754 0.668148281107254 1.24009361110736 1.76736994372824 0.514183249250956 1.22696476792286 1.87222221905272 1.58712322506665 0.899136620392806;0.995918733217741 1.57784235228208 0.949856035477784 1.1820334094137 1.46127638101438 0.816264168546478 0.872065204595773 1.35287364461043 0.445267025957944 1.00539440958911] ==> alpha = 0.854784493132274

Hint
• You need to use the function fzero.m.
• You can modify irrFind.m to make things easier.
• The distance of a point $(x_0, y_0)$ to a line $y=ax+b$ is $\frac{|y_0-ax_0-b|}{\sqrt{1+a^2}}$.
• For a good initial guess, you can set the initial value of alpha such that the mean vector of A will pass the line.

4. ¦b XY ¥­­±¤Wµ¹©w¤TÂI A¡BB¡BC¡A§ä¥X¥t¥~¤@ÂI X¡A¨Ï±o X ¨ì A¡BB¡BC ¤TÂIªº¶ZÂ÷©M¬°³Ì¤p¡C½Ð¼g¤@­Ó¨ç¦¡ mindist.m ¸Ñ¨M¤W­z°ÝÃD¡A¦¹¨ç¦¡ªº¿é¥X¤J®æ¦¡¦p¤U¡G
x = mindist(a, b, c)
¨ä¤¤ a¡Bb¡Bc ¬°¤TÂIªº®y¼Ð¡Ax «h¬O¿é¥XÂIªº®y¼Ð¡A§A¥²¶·¨Ï¥Î fminsearch «ü¥O¨Ó¶i¦æ³Ì¨Î¤Æ¡C
• ·í a = [4 0]¡Bb = [0 3]¡Bc = [0 0] ®É¡Amindist.m ©Ò¶Ç¦^ªº x ­È¬°¦ó¡H¹ïÀ³ªº³Ìµu¶ZÂ÷©M¬°¦ó¡H
• ¦b¤W¤pÃD¤¤¡A·í³Ìµu¶ZÂ÷©Mµo¥Í®É¡A¨¤«× $\angle AXB$¡B$\angle BXC$¡B$\angle CXA$ ¦U¬O¦h¤Ö¡H
5. ¦b XY ¥­­±¤Wµ¹©w¤TÂI A¡BB¡BC¡A§ä¥X¥t¥~¤@ÂI X¡A¨Ï±o X ¨ì A¡BB¡BC ¤TÂIªº¶ZÂ÷¥­¤è©M¬°³Ì¤p¡C½Ð¼g¤@­Ó¨ç¦¡ mindist2.m ¸Ñ¨M¤W­z°ÝÃD¡A¦¹¨ç¦¡ªº¿é¥X¤J®æ¦¡¦p¤U¡G
x = mindist2(a, b, c)
¨ä¤¤ a¡Bb¡Bc ¬°¤TÂIªº®y¼Ð¡Ax «h¬O¿é¥XÂIªº®y¼Ð¡A§A¥²¶·¨Ï¥Î fminsearch «ü¥O¨Ó¶i¦æ³Ì¨Î¤Æ¡C
• ·í a = [4 0]¡Bb = [0 3]¡Bc = [0 0] ®É¡Amindist2.m ©Ò¶Ç¦^ªº x ­È¬°¦ó¡H¹ïÀ³ªº³Ìµu¶ZÂ÷¥­¤è©M¬°¦ó¡H
• ¦b¤W¤pÃD¤¤¡A·í³Ìµu¶ZÂ÷¥­¤è©Mµo¥Í®É¡Ax-(a+b+c)/3 ªºªø«×¬O¦h¤Ö¡H
6. ¦b XY ¥­­±¤Wµ¹©w¤@²Õ¦æ¦V¶q x1, x2, ... xn¡A½Ð§ä¥X¤@­Ó³æ¦ì¦V¶q u¡A¨Ï±o³o¤@²Õ¦V¶q¦b u ¤è¦Vªº§ë¼v¶q¥­¤è©M¬°³Ì¤p¡C½Ð¼g¤@­Ó¨ç¦¡ minProj.m ¸Ñ¨M¤W­z°ÝÃD¡A¦¹¨ç¦¡ªº¿é¥X¤J®æ¦¡¦p¤U¡G
u = minproj(X)
¨ä¤¤ X ªº¨C¤@­Óª½¦æ§Y¬O¦æ¦V¶q xi, i = 1, ..., n¡A¦Ó u ¬O¤@­Óªø«×¬°¤@ªº¦V¶q¡A¥Nªí³Ì¨Îªº§ë¼v¤è¦V¡C§A¥²¶·¨Ï¥Î fminsearch «ü¥O¨Ó¶i¦æ³Ì¨Î¤Æ¡C
7. Function for min. total distance to a set of points: Write a function minDist2points(A) that returns a point in a d-dimensional space such that the total distance between this point and all the other $n$ points is minimized, where these $n$ points can be packed into a d-by-n matrix A, with A(:,i) being the i-th point. The initial guess of the solution should be set to the mean of these $n$ points.

Test cases

• minDist2points([1 4 2;8 6 1]) returns [3.2438; 5.7910].
• minDist2points([1 4 2 3; 8 6 1 7; 5 9 0 1]) returns [ 2.2855; 6.3539; 3.6291].
(Note that you are not allowed to use any toolboxes in this exercise.)

Hint
• Since there is no analytic solution, you need to use "fminsearch" (with default options) to search for the point.
• Analytic solution of this problem exists if the "total distance" is replaced by "total squared distance".

8. Function for min. total distance to a set of hyperplanes: Write a function minDist2hyperplanes(A) that returns a point in a d-dimensional space such that the total distance between this point and all the other $n$ hyperplanes is minimized, where these $n$ hyperlines can be packed into a (d+1)-by-n matrix A, with A(:,i) being the coefficients of the i-th hyperplane: $A(1,i)*x_1+A(2,i)*x_2+\cdots+A(d,i)*x_d+A(d+1,1)=0$.

Hint
• Since there is no analytic solution, you need to use "fminsearch" (with default options) to search for the point.
• Analytic solution of this problem exists if the "total distance" is replaced by "total squared distance".

9. Circle fitting via DSS: A circle in 2D can be described by the following equation $$(x-a)^2+(y-b)^2=r^2,$$ where $(a, b)$ is the center and $r$ is the radius of the circle. Given a dataset $\{(x_i, y_i)|i=1, 2, ..., n\}$, the sum of distances of these points to the circle can be formulated as follows: $$f(a, b, r)=\sum_{i=1}^{n}\left|\sqrt{(x_i-a)^2+(y_i-b)^2}-r\right|$$ Write a function circleFit.m that can find the best values of $[a, b, r]^T$ such that $f(a, b, r)$ can be minimized. The usage of the function is:
output = circleFit(data)
where
• data: an 2-by-n dataset matrix, with each column being a sample data point.
• output: a column vector of the derived $[a, b, r]^T$ using Downhill Simplex Search (which is implemented as the function "fminsearch" in MATLAB).

Note that the initial guess of $[a, b, r]^T$ should be as close as possible to the minimizing point. One good choice is to set the center ($[a, b]^T$) as the mean of all the data points, and set $r$ as the average distance of the center to each data point.

Here is a test example:

1. Example 2: 08-¤@¯ë¼Æ¾Ç¨ç¼Æªº³B²z»P¤ÀªR/circleFit01.mdata=[12 -5 13 -3 -8 3 7 -4 7 -4 -4 -1 -5 2 13 -5 -6 5 -5 -8 -6 -7 2 9 -5 -4 -5 8 4 -1 12 1 7 11 11 -1 9 0 -5 14 -3 -8 -3 12 -1 -1 13 7 -6 -7 12 12 -8 10 6 14 -7 6 10 12 8 14 7 8 -1 10 9 13 3 13 -7 12 7 13 -5 -7 -2 9 10 -6 7 7 14 10 9 -6 11 -3 12 -6 8 12 9 10 11 11 1 1 -6 -4; 3 13 6 1 9 16 15 1 17 13 -1 -3 9 17 12 5 3 -2 0 7 6 10 15 -4 8 -1 0 14 17 16 12 -3 -3 6 11 -3 14 16 13 9 -2 6 12 7 -4 15 5 -3 12 4 7 5 4 2 -1 6 10 16 0 7 1 10 15 -1 17 0 14 5 16 9 0 1 -1 0 12 2 -1 16 0 13 -2 15 7 1 -2 11 11 3 6 10 15 0 15 7 0 4 -4 -1 5 1]; theta=circleFit(data); format long; theta % Plotting t=linspace(0, 2*pi); x1=theta(1)+theta(3)*cos(t); y1=theta(2)+theta(3)*sin(t); plot(data(1,:), data(2,:), '.', x1, y1, 'r'); axis image legend({'Sample data', 'Fitting circle'}, 'location', 'northOutside', 'orientation', 'horizontal'); theta = 2.500014916354736 6.500011175675343 9.924708551335694

10. Rectangle fitting via DSS: A rectangle in 2D can be described by 4 parameters $[x, y, \alpha, \beta]$, where $[x, y]$ is the center coordinate of the rectangle, $\alpha$ is the half width, and $\beta$ is the half height. (Thus the 4 corners of the rectangle can be represented by 4 points at $[x-\alpha, y-\beta]$, $[x-\alpha, y+\beta]$, $[x+\alpha, y+\beta]$, and $[x+\alpha, y-\beta]$.) Given a point in 2D, the distance of this point to the rectangle is defined as the shortest distance of this point to all possible data points on the rectangle. Write a function rectangleFit.m that can find the best values of $[x, y, \alpha, \beta]^T$ such that the total distance of a dataset to the rectangle can be minimized. The usage of the function is:
output = rectangleFit(data)
where
• data: an 2-by-n dataset matrix, with each column being a sample data point.
• output: a column vector of the derived $[x, y, \alpha, \beta]^T$ using Downhill Simplex Search (which is implemented as the function "fminsearch" in MATLAB).

Note that the initial guess of $[x, y, \alpha, \beta]^T$ should create a bounding box for the dataset.

Here is a test example:

1. Example 3: 08-¤@¯ë¼Æ¾Ç¨ç¼Æªº³B²z»P¤ÀªR/rectangleFit01.m% Create the sample data n=20; d1=[rand(1,n)/4+2; 3*rand(1,n)+2]; d2=[4*rand(1,n)-2; rand(1,n)/4+2]; d3=[4*rand(1,n)-2; rand(1,n)/4+5]; d4=[rand(1,n)/4-2; 3*rand(1,n)+2]; data=[d1, d2, d3, d4]; data=round(data*50); % Do the fitting theta=rectangleFit(data); fprintf('data=%s\n', mat2str(data)); fprintf('theta=%s\n', mat2str(theta)); % Plot the result plot(data(1,:), data(2,:), '.'); x1=theta(1)-theta(3); x2=theta(1)+theta(3); y1=theta(2)-theta(4); y2=theta(2)+theta(4); line([x1 x1 x2 x2 x1], [y1 y2 y2 y1 y1], 'color', 'r'); axis image legend({'Sample data', 'Final fitting rectangle'}, 'location', 'northOutside', 'orientation', 'horizontal');data=[101 110 105 104 104 112 111 112 107 106 106 106 105 110 108 109 101 112 109 108 81 -52 -63 -25 28 -21 -20 -75 -39 -22 -12 48 -44 -13 54 -52 85 29 -6 85 54 -33 -80 56 4 36 -23 -63 86 76 25 35 -30 -76 -5 -86 -63 73 -86 -46 -88 -96 -88 -95 -90 -92 -88 -98 -93 -92 -94 -96 -89 -92 -92 -97 -91 -88 -96 -98;136 240 208 191 157 179 124 137 235 230 186 163 134 176 103 103 111 123 225 234 100 107 105 110 109 105 103 102 112 102 103 108 101 109 110 112 102 111 101 101 253 260 253 259 251 251 258 255 256 252 257 257 259 252 256 261 261 255 258 253 222 170 231 228 222 112 136 230 147 110 139 193 197 174 159 209 141 129 149 151] theta=[7.29406018687973 180.499991163551 99.2940805465921 75.4999909043646]

MATLABµ{¦¡³]­p¡G¶i¶¥½g