# Question1

对于深度为 $D$ 的某个测线，其左侧长度 $L = \dfrac{D\sin \varphi}{\cos (\varphi + \alpha)} \times \cos \alpha$，右侧 $R = \dfrac{D \sin \varphi}{\cos (\varphi - \alpha)} \times \cos \alpha$. 总覆盖宽度即为 $W = D \sin \varphi \cos \alpha \left(\dfrac{1}{\cos (\varphi - \alpha)} + \dfrac{1}{\cos (\varphi + \alpha)}\right)$.

重叠率的话，条带 $i$ 相对于条带 $i-1$ 的重叠率定义为 $R_i = \dfrac{L_i + R_{i-1} - d}{W_i}$.

对于问题一，深度 $D$ 与距离中心点位置 $X$ 的关系式：$D = 70 - X\tan \alpha$

覆盖宽度 $W$：在海底的覆盖区域在海平面上的投影。

重叠宽度 $r$：在海底的重叠区域在海平面上的投影。

重叠率：$\eta_i = \dfrac{r_{i-1,i}}{W_i}$

以下是深度、覆盖宽度、重叠率的数据：

>[90.9487 85.7116 80.4744 75.2372 70. 64.7628 59.5256 54.2884 49.0513]
[315.7051 297.5256 279.346 261.1665 242.987 224.8074 206.6279 188.4484
170.2688]
[35.6954 31.5106 26.7431 21.2622 14.8949 7.4072 -1.5252 -12.365]

以下是 深度、宽度、重叠率的数据：

(deprecated)
使用题目公式 $\eta_i = 1 - \dfrac{d}{W_{i-1}}$：

>[90.9487 85.7116 80.4744 75.2372 70. 64.7628 59.5256 54.2884 49.0513]
[315.8133 297.6276 279.4418 261.256 243.0703 224.8845 206.6987 188.513
170.3272]
[36.6715 32.8019 28.4287 23.4467 17.7193 11.0655 3.2408 -6.0935]

使用题目公式 $\eta_i = 1 - \dfrac{d}{W_{i}}$：

>[90.9487 85.7116 80.4744 75.2372 70. 64.7628 59.5256 54.2884 49.0513]
[315.8133 297.6276 279.4418 261.256 243.0703 224.8845 206.6987 188.513
170.3272]
[ 32.8019 28.4287 23.4467 17.7193 11.0655 3.2408 -6.0935 -17.4211]

使用自定义公式 $R_i = \dfrac{L_i + R_{i-1} - d/\cos \alpha}{W_i}$

>[90.9487 85.7116 80.4744 75.2372 70. 64.7628 59.5256 54.2884 49.0513]
[315.8133 297.6276 279.4418 261.256 243.0703 224.8845 206.6987 188.513
170.3272]
[ 35.6954 31.5106 26.7431 21.2622 14.8949 7.4072 -1.5252 -12.365 ]

使用自定义公式 $R_i = \dfrac{L_i + R_{i-1} - d/\cos \alpha}{W_{i-1}}$

>[90.9487 85.7116 80.4744 75.2372 70. 64.7628 59.5256 54.2884 49.0513]
[315.8133 297.6276 279.4418 261.256 243.0703 224.8845 206.6987 188.513
170.3272]
[ 33.64 29.5852 25.0027 19.7822 13.7805 6.8082 -1.391 -11.1721]

# Question2


以下是不同 beta 对应的覆盖宽度的数据：

>0
[415.69 466.09 516.49 566.89 617.29 667.69 718.09 768.48]
45
[416.12 451.79 487.47 523.14 558.82 594.49 630.16 665.84]
90
[416.55 416.55 416.55 416.55 416.55 416.55 416.55 416.55]
135
[416.12 380.45 344.77 309.1 273.42 237.75 202.08 166.4 ]
180
[415.69 365.29 314.89 264.5 214.1 163.7 113.3 62.9 ]
225
[416.12 380.45 344.77 309.1 273.42 237.75 202.08 166.4 ]
270
[416.55 416.55 416.55 416.55 416.55 416.55 416.55 416.55]
315
[416.12 451.79 487.47 523.14 558.82 594.49 630.16 665.84]

# Question3

每一条测线在海平面上覆盖的是一个矩形区域。东西走向 $H=4 \times 1852$，南北走向 $W = 2 \times 1852$.

以海域西南点为原点建系。

原点深度 $depth_O = depth_{center} + \dfrac{H}{2} \times \tan \alpha$.

对于任意点 $(x,y)$，其深度为 $depth_{(x,y)} = depth_O - y \times \tan \alpha$.


考虑测线沿着等深线的情况。

此时，每条测线的长度都等于 $W$，只需使测线条数最少即可。

要最小化测线条数。若初始测线已经确定，根据贪心思想，每条测线都与上一条测线尽可能远，直至覆盖完整个海域。若能通过贪心求出一个符合条件的解，则这个解一定是当前初始测线的最优解。

选取最优的初始测线进行尝试，即可求出全局的最优解。

最优的初始测线距离边界尽可能远，存在两种情况：从下边界开始、从上边界开始。

测线 $i$ 经过点 $(0,y_i),(W,y_i)$.

以下边界开始为例，考虑初始测线的选择。初始测线必须覆盖海域下边界，要求 $L_1 \ge y_1$，也即：

$$
\begin{aligned}
G(y_1) = \dfrac{ (D_0 - y_1\tan \alpha) \sin \varphi \cos \alpha}{\cos (\varphi + \alpha)} - y_1 \ge 0
\end{aligned}
$$

证明 $\dfrac{\partial G}{\partial y_1} < 0$.

$$
\begin{aligned}
\dfrac{\partial G}{\partial y_1} &= \dfrac{-\sin \varphi \sin \alpha}{\cos (\varphi + \alpha)} - 1
\end{aligned}
$$

其中 $\varphi = \dfrac{\theta}{2} = \dfrac{\pi}{3}$，$\alpha = 1.5^{\circ}$，则 $\dfrac{\partial G}{\partial y_1} < 0$.

则 $y_1 \uparrow$，$G(y_1) \downarrow$. 使用二分找到 $\max y_1 \text{ s.t. } G(y_1) \ge 0$ 作为初始测线。

**可以直接求解。**

$$y_1 = \dfrac{D_0 \sin \varphi \sin \alpha}{\sin \alpha \sin \varphi + \cos(\alpha + varphi)}$$

对于测线 $A,B$，二者之间的间距 $d(A,B)$ 与其重叠率 $R_{(A,B)}$ 存在单调性，重叠率的定义式：

$$
\begin{aligned}
ratio &= \dfrac{L_{i-1} + R_i - d}{W_i} \\
& = \dfrac{L_{i-1} + \dfrac{D_i \sin \varphi \cos \alpha}{\cos (\varphi - \alpha)} - d}{D_i \sin \varphi \cos \alpha \left(\dfrac{1}{\cos (\varphi - \alpha)} + \dfrac{1}{\cos (\varphi + \alpha)}\right)} \\
& = \dfrac{\dfrac{\sin \varphi \cos \alpha}{\cos (\varphi - \alpha)} }{\sin \varphi \cos \alpha \left(\dfrac{1}{\cos (\varphi - \alpha)} + \dfrac{1}{\cos (\varphi + \alpha)}\right)} + \\
& \dfrac{L_{i-1} - d}{(D_{i-1} - d \tan \alpha) \sin \varphi \cos \alpha \left(\dfrac{1}{\cos (\varphi - \alpha)} + \dfrac{1}{\cos (\varphi + \alpha)}\right)}\\
\end{aligned}
$$

只需要考察 $d$ 增大时，

$$F(d) = \dfrac{L_{i-1} - d}{(D_{i-1} - d \tan \alpha) \sin \varphi \cos \alpha \left(\dfrac{1}{\cos (\varphi - \alpha)} + \dfrac{1}{\cos (\varphi + \alpha)}\right)}$$

的变化。

$$
\begin{aligned}
\dfrac{\partial F}{\partial d} & = \dfrac{(L_{i-1} - d)\sin \alpha \sin \varphi \left( \dfrac{1}{\cos (\varphi - \alpha)} + \dfrac{1}{\cos (\varphi + \alpha)} \right) - (D_{i-1} - d \tan \alpha) \sin \varphi \cos \alpha \left(\dfrac{1}{\cos (\varphi - \alpha)} + \dfrac{1}{\cos (\varphi + \alpha)}\right)}{K^2}\\
& = ((L_{i-1} - d) \sin \alpha - (D_{i-1} - d\tan\alpha)\cos \alpha) \times T^2 \\
& = (L_{i-1} \sin \alpha - D_{i-1} \cos \alpha) \times P^2
\end{aligned}
$$

考虑到 $\sin \alpha \ll \cos \alpha$，因此 $\dfrac{\partial F}{\partial d} < 0$，则 $d \uparrow$，$F \downarrow$，$R \downarrow$，随着间距增大，重叠率减小。

$$Z(x,y) = Z\left(6 \times \lfloor \dfrac{x + 3}{6} \rfloor, 6 \times \lfloor \dfrac{y+3}{6} \rfloor \right), x \bmod 6 \neq 0 \text{ or } y \bmod 6 \neq 0$$

单调性证明完毕。

$python,Python,\mathrm{Python},\text{Python}$

**可以直接求解。**

令：

$$K = \left[ ratio\left( \dfrac{1}{\cos(\varphi+\alpha)} + \dfrac{1}{\cos (\varphi - \alpha)} \right) - \dfrac{1}{\cos(\varphi - \alpha)} \right]\sin \varphi \cos \alpha$$

原式即为：

$$\dfrac{L_{i-1} - d}{D_{i-1} - d\tan \alpha} = K$$

解得：

$$d = \dfrac{L_{i-1} - K D_{i-1}}{1 - K \tan \alpha}$$

即可通过 $R$ 确定 $d$.

则对于测线 $i$，可以通过二分法，求出最大的 $y_{i+1} = y_i + d$ 满足 $R_{i+1} \ge 0.1$，即满足测线间距最大。

对于题目所给数据，从下边界开始，可以得出一组 $34$ 条测线的解：（二分法）

> [358.5183868408203, 953.0118332752609, 1500.6703408746143, 2005.1878963911574, 2469.955788627605, 2898.1052289363024, 3292.5300583002854, 3655.8818575620235, 3990.610231581855, 4298.9645287897965, 4583.030016036086, 4844.713465287627, 5085.784274563441, 5307.859263962278, 5512.438403044078, 5700.899790302463, 5874.518101958445, 6034.45664174709, 6181.795658600697, 6317.530207469734, 6442.565840647968, 6557.750314707622, 6663.862866221392, 6761.614889303363, 6851.6645728461535, 6934.619129031264, 7011.040784531282, 7081.442654669723, 7146.299686023771, 7206.046391616304, 7261.089350493099, 7311.787153978939, 7358.495953860012, 7401.5279744365325]

对应的重叠率、每个条带的覆盖范围：

>[(0.100009053371949, 0.100009053371949), (0.100009981444800, 0.100009981444800), (0.100002717291234, 0.100002717291234), (0.100009699490757, 0.100009699490757), (0.100018566040283, 0.100018566040283), (0.100006588948690, 0.100006588948690), (0.100006627853870, 0.100006627853870), (0.100001847029824, 0.100001847029824), (0.100014058767330, 0.100014058767330), (0.100002593290124, 0.100002593290124), (0.100014179616139, 0.100014179616139), (0.100002941912047, 0.100002941912047), (0.100020765255945, 0.100020765255945), (0.100025103120718, 0.100025103120718), (0.100031295778794, 0.100031295778794), (0.100010781118767, 0.100010781118767), (0.100023484953317, 0.100023484953317), (0.100021432135690, 0.100021432135690), (0.100001218247468, 0.100001218247468), (0.100045056295035, 0.100045056295035), (0.100054959369426, 0.100054959369426), (0.100037213926518, 0.100037213926518), (0.100049031047983, 0.100049031047983), (0.100067617653482, 0.100067617653482), (0.100084156896305, 0.100084156896305), (0.100061298042675, 0.100061298042675), (0.100055475586784, 0.100055475586784), (0.100037646947762, 0.100037646947762), (0.100054224063749, 0.100054224063749), (0.100002685827518, 0.100002685827518), (0.100172656711491, 0.100172656711491), (0.100082315480932, 0.100082315480932), (0.100021434716505, 0.100021434716505)]

>(-0.00356761154603191, 685.929604525877)
(622.734374006477, 1254.62947138698)
(1196.41224005782, 1778.52644994088)
(1724.89951929846, 2261.15425411969)
(2211.74862129843, 2705.75703321076)
(2660.23952184892, 3115.33014315936)
(3073.40354886104, 3492.64186844638)
(3454.01826028059, 3840.22874447207)
(3804.64964215444, 4160.43409388580)
(4127.65390987857, 4455.40967153086)
(4425.21540172250, 4727.15026975899)
(4699.33148074707, 4977.47993048389)
(4951.85560940315, 5208.09128198240)
(5184.48142321577, 5420.53099458439)
(5398.78015558007, 5616.23395793271)
(5596.19537870769, 5796.51847828380)
(5778.06232892607, 5962.60392685450)
(5945.59957874898, 6115.60313454853)
(6099.93869993820, 6256.54948100642)
(6242.12202269157, 6386.39484824006)
(6373.09812226226, 6506.00549890044)
(6493.75503229630, 6616.19240752840)
(6604.90901104215, 6717.70100157617)
(6707.30525108174, 6811.21180955149)
(6801.63321198547, 6897.35446318176)
(6888.52895469951, 6976.70982923490)
(6968.58141739116, 7049.81574077829)
(7042.32809358923, 7117.16305034854)
(7110.26649467189, 7179.20609778207)
(7172.85177745726, 7236.36054367151)
(7230.50983763788, 7289.01532661759)
(7283.61630327965, 7337.51347956691)
(7332.54424700694, 7382.19570177294)
(7377.62072695505, 7423.36067090659)

从上边界开始排线的解：

>[221.47200441483244, 823.8854107583844, 1379.0641597195977, 1890.7109912687129, 2362.2420590092584, 2796.804978566807, 3197.2964061498824, 3566.3844958236828, 3906.535839365547, 4220.013644294711, 4508.915952964642, 4775.16746048, 5020.540880272363, 5246.6744211800415, 5455.0814046215255, 5647.145844640579, 5824.151675003875, 5987.278191981882, 6137.6139586931895, 6276.164386334944, 6403.853528148731, 6521.5311120055585, 6629.980500068197, 6729.9240204679845, 6822.035975482093, 6906.922053847351, 6985.155453858524, 7057.250627428213, 7123.69284624331, 7184.9299131164025, 7241.364958781343, 7293.3712384884675, 7341.301527045667, 7385.477355957031]

重叠率：

>[(0.10465009385582114, 0.10465009385582114), (0.10465332153657249, 0.10465332153657249), (0.10465850273693905, 0.10465850273693905), (0.10465837968985572, 0.10465837968985572), (0.10465303315655582, 0.10465303315655582), (0.10465124749879244, 0.10465124749879244), (0.10465770355483577, 0.10465770355483577), (0.10465273324083355, 0.10465273324083355), (0.10466423706387985, 0.10466423706387985), (0.1046552243473812, 0.1046552243473812), (0.1046524965058514, 0.1046524965058514), (0.10466211459487827, 0.10466211459487827), (0.10466801628885705, 0.10466801628885705), (0.10465245983017903, 0.10465245983017903), (0.1046637378902374, 0.1046637378902374), (0.10466275371089184, 0.10466275371089184), (0.1046697741039024, 0.1046697741039024), (0.10467568753782068, 0.10467568753782068), (0.1046646550989749, 0.1046646550989749), (0.10465146747462355, 0.10465146747462355), (0.10465130182583622, 0.10465130182583622), (0.1046654655006329, 0.1046654655006329), (0.10469386562311156, 0.10469386562311156), (0.1046490283147242, 0.1046490283147242), (0.10469183887637255, 0.10469183887637255), (0.1046594059897856, 0.1046594059897856), (0.10471760136456926, 0.10471760136456926), (0.10472717609435912, 0.10472717609435912), (0.10466527341785051, 0.10466527341785051), (0.10467808165762145, 0.10467808165762145), (0.10475370081589465, 0.10475370081589465), (0.1047298404490423, 0.1047298404490423), (0.10465829929598465, 0.10465829929598465)]

覆盖范围：

>(-143.56104938030023, 554.8293209030701)
(487.47313092812055, 1131.1055204771228)
(1069.0285264194342, 1662.1964559819476)
(1604.983794934604, 2151.644214787433)
(2098.9173921758274, 2602.716732160411)
(2554.126477577629, 3018.425056579094)
(2973.6453280284913, 3401.5401656043095)
(3360.2688620938707, 3754.6144487884485)
(3716.5808597892487, 4080.007478678165)
(4044.9520540477406, 4379.884267894858)
(4347.580165608677, 4656.25182999644)
(4626.481332202267, 4910.951352394371)
(4883.512489207834, 5145.678634930628)
(5120.389677072969, 5362.0008086708685)
(5338.698115400696, 5561.365535812845)
(5539.887573001678, 5745.09678150225)
(5725.302983576746, 5914.422772839896)
(5896.179671983442, 6070.471639388903)
(6053.657919178369, 6214.284714244406)
(6198.790903633291, 6346.82378633341)
(6332.546580532682, 6468.972816544993)
(6455.81504847813, 6581.544665189071)
(6569.416887315742, 6685.288706308946)
(6674.108743121904, 6780.895928030029)
(6770.596954401493, 6869.011376344926)
(6859.5159862768705, 6950.214460675322)
(6941.4662698013335, 7025.053509679627)
(7016.986698594375, 7094.020654492268)
(7086.585599691783, 7157.580112078767)
(7150.732051101791, 7216.160256210823)
(7209.848336375055, 7270.14672679085)
(7264.325444188888, 7319.896584460045)
(7314.532909748493, 7365.747298012191)
(7360.807540580048, 7408.006448505857)

直接计算法、下边界开始排线：

> [358.5217926421081, 952.335139671972, 1499.4211427168289, 2003.4567899865501, 2467.8297264255334, 2895.6610222179297, 3289.82614963261, 3652.9743091941345, 3987.546235071743, 4295.790599357135, 4579.779125484885, 4841.420512373445, 5082.473262871449, 5304.557502729887, 5509.1658695359265, 5697.673544793388, 5871.34749657591, 6031.354994873059, 6178.771456861394, 6314.587674828883, 6439.716475331856, 6554.998854340972, 6661.2096296107775, 6759.062648262666, 6849.215584581631, 6932.274360273011, 7008.797216887937, 7079.298467788465, 7144.25195486947, 7204.094233270102, 7259.22750547938, 7310.022324556157, 7356.82008463194, 7399.935315435306]

> [(0.10112613945452546, 0.10112613945452546), (0.10112613945452528, 0.10112613945452528), (0.10112613945452507, 0.10112613945452507), (0.1011261394545255, 0.1011261394545255), (0.10112613945452556, 0.10112613945452556), (0.10112613945452517, 0.10112613945452517), (0.10112613945452521, 0.10112613945452521), (0.10112613945452575, 0.10112613945452575), (0.10112613945452437, 0.10112613945452437), (0.10112613945452589, 0.10112613945452589), (0.10112613945452541, 0.10112613945452541), (0.1011261394545261, 0.1011261394545261), (0.10112613945452695, 0.10112613945452695), (0.1011261394545267, 0.1011261394545267), (0.10112613945452734, 0.10112613945452734), (0.10112613945452696, 0.10112613945452696), (0.10112613945452296, 0.10112613945452296), (0.1011261394545246, 0.1011261394545246), (0.1011261394545238, 0.1011261394545238), (0.10112613945452717, 0.10112613945452717), (0.10112613945452867, 0.10112613945452867), (0.10112613945452259, 0.10112613945452259), (0.10112613945452252, 0.10112613945452252), (0.1011261394545259, 0.1011261394545259), (0.1011261394545228, 0.1011261394545228), (0.10112613945452734, 0.10112613945452734), (0.10112613945452234, 0.10112613945452234), (0.10112613945452528, 0.10112613945452528), (0.1011261394545296, 0.1011261394545296), (0.1011261394545278, 0.1011261394545278), (0.1011261394545309, 0.1011261394545309), (0.10112613945453328, 0.10112613945453328), (0.10112613945453185, 0.10112613945453185)]

> (5.684341886080802e-14, 685.9328625579885)
(622.0255305631295, 1253.9821378218987)
(1195.1036922611765, 1777.3314513580108)
(1723.086167703769, 2259.4982560801377)
(2209.521549482229, 2703.7232155151974)
(2657.679190410756, 3112.9919844401034)
(3070.5711769852333, 3490.055275594041)
(3450.972573744207, 3837.447347335353)
(3801.440074595246, 4157.503036499355)
(4124.329186463041, 4452.373450935654)
(4421.810060751256, 4724.040427195151)
(4695.882079022082, 4974.329850537493)
(4948.387290924437, 5204.923926783268)
(5181.022794687722, 5417.372488490619)
(5395.352143390928, 5613.103411445534)
(5592.815853669147, 5793.432211475521)
(5774.741087486914, 5959.570886087224)
(5942.350572050012, 6112.636060353028)
(6096.770817806835, 6253.65649179549)
(6239.039689772854, 6383.579984710238)
(6370.113383065362, 6503.279760398812)
(6490.872849531377, 6613.560326126033)
(6602.129718662342, 6715.162882247421)
(6704.631752590326, 6808.770303848195)
(6799.067871829001, 6895.011730375656)
(6886.072785537611, 6974.466794112078)
(6966.231257428125, 7047.669515907833)
(7040.08203598693, 7115.1118943581605)
(7108.121475426232, 7177.247212546576)
(7170.806871701752, 7234.49308457968)
(7228.559536018225, 7287.234262389266)
(7281.767626479859, 7335.825221666363)
(7330.788756917402, 7380.592544307371)
(7375.95240042585, 7421.837113384827)

这里可以画个图，把海平面上条带画出来。


还有一种无解的情况：在贪心加线到最后时，当前的最后一条线还无法覆盖到另一边界，但再加一条线就无法满足重叠率要求。

根据贪心思想，目前的测线排布已经尽可能远，但仍无法覆盖到最后边界，说明只用当前数量的测线是不行的，必须加线。但是由于剩余空间过少，无法在满足重叠率要求的情况下添加最后一根线来覆盖另一边界。

那么：可以稍微放宽一点要求，让目前的测线相互靠得更加紧密一些，腾出安放最后一条线的空间。

具体方法：修改约束为重叠率 $R_i \ge lowbound$，其中 $lowbound = 0.1 + \Delta$，找到最小的 $\Delta$ 使得测线排布能够覆盖整个海域，且测线数量最少（等于原测线数量加一）。考虑到测线数量与 $\Delta$ 也存在单调性，$\Delta$ 越大，间距越小，测线数量越大，此处也可以使用二分法求解。

另一个调整策略是：从初始测线处腾出空间，以在末尾安插最后一条测线。

# Question4

给出的是网格数据，使用反距离加权法进行空间内插补全计算所需的点。经过尝试，取 $p=5$ 时效果较优，将 $loss$ 定义为：$loss = \sum (estimate - origin)^2$，此时对于超过五万个样本点，总 $loss = 84.92$，平均 $loss = 0.00168$，可以几乎认为一致。

第三问中，已经说明了测线沿着等深线排布是较优的。第四问中的海底面较为复杂，需要计算一个大致的等深线方向。



（这个深度一致指数效果比较差，可以忽略）
定义深度一致指数为：以 $1000$ 条成 $\beta$ 角的等距直线交整个海域进行采样。在直线上等距选取 $1000$ 个采样点，得到一个深度序列，计算出该序列的方差。所有直线的方差和即为深度一致指数。

深度一致指数越接近 $0$，说明该方向上深度变化越小。选取深度一致指数最小的 $\beta$ 作为布线方向。

现在考虑在这个海平面情况下，如何计算在某点处的 $L,R,W$.

定义 $x$ 减小的方向为正方向。这样向下边界的覆盖为 $L$，向 上边界的覆盖为 $R$，与前三问一致。

设当前点为 $(x,y)$，要求在垂直于测线的方向上，距离 $d \in [-L,0]$ 的所有点，满足 $D > \dfrac{d}{\tan \varphi}$，找到最大的 $L$. 另一侧同理。

要求是整个范围内满足，一旦出现不满足就需要停止了。

如果要使用二分，则要求存在单调性：

$$\dfrac{\partial D}{\partial d} - \dfrac{1}{\tan \varphi} \le 0$$

考虑到海底平面的变化幅度较小，这个式子是恒成立的，因此我们可以采用二分来确定测线上某点的覆盖范围。

数据化证明：经过验证，相邻数据点最大深度差为 $2.01 \mathrm{m}$，而距离差为 $0.02 \times 1852 = 37.04 \mathrm{m}$，显然原式成立。

这里补充一个图：$\beta = 45^{\circ}$ 时，海域中心点 $d$ 与 $D - \dfrac{d}{\tan \varphi}$ 的关系。


基于此，就可以设计一个通过**二分**来计算两侧覆盖范围的函数。

那么对于两条测线，要如何计算其重叠率情况呢？

在一个测线上划分采样点，计算采样点在另一条测线上的投影，若投影在另一条测线上(也就是公共区域)，则计算其重叠率。

可以考虑自适应采样，因为深度变化剧烈的位置可能需要更多的采样，不过这个以后再说吧。
首先每 $50$ 米设置一个采样点。

对深度计算采用一个缓存策略，因为每次深度计算都是 5w 个点一起用上来插值还是有点慢的，对于 $(x,y)$，保存 $(\lfloor \dfrac{x+3}{6} \rfloor,\lfloor \dfrac{y+3}{6} \rfloor)$ 作为其缓存索引。

考虑到原始数据间隔为 $37$ 米，以 $6$ 米为粒度缓存没有什么问题。
经过计算，随机选取了 $10000$ 个点进行计算，缓存后数据与缓存前的最小二乘 loss 总计为 $60$，平均差值极小，可以接受。

具体方法，划分 $6 \times 6$ 网格，每次计算某点时，寻找与其最近的网格整点作为其深度。提前缓存好网格即可查表得到深度。

接下来需要考虑如何排线，此时需要考虑三个指标：

- 测线总长度
- 海域漏测率
- 重叠超出率（注意这里计算的是超出部分长度占测线总长度的比例，更能反映重叠情况性质）

我们希望：总长度、漏测率、重叠超出率都**尽可能小**。

漏测量的计算方法：随机选取 $100000$ 个点，计算其是否被测线覆盖。即计算出每个点离最近测线的距离 $d$，然后使用 $D > \dfrac{d}{\tan \varphi}$ 计算. 漏测点数除以总点数即得漏测量。

重叠超出量：在重叠部分采样，计算所有相邻的测线的重叠率，在两个散点之间采用线性拟合来建立一个函数，从而估计出重叠部分超出 $20\%$ 的总长度。

现在考虑如何排线，首先考虑初始测线情况：

若 $\beta < \dfrac{\pi}{2}$，从左下角开始依次排线，通过二分法找到最远的、恰好能覆盖原点 $O(0,0)$ 的测线。

若 $\beta > \dfrac{\pi}{2}$，从右下角开始依次排线。


确定初始测线后，考虑后续测线如何安置。

可以发现，两测线间的间距 $d$ 增大时，整体的重叠率下降，漏测率上升，重叠超出率下降。


希望找到一种方法，能够综合考虑相邻两条测线的间距对测线总长度、海域漏测率、重叠超出率的影响，进行排线。

假设当前已经确定了间距 $d$，则可以估算出相邻两条测线之间的漏测面积、重叠区域重叠率超出 $20\%$ 的长度。

具体地，我们在测线上选取若干采样点，获得了重叠率采样序列 $ratio$，对于采样点 $i$，若 $ratio_i < 0$，则该采样点处存在漏测；若 $ratio_i > 0.2$，则该采样点处存在重叠率过高。

定义 $P = \sum |ratio_i| \times width_i \text{ where } ratio_i < 0$，这是估计了漏测区域占当前测线覆盖区域的比例。其中 $width_i$ 为当前测线的覆盖宽度，$\Delta L$ 为采样点的步长。$S$ 为当前测线的预估覆盖面积，计算方法为：$S = \sum width_i \times \Delta L$. 化简即得 $P = \sum |ratio_i| \text{ where } ratio_i < 0$.

定义 $Q = \Delta L \times num \times \dfrac{1}{Len}$，其中 $num$ 为 $ratio_i > 0.2$ 的采样点数，$Len$ 为当前测线长度，$Q$ 估计的是当前测线重叠区域超出 $0.2$ 部分长度所占当前测线长度的比例。




则可以用 $T = \dfrac{P}{Q}$ 来表示当前测线对海域漏测率、重叠超出率贡献的大致比例情况。可以发现，随着 $d$ 增大，漏测率增大，$P$ 增大；重叠率减小，$Q$ 减小，则 $T$ 增大。

预先设置一个 $T$ 值，代表希望得到的漏测率对重叠超出率的比例，而后使用二分法进行排线，求得 $d$ 使得 $\dfrac{P}{Q} \le T$ 且 $\dfrac{P}{Q}$ 最大，使得每条测线对漏测率、重叠超出率的贡献接近 $T$ 值代表的关系。

改变不同的 $T$ 值，即可得到不同间距。例如 $T$ 较大时，$P$ 大于 $Q$，漏测率相对大小高于重叠超出率相对大小，说明此时测线排布较为稀疏。

固定 $\beta$，在不同 $T$ 值下求解，即可求得几组疏密程度不同、漏测率、重叠超出率相应变化的测线组。
枚举 $\beta$，对每个 $\beta$ 再计算不同 $T$ 值下的解，获得若干组测线组后，对测线组进行综合评价分析，以确定最优的测线组。

使用 TOPSIS 法确定最优解组。

在实际测量中，应当优先考虑覆盖尽可能多的海域，其余两个指标重要性相对较低，因此设置权值 $W = [0.2,0.5,0.3]$.

>10 5000 412322.9637477178 0.0639 0.2601774480257779
10 2000 446207.447768792 0.03686 0.3227534956840702
10 500 484644.97097578313 0.0127 0.39195947397792075
10 100 508413.23994059325 0.00324 0.4348145419498167
20 5000 418518.0683307921 0.05403 0.22928631326901894
20 2000 444482.97170284606 0.02968 0.2848504720586053
20 500 474204.1663760035 0.01053 0.35387205665839405
20 100 492903.63016225083 0.00275 0.3998476487228384
30 5000 422257.6950572781 0.04863 0.20642705009208537
30 2000 445512.82722225116 0.02622 0.2666335816699192
30 500 472386.1871758995 0.00876 0.3395757002017608
30 100 489793.50908138754 0.00241 0.3877411963527947
40 5000 417902.4774619697 0.05681 0.20068432979924442
40 2000 445155.0353617381 0.03037 0.2555260362927552
40 500 475611.9979786122 0.01055 0.32994803429607444
40 100 494839.3460351145 0.00269 0.3826708651566769
50 5000 410153.107078025 0.06976 0.2289274309517094
50 2000 443870.7830816348 0.04034 0.2800389245472378
50 500 481827.67548644234 0.01324 0.342690611668083
50 100 505848.2417701624 0.00324 0.3878580948147782
60 5000 402133.42526798986 0.08501 0.25368415863334204
60 2000 443771.7766536939 0.0495 0.3103273482445746
60 500 491377.53604632546 0.01825 0.37474149013772245
60 100 521723.46379377705 0.00424 0.41635155598828033
70 5000 394451.922311807 0.09569 0.2755445524326068
70 2000 442768.760291073 0.05653 0.3409302059857913
70 500 502685.3986376083 0.02145 0.41665311603846084
70 100 541312.4949283272 0.00551 0.46333333391157255
80 5000 388393.29579463217 0.10682 0.29802032213396884
80 2000 442060.1396805495 0.06419 0.3728712261162787
80 500 514250.44550309377 0.02579 0.4616704671236765
80 100 563213.0282900742 0.00765 0.5170349417809481
90 5000 392624.0 0.10748 0.3457031088510499
90 2000 451888.0 0.06824 0.422789270479303
90 500 533376.0 0.02684 0.5131844550116648
90 100 592640.0 0.0071 0.5762258520228188
100 5000 391207.2950234107 0.11032 0.33169625981825307
100 2000 450202.8722063753 0.07293 0.4222493159234808
100 500 535060.8845413231 0.03182 0.5267071751728651
100 100 597451.2157722039 0.01115 0.5949891446084937
110 5000 392594.7699472151 0.10872 0.36523140463650927
110 2000 452376.3561973288 0.07149 0.465842331372584
110 500 541926.2162289261 0.03012 0.585536283622925
110 100 610993.4016899442 0.01 0.6610549649298492
120 5000 393906.13344413886 0.1074 0.4041626771134242
120 2000 455158.15112658375 0.07267 0.505380790498858
120 500 549057.0294253628 0.02888 0.623647595440707
120 100 624371.383209393 0.00921 0.7024739491366212
130 5000 396903.4221620707 0.10483 0.4240159382743596
130 2000 459116.8654804375 0.06963 0.5269348607556871
130 500 555786.7394677309 0.0285 0.6462729512525404
130 100 634895.1196867874 0.00881 0.7266142602986361
140 5000 400274.8340916149 0.10092 0.42989513016315306
140 2000 461312.75270485104 0.06541 0.5336063783114435
140 500 556443.6393110652 0.02779 0.6546286126519697
140 100 634879.1908177334 0.00767 0.7363142492802353
150 5000 401008.6030042845 0.08966 0.4021565744146674
150 2000 455689.6075132504 0.05959 0.5060836949485014
150 500 539924.4754254194 0.026 0.6280941393046775
150 100 609307.524175418 0.00779 0.7125138277776295
160 5000 401795.520410111 0.08068 0.3207325076523209
160 2000 447891.73825258174 0.05364 0.41711935008722334
160 500 515373.75682384707 0.02275 0.5364124124163595
160 100 567304.7206423979 0.00993 0.6182875383428841
170 5000 397526.2538062613 0.08067 0.2845214733639639
170 2000 439975.88471505936 0.05104 0.36723325374206145
170 500 497094.5339179005 0.02527 0.4691082318133291
170 100 537675.125582906 0.01161 0.5382360114166416

最终通过 TOPSIS 法选出的方案是：

>30, 2000, 445512.82722225116, 0.02622, 0.2666335816699192
>[84.27060082424256, 248.30720864794364, 407.9548123811725, 564.1195556227807, 716.8602548489171, 867.0495594260901, 1014.8881238596787, 1160.8929073894822, 1305.4071913322623, 1448.2893347131167, 1589.8743109088996, 1730.6445918568156, 1870.4482799942673, 2009.9090956424475, 2148.408053858484, 2286.864689440734, 2425.1155243949725, 2563.0014008031394, 2700.9634116752077, 2840.3176976439036, 2982.489113468121, 3126.817862829633, 3273.2395630697783, 3420.8278429338507, 3569.537663027204, 3721.8674612111, 3876.30791945716, 4032.2292516066714, 4192.326978337502, 4355.3751827788365, 4522.079968469296, 4693.115607509405, 4866.733734505627, 5045.189831642589, 5228.5595673349335, 5415.617333091212, 5607.978993511904, 5805.666981239585, 6009.184349763875, 6217.765447600186, 6432.602907488335, 6653.850858138867, 6882.808079233382, 7118.3480521915335, 7362.120241223628, 7613.385557598045, 7873.398227167054, 8141.757807399445, 8419.951500478326, 8708.033817037634, 9006.790636209204, 9316.646947094778, 9638.072752498436, 9969.84258150739, 10312.74855518575, 10666.801581610165, 11033.22207024859, 11412.355672719936, 11804.886986712068, 12211.241210796812, 12632.145400117373, 13067.159520063838, 13512.184500094623, 13967.726349317449, 14433.785167137496, 14909.792631054514, 15394.561378922297, 15885.025563752468, 16382.937915022276, 16884.800102544177, 17391.155762826296, 17897.74646780012, 18401.43217825366, 18902.49177629943, 19395.057466864513, 19886.401528021663, 20373.77780700193, 20855.70752733905, 21329.20850940838, 21793.072947742432, 22090.74140645977]