看论文看到了这距离的作用，就试着学了一下，然后又恰巧发现这东西是个二维的dp 就用之前学的dp优化方法搞了一下。
这个距离的定义我就不讲了，数学描述烧脑子，有兴趣自己去看。直觉定义我放这儿。
一个人在遛狗，他们走在各自的道路上。他们可能有着不同的速度，但是都不能往回走。最终的目的，就是求满足要求的绳子的最小长度。
作用。这个重要，用来衡量两个曲线（空间路径）的相似性，曲线的相似性，我感觉我回到了泛函分析（晕）
文件结构 代码首先定义一个计算距离的py文件，其实就是把三种距离的计算打包在一个py文件里面，主要就是看你想用啥距离测度来描述两个点的距离（曼哈顿，欧式。切比雪夫、马氏、测地巴拉巴拉）
distance_lib.py
import numpy as np
import math
from numba import jit
@jit(nopython=True, fastmath=True)
def euclidean(p: np.ndarray, q: np.ndarray) -> float:
d = p - q
return math.sqrt(np.dot(d, d))
@jit(nopython=True, fastmath=True)
def haversine(p: np.ndarray,
q: np.ndarray) -> float:
"""
Vectorized haversine distance calculation
:p: Initial location in radians
:q: Final location in radians
:return: Distance
"""
d = q - p
a = math.sin(d[0]/2.0)**2 + math.cos(p[0]) * math.cos(q[0])
* math.sin(d[1]/2.0)**2
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1.0 - a))
return c
@jit(nopython=True, fastmath=True)
def earth_haversine(p: np.ndarray, q: np.ndarray) -> float:
"""
Vectorized haversine distance calculation
:p: Initial location in degrees [lat, lon]
:q: Final location in degrees [lat, lon]
:return: Distances in meters
"""
earth_radius = 6378137.0
return haversine(np.radians(p), np.radians(q)) * earth_radius
test1.py
import numpy as np
from typing import Callable, Dict
from numba import jit
from timeit import default_timer as timer
from distance_lib import euclidean, haversine, earth_haversine
class DiscreteFrechet(object):
"""
Calculates the discrete Fréchet distance between two poly-lines using the
original recursive algorithm
"""
def __init__(self, dist_func):
"""
Initializes the instance with a pairwise distance function.
:param dist_func: The distance function. It must accept two NumPy
arrays containing the point coordinates (x, y), (lat, long)
"""
self.dist_func = dist_func
self.ca = np.array([0.0])
def distance(self, p: np.ndarray, q: np.ndarray) -> float:
"""
Calculates the Fréchet distance between poly-lines p and q
This function implements the algorithm described by Eiter & Mannila
:param p: Poly-line p
:param q: Poly-line q
:return: Distance value
"""
def calculate(i: int, j: int) -> float:
"""
Calculates the distance between p[i] and q[i]
:param i: Index into poly-line p
:param j: Index into poly-line q
:return: Distance value
"""
if self.ca[i, j] > -1.0:
return self.ca[i, j]
d = self.dist_func(p[i], q[j])
if i == 0 and j == 0:
self.ca[i, j] = d
elif i > 0 and j == 0:
self.ca[i, j] = max(calculate(i-1, 0), d)
elif i == 0 and j > 0:
self.ca[i, j] = max(calculate(0, j-1), d)
elif i > 0 and j > 0:
self.ca[i, j] = max(min(calculate(i-1, j),
calculate(i-1, j-1),
calculate(i, j-1)), d)
else:
self.ca[i, j] = np.infty
return self.ca[i, j]
n_p = p.shape[0]
n_q = q.shape[0]
self.ca = np.zeros((n_p, n_q))
self.ca.fill(-1.0)
return calculate(n_p - 1, n_q - 1)
@jit(nopython=True)
def _get_linear_frechet(p: np.ndarray, q: np.ndarray,
dist_func: Callable[[np.ndarray, np.ndarray], float])
-> np.ndarray:
n_p = p.shape[0]
n_q = q.shape[0]
ca = np.zeros((n_p, n_q), dtype=np.float64)
for i in range(n_p):
for j in range(n_q):
d = dist_func(p[i], q[j])
if i > 0 and j > 0:
ca[i, j] = max(min(ca[i - 1, j],
ca[i - 1, j - 1],
ca[i, j - 1]), d)
elif i > 0 and j == 0:
ca[i, j] = max(ca[i - 1, 0], d)
elif i == 0 and j > 0:
ca[i, j] = max(ca[0, j - 1], d)
elif i == 0 and j == 0:
ca[i, j] = d
else:
ca[i, j] = np.infty
return ca
class LinearDiscreteFrechet(DiscreteFrechet):
def __init__(self, dist_func):
DiscreteFrechet.__init__(self, dist_func)
# JIT the numba code
self.distance(np.array([[0.0, 0.0], [1.0, 1.0]]),
np.array([[0.0, 0.0], [1.0, 1.0]]))
def distance(self, p: np.ndarray, q: np.ndarray) -> float:
n_p = p.shape[0]
n_q = q.shape[0]
self.ca = _get_linear_frechet(p, q, self.dist_func)
return self.ca[n_p - 1, n_q - 1]
@jit(nopython=True)
def distance_matrix(p: np.ndarray,
q: np.ndarray,
dist_func: Callable[[np.array, np.array], float])
-> np.ndarray:
n_p = p.shape[0]
n_q = q.shape[0]
dist = np.zeros((n_p, n_q), dtype=np.float64)
for i in range(n_p):
for j in range(n_q):
dist[i, j] = dist_func(p[i], q[j])
return dist
class VectorizedDiscreteFrechet(DiscreteFrechet):
def __init__(self, dist_func):
DiscreteFrechet.__init__(self, dist_func)
self.dist = np.array([0.0])
def distance(self, p: np.ndarray, q: np.ndarray) -> float:
"""
Calculates the Fréchet distance between poly-lines p and q
This function implements the algorithm described by Eiter & Mannila
:param p: Poly-line p
:param q: Poly-line q
:return: Distance value
"""
def calculate(i: int, j: int) -> float:
"""
Calculates the distance between p[i] and q[i]
:param i: Index into poly-line p
:param j: Index into poly-line q
:return: Distance value
"""
if self.ca[i, j] > -1.0:
return self.ca[i, j]
d = self.dist[i, j]
if i == 0 and j == 0:
self.ca[i, j] = d
elif i > 0 and j == 0:
self.ca[i, j] = max(calculate(i-1, 0), d)
elif i == 0 and j > 0:
self.ca[i, j] = max(calculate(0, j-1), d)
elif i > 0 and j > 0:
self.ca[i, j] = max(min(calculate(i-1, j),
calculate(i-1, j-1),
calculate(i, j-1)), d)
else:
self.ca[i, j] = np.infty
return self.ca[i, j]
n_p = p.shape[0]
n_q = q.shape[0]
self.ca = np.zeros((n_p, n_q))
self.ca.fill(-1.0)
self.dist = distance_matrix(p, q, dist_func=self.dist_func)
return calculate(n_p - 1, n_q - 1)
@jit(nopython=True)
def compression_get_linear_frechet(p: np.ndarray, q: np.ndarray,
dist_func: Callable[[np.ndarray, np.ndarray], float])
-> np.ndarray:
n_p = p.shape[0]
n_q = q.shape[0]
ca = np.zeros((n_q), dtype=np.float64)
for j in range(n_q):
ca[j] = dist_func(p[0], q[j])
for i in range(1,n_p):
temp = ca[0]
# 初始化最开始的
d = dist_func(p[i], q[0])
ca[0] = max(ca[0], d)
for j in range(1,n_q):
left_up = temp
d = dist_func(p[i], q[j])
temp = ca[j]
ca[j] = max(min(ca[j],left_up,ca[j - 1]), d)
return ca
class compressionLinearDiscreteFrechet(DiscreteFrechet):
def __init__(self, dist_func):
DiscreteFrechet.__init__(self, dist_func)
# JIT the numba code
self.distance(np.array([[0.0, 0.0], [1.0, 1.0]]),
np.array([[0.0, 0.0], [1.0, 1.0]]))
def distance(self, p: np.ndarray, q: np.ndarray) -> float:
self.ca = compression_get_linear_frechet(p, q, self.dist_func)
return self.ca[-1]
def main():
np.set_printoptions(precision=4)
distance_fun = earth_haversine
linear_frechet = LinearDiscreteFrechet(distance_fun)
slow_frechet = DiscreteFrechet(distance_fun)
VDF = VectorizedDiscreteFrechet(distance_fun)
compression_linear = compressionLinearDiscreteFrechet(distance_fun)
p = np.array([
[ 42.31644861, -83.77730583],
[ 42.31631778, -83.77754194],
[ 42.31619611, -83.77816083],
[ 42.31604194, -83.77894 ],
[ 42.31589861, -83.7797925 ],
[ 42.31565222, -83.78029194],
[ 42.31527111, -83.780575 ],
[ 42.31491194, -83.78094639],
[ 42.31462333, -83.78133361],
[ 42.31411778, -83.78156806],
[ 42.31361861, -83.78157389],
[ 42.31300028, -83.78156694],
[ 42.31235028, -83.78153222],
[ 42.31171806, -83.78150528],
[ 42.31097083, -83.78147556],
[ 42.31028861, -83.78144833],
[ 42.30959611, -83.78140667],
[ 42.30890083, -83.78137667],
[ 42.30821972, -83.78134028],
[ 42.30762528, -83.78131917],
[ 42.30691111, -83.781295 ],
[ 42.30626583, -83.78123278],
[ 42.30579611, -83.78121444],
[ 42.30541694, -83.78127667],
[ 42.30485833, -83.78123083],
[ 42.30413889, -83.78119778],
[ 42.30312917, -83.78116222],
[ 42.30247667, -83.78113083],
[ 42.30210861, -83.78116667],
[ 42.30192611, -83.78127389],
[ 42.30147583, -83.78119139],
[ 42.30077167, -83.78109194],
[ 42.30028778, -83.7810625 ],
[ 42.29992 , -83.7812025 ],
[ 42.29948083, -83.78110111],
[ 42.29883806, -83.78105444],
[ 42.29824833, -83.78105167],
[ 42.29765167, -83.78105667],
[ 42.29700667, -83.78105194],
[ 42.29634194, -83.78104889],
[ 42.29573611, -83.7810525 ],
[ 42.295395 , -83.78100861],
[ 42.29534111, -83.78095944],
[ 42.29527 , -83.78094 ],
[ 42.29494278, -83.78086833],
[ 42.29426028, -83.78081528],
[ 42.29358333, -83.78078778],
[ 42.29294528, -83.78075722],
[ 42.29230917, -83.78073306],
[ 42.29162361, -83.78072333],
[ 42.29089417, -83.78071083],
[ 42.29000861, -83.78067528],
[ 42.28929556, -83.78065222],
[ 42.28855944, -83.78064944],
[ 42.28785778, -83.78065806],
[ 42.28723694, -83.78065444],
[ 42.28653778, -83.78063944],
[ 42.28624111, -83.78061833],
[ 42.286215 , -83.78061333],
[ 42.2862275 , -83.78057944],
[ 42.28612 , -83.78060611],
[ 42.28583833, -83.78057194],
[ 42.28545444, -83.7805525 ],
[ 42.2850025 , -83.78053639],
[ 42.28455472, -83.78052861],
[ 42.283995 , -83.78050056],
[ 42.28351194, -83.78048444],
[ 42.28297472, -83.78047333],
[ 42.28236417, -83.78045944],
[ 42.28184889, -83.78045667],
[ 42.28155556, -83.78045972],
[ 42.28151444, -83.78046194],
[ 42.2815175 , -83.78046 ],
[ 42.2813275 , -83.78045028],
[ 42.28095361, -83.78043917],
[ 42.28050833, -83.78044917],
[ 42.280135 , -83.78044611],
[ 42.27977472, -83.78042778],
[ 42.27919556, -83.78023417],
[ 42.27864194, -83.77985167],
[ 42.278055 , -83.77948111],
[ 42.27750944, -83.77912028],
[ 42.276865 , -83.77870917],
[ 42.27639083, -83.77840111],
[ 42.27569194, -83.77795083],
[ 42.27524083, -83.77764583],
[ 42.27509861, -83.77755361],
[ 42.27511028, -83.77751083],
[ 42.27509667, -83.77747278],
[ 42.27495222, -83.7773675 ],
[ 42.27458694, -83.77713028]])
q = np.array([
[ 42.31661889, -83.77759694],
[ 42.31651444, -83.77805778],
[ 42.31639167, -83.77864528],
[ 42.31627694, -83.77921639],
[ 42.31612361, -83.77979778],
[ 42.31601167, -83.78022333],
[ 42.31587083, -83.78046167],
[ 42.31573444, -83.78056583],
[ 42.31549833, -83.78067222],
[ 42.3152775 , -83.780815 ],
[ 42.31496194, -83.78111833],
[ 42.31475 , -83.78141778],
[ 42.31445972, -83.78161111],
[ 42.31412833, -83.78162167],
[ 42.31372361, -83.78162611],
[ 42.31325667, -83.78158194],
[ 42.31257306, -83.78156139],
[ 42.31207222, -83.78153778],
[ 42.3114975 , -83.78147417],
[ 42.3110025 , -83.78147611],
[ 42.310545 , -83.78148778],
[ 42.30996028, -83.78151278],
[ 42.30964889, -83.78154667],
[ 42.30927861, -83.78154222],
[ 42.30889583, -83.78153222],
[ 42.30830583, -83.78148917],
[ 42.30787444, -83.78151389],
[ 42.30739361, -83.78149083],
[ 42.30688833, -83.78149306],
[ 42.30645611, -83.78140167],
[ 42.30617917, -83.78143528],
[ 42.30593583, -83.7815 ],
[ 42.30538944, -83.78145306],
[ 42.3048975 , -83.78143833],
[ 42.30437361, -83.78140833],
[ 42.30387111, -83.78138111],
[ 42.30336361, -83.78134694],
[ 42.30279222, -83.78133222],
[ 42.3024175 , -83.78134167],
[ 42.30200111, -83.78141333],
[ 42.30142417, -83.78128833],
[ 42.30099889, -83.78121667],
[ 42.30059 , -83.78115861],
[ 42.30020167, -83.78121778],
[ 42.29977306, -83.78127833],
[ 42.29939833, -83.78119194],
[ 42.29899917, -83.78111944],
[ 42.29854361, -83.78108361],
[ 42.29815611, -83.78103944],
[ 42.29781111, -83.78100278],
[ 42.29738556, -83.78100111],
[ 42.29699972, -83.78100667],
[ 42.296655 , -83.78100444],
[ 42.29633833, -83.78099861],
[ 42.29605778, -83.78096972],
[ 42.29586694, -83.78095194],
[ 42.29575806, -83.78089528],
[ 42.29561083, -83.78085861],
[ 42.29547028, -83.78088333],
[ 42.29539 , -83.78079861],
[ 42.295295 , -83.78078528],
[ 42.29517639, -83.78075333],
[ 42.2949275 , -83.78072667],
[ 42.29467417, -83.78067917],
[ 42.29445778, -83.78064917],
[ 42.29409972, -83.78061444],
[ 42.293735 , -83.78059833],
[ 42.29332611, -83.78060528],
[ 42.29283 , -83.78062111],
[ 42.29163472, -83.78061194],
[ 42.291115 , -83.78057333],
[ 42.29058611, -83.78053583],
[ 42.28991556, -83.78050139],
[ 42.28944694, -83.78049 ],
[ 42.28895194, -83.7804875 ],
[ 42.28846889, -83.78049167],
[ 42.28796361, -83.78048278],
[ 42.28730917, -83.78049444],
[ 42.28680806, -83.78053278],
[ 42.28629917, -83.78051222],
[ 42.28586972, -83.78049972],
[ 42.28529083, -83.78052472],
[ 42.28475306, -83.78054 ],
[ 42.28422444, -83.78052833],
[ 42.28372139, -83.78050028],
[ 42.28336 , -83.78042 ],
[ 42.28331167, -83.78041917],
[ 42.28296583, -83.78043139],
[ 42.28257361, -83.78042306],
[ 42.28213528, -83.780415 ],
[ 42.28167583, -83.78038389],
[ 42.28125306, -83.78035861],
[ 42.27966083, -83.78032361],
[ 42.27943167, -83.78029611],
[ 42.27922417, -83.78011056],
[ 42.27854833, -83.77966083],
[ 42.27816278, -83.77938583],
[ 42.27776444, -83.77910083],
[ 42.27735694, -83.77880583],
[ 42.27690417, -83.7785075 ],
[ 42.27637639, -83.77812556],
[ 42.27598167, -83.77782778],
[ 42.27558917, -83.77756861],
[ 42.27521528, -83.77733417],
[ 42.27487861, -83.77709444],
[ 42.274515 , -83.77680611],
[ 42.27439389, -83.77672333]])
start = timer()
distance = slow_frechet.distance(p, q)
end = timer()
slow_time = end - start
print("Slow time and ferechet distance:n {:.8f}".format(slow_time),end=" ")
print(distance)
start = timer()
distance = linear_frechet.distance(p, q)
end = timer()
linear_time = end - start
print("Linear time and ferechet distance:n {:.8f}".format(linear_time),end=" ")
print(distance)
start = timer()
distance = VDF.distance(p, q)
end = timer()
VDF_time = end - start
print("VDF time and ferechet distance:n {:.8f}".format(VDF_time),end=" ")
print(distance)
start = timer()
distance = compression_linear.distance(p, q)
end = timer()
compression_linear_time = end - start
print("compression_linear time and ferechet distance :n {:.8f}".format(compression_linear_time),end=" ")
print(distance)
print()
print("time ratio(based on linear):")
print("Linear : compression_linear : :slow : VDA ")
print("{:.2f} : {:.2f} : {:.2f} : {:.2f} ".format(linear_time / linear_time,compression_linear_time / linear_time,slow_time / linear_time,VDF_time / linear_time))
if __name__ == "__main__":
main()
其实干了啥呢，原始的 DiscreteFrechet 是从后往前递归实现的，然后改成 dp 从前往后实现得到 LinearDiscreteFrechet ，然后对 dp 做了点优化减少了空间复杂度 得到compressionLinearDiscreteFrechet，后来又想着先把所有距离都算出来，利用查表法看能不能降低时间 VectorizedDiscreteFrechet，结果表现超级拉跨
结果Slow time and ferechet distance: 0.02692690 83.23780104754721 Linear time and ferechet distance: 0.00266960 83.23780104754721 VDF time and ferechet distance: 0.21261920 83.23780104754721 compression_linear time and ferechet distance : 0.00274860 83.23780104754721 time ratio(based on linear): Linear : compression_linear : :slow : VDA 1.00 : 1.03 : 10.09 : 79.64另外一组曲线（供测试）
最后在提供一组曲线，大家测试下
p = np.array([[ 42.27764194, -83.69931 ],
[ 42.27735028, -83.69914667],
[ 42.27678667, -83.69895222],
[ 42.27631444, -83.69889278],
[ 42.27580917, -83.69888194],
[ 42.27528806, -83.69894139],
[ 42.27462333, -83.698925 ],
[ 42.27417667, -83.69887167],
[ 42.27371028, -83.69883389],
[ 42.27326722, -83.69875833],
[ 42.27293333, -83.69871 ],
[ 42.27260083, -83.698555 ],
[ 42.27252667, -83.69851111],
[ 42.27253611, -83.69829611],
[ 42.27263194, -83.69801361],
[ 42.27283111, -83.69780778],
[ 42.2731525 , -83.69777056],
[ 42.27344667, -83.69794889],
[ 42.27366083, -83.69829139],
[ 42.27385444, -83.69872417],
[ 42.27410694, -83.69931611],
[ 42.27419444, -83.69977167],
[ 42.27431083, -83.70023639],
[ 42.274425 , -83.70078917],
[ 42.27458694, -83.70132583],
[ 42.2747225 , -83.70187472],
[ 42.27478528, -83.70254 ],
[ 42.27466083, -83.70296472],
[ 42.2744675 , -83.7033175 ],
[ 42.27416083, -83.70364194],
[ 42.27395389, -83.70386194],
[ 42.27376833, -83.70406583],
[ 42.27352111, -83.70428028],
[ 42.27334083, -83.70450972],
[ 42.27321917, -83.70478194],
[ 42.27316361, -83.70501722],
[ 42.27314528, -83.70533861],
[ 42.27324861, -83.70541694],
[ 42.27351222, -83.70534194],
[ 42.273705 , -83.70534722],
[ 42.27400667, -83.70527111],
[ 42.27421361, -83.7051425 ],
[ 42.27430278, -83.70497889],
[ 42.27441833, -83.70490389],
[ 42.27453583, -83.704895 ],
[ 42.27475278, -83.70488778],
[ 42.27492472, -83.70493556],
[ 42.27510028, -83.70497278],
[ 42.2752525 , -83.70503917],
[ 42.27542472, -83.70511444],
[ 42.27550639, -83.70519222],
[ 42.27555194, -83.70534667],
[ 42.27552194, -83.70549278],
[ 42.27546694, -83.70568444],
[ 42.27534833, -83.70591167],
[ 42.27536472, -83.70607 ],
[ 42.2753675 , -83.70621972],
[ 42.27536694, -83.70642444],
[ 42.27538444, -83.70660611],
[ 42.27535861, -83.70683833],
[ 42.275355 , -83.70706194],
[ 42.27547472, -83.70726167],
[ 42.27542306, -83.7075275 ],
[ 42.27534278, -83.70771972],
[ 42.27527111, -83.70786361],
[ 42.27521778, -83.70804306],
[ 42.27517139, -83.70821833],
[ 42.27513167, -83.7084025 ],
[ 42.27510444, -83.70860556],
[ 42.27506056, -83.7088725 ],
[ 42.27509111, -83.70900833],
[ 42.27515028, -83.70914944],
[ 42.27523528, -83.70925528],
[ 42.27538472, -83.70936833],
[ 42.27545833, -83.70943417],
[ 42.27551972, -83.7095125 ],
[ 42.27556361, -83.70954667],
[ 42.27561944, -83.70959194],
[ 42.27566028, -83.70961639],
[ 42.27570361, -83.70961333],
[ 42.27572806, -83.70965167],
[ 42.2757625 , -83.70968056],
[ 42.27575861, -83.70967806],
[ 42.27577583, -83.70970444],
[ 42.27579194, -83.70970111],
[ 42.27577444, -83.7097 ],
[ 42.27574889, -83.70968944],
[ 42.27568194, -83.70960222],
[ 42.27565278, -83.70961583],
[ 42.27560167, -83.70957417],
[ 42.27554556, -83.70955861],
[ 42.27549583, -83.70952278],
[ 42.27543806, -83.70950056],
[ 42.27542083, -83.70949778],
[ 42.27541083, -83.7095025 ],
[ 42.27543528, -83.70953306],
[ 42.27543778, -83.70958667],
[ 42.27540528, -83.70969556],
[ 42.27537611, -83.70976333],
[ 42.27540389, -83.70973556],
[ 42.27540583, -83.70983694],
[ 42.27542306, -83.70984806],
[ 42.27540278, -83.70986861],
[ 42.27537944, -83.709825 ],
[ 42.27534917, -83.70990056],
[ 42.27537444, -83.7098625 ],
[ 42.27537028, -83.70984889],
[ 42.27538917, -83.70982111],
[ 42.27540167, -83.70979611],
[ 42.27542583, -83.709775 ],
[ 42.27545278, -83.70974 ],
[ 42.27548194, -83.70971194],
[ 42.27548389, -83.70964444],
[ 42.27550694, -83.70959694],
[ 42.27545083, -83.7095675 ],
[ 42.27538222, -83.70952944],
[ 42.27532833, -83.70948333],
[ 42.27526194, -83.70943972],
[ 42.27519222, -83.70937194],
[ 42.27514583, -83.70930028],
[ 42.27513333, -83.70918389],
[ 42.27511694, -83.70905028],
[ 42.27512222, -83.70891639],
[ 42.27511778, -83.70879583],
[ 42.27510972, -83.70864417],
[ 42.27511778, -83.70834028],
[ 42.27512778, -83.70811833],
[ 42.27513806, -83.70787194],
[ 42.27513056, -83.70763194],
[ 42.27512861, -83.70733028],
[ 42.27518722, -83.70722167],
[ 42.27517639, -83.70714222],
[ 42.27514222, -83.70718472],
[ 42.27518194, -83.707205 ],
[ 42.27519889, -83.70723056],
[ 42.27517 , -83.70722778],
[ 42.27517 , -83.70721778],
[ 42.27517361, -83.70710389],
[ 42.27523056, -83.70703194],
[ 42.27523333, -83.70698417],
[ 42.27523306, -83.706885 ],
[ 42.27522111, -83.70677833],
[ 42.27519778, -83.70666472],
[ 42.27516333, -83.70651 ],
[ 42.27519111, -83.70633611],
[ 42.27522889, -83.70622583],
[ 42.27530583, -83.70595806],
[ 42.27535056, -83.70574611],
[ 42.27532861, -83.70556333],
[ 42.27517083, -83.70539778],
[ 42.27506972, -83.70536167],
[ 42.27484444, -83.705305 ],
[ 42.27470556, -83.70526083],
[ 42.27446444, -83.70528389],
[ 42.27429361, -83.70538917],
[ 42.27413972, -83.70551028],
[ 42.2739825 , -83.70562639],
[ 42.27380639, -83.70569028],
[ 42.27358806, -83.70565861],
[ 42.27339417, -83.70563556],
[ 42.27321417, -83.70562056],
[ 42.27310028, -83.70557556],
[ 42.27305194, -83.70551083],
[ 42.27300278, -83.70524583],
[ 42.2731225 , -83.7047475 ],
[ 42.27326056, -83.70435944],
[ 42.27347472, -83.70401667],
[ 42.2737775 , -83.70377333],
[ 42.2740575 , -83.70346361],
[ 42.2743175 , -83.70316194],
[ 42.27452722, -83.7028325 ],
[ 42.27465278, -83.70227667],
[ 42.27460833, -83.70184528],
[ 42.27454194, -83.70139444],
[ 42.27447278, -83.70093833],
[ 42.27437833, -83.70046278],
[ 42.274225 , -83.69978694],
[ 42.27411361, -83.69926417],
[ 42.27400111, -83.69874944],
[ 42.27386667, -83.69824333],
[ 42.27365111, -83.69786667],
[ 42.27332 , -83.69768583],
[ 42.27309361, -83.69775278],
[ 42.27291556, -83.69788083],
[ 42.27282361, -83.69796278],
[ 42.27276 , -83.69805 ],
[ 42.27269667, -83.698075 ],
[ 42.27267056, -83.69810833],
[ 42.27270583, -83.69825722],
[ 42.27287667, -83.69833861],
[ 42.27310667, -83.69840833],
[ 42.2733975 , -83.698505 ],
[ 42.27376861, -83.69857 ],
[ 42.2741875 , -83.69860167],
[ 42.274615 , -83.69863778],
[ 42.27505278, -83.69865944],
[ 42.27563028, -83.69871 ],
[ 42.27619833, -83.69876167],
[ 42.27660611, -83.69876917],
[ 42.27699083, -83.69876 ],
[ 42.27726667, -83.69874528],
[ 42.27736167, -83.69874556],
[ 42.27742333, -83.69872694],
[ 42.27748417, -83.69847889],
[ 42.27745111, -83.69810972],
[ 42.27738778, -83.69766083],
[ 42.27731778, -83.69713833],
[ 42.27719667, -83.69637444],
[ 42.27709722, -83.69576861],
[ 42.2770175 , -83.69514778],
[ 42.27687028, -83.69428806],
[ 42.27677667, -83.69364444],
[ 42.27669861, -83.6929975 ],
[ 42.27665972, -83.69232833],
[ 42.27664167, -83.69166972],
[ 42.27663167, -83.69100417],
[ 42.27655694, -83.69021972],
[ 42.27650778, -83.68965667],
[ 42.27641861, -83.68910694],
[ 42.27632889, -83.68869889],
[ 42.276215 , -83.68823667],
[ 42.27611861, -83.68777667],
[ 42.27597472, -83.68726778],
[ 42.2758375 , -83.68673194],
[ 42.27567861, -83.68615889],
[ 42.27547472, -83.6854175 ],
[ 42.27532333, -83.68491111],
[ 42.27522333, -83.684485 ],
[ 42.2751225 , -83.68412444],
[ 42.27502611, -83.68370167],
[ 42.27495639, -83.68342083],
[ 42.27490278, -83.6832025 ],
[ 42.27488389, -83.68309528],
[ 42.27486167, -83.68304194],
[ 42.27484222, -83.68307861],
[ 42.27481194, -83.68301833],
[ 42.27479778, -83.68299278],
[ 42.27477778, -83.68293167],
[ 42.27475917, -83.682865 ],
[ 42.27474444, -83.68283528],
[ 42.27470306, -83.68274972],
[ 42.27467722, -83.68264139],
[ 42.27466861, -83.68260667],
[ 42.27465028, -83.68254194],
[ 42.27462806, -83.68246056],
[ 42.27455639, -83.68231111],
[ 42.27450194, -83.68200028],
[ 42.27451694, -83.68171917],
[ 42.27454472, -83.68133806],
[ 42.27452861, -83.68087194],
[ 42.27451278, -83.68020528],
[ 42.27449917, -83.67972722],
[ 42.27448389, -83.67930444],
[ 42.27445278, -83.67893528],
[ 42.27441444, -83.67861556],
[ 42.27432694, -83.67843583],
[ 42.27435111, -83.677985 ],
[ 42.27444944, -83.67753639],
[ 42.27446361, -83.67697667],
[ 42.27445583, -83.67639833],
[ 42.27444722, -83.67581417],
[ 42.27444222, -83.67525306],
[ 42.27442917, -83.67478083]])
q = np.array([[ 42.27757111, -83.69863194],
[ 42.27751444, -83.69895889],
[ 42.27713361, -83.69901167],
[ 42.27669778, -83.69890111],
[ 42.27616111, -83.69882278],
[ 42.27561306, -83.69877222],
[ 42.2749725 , -83.69873472],
[ 42.27452028, -83.69869556],
[ 42.27408167, -83.69866222],
[ 42.27367222, -83.69863944],
[ 42.27323889, -83.69853778],
[ 42.27307583, -83.69847583],
[ 42.2730175 , -83.69846444],
[ 42.27296667, -83.69843167],
[ 42.27292639, -83.69841944],
[ 42.27282694, -83.69835917],
[ 42.27277778, -83.69812278],
[ 42.272935 , -83.69784611],
[ 42.27319417, -83.69772389],
[ 42.27360111, -83.69789833],
[ 42.27377056, -83.69828194],
[ 42.27388917, -83.69876139],
[ 42.27405917, -83.69948139],
[ 42.27419111, -83.70004528],
[ 42.27432056, -83.70063944],
[ 42.27452333, -83.70153806],
[ 42.27464028, -83.70210694],
[ 42.27461278, -83.70256278],
[ 42.27444361, -83.70296944],
[ 42.27411944, -83.70332111],
[ 42.27393333, -83.70354444],
[ 42.27374278, -83.70377056],
[ 42.2734825 , -83.70411944],
[ 42.27332639, -83.704455 ],
[ 42.27323778, -83.70483167],
[ 42.27320694, -83.70518944],
[ 42.27315528, -83.70575083],
[ 42.27315278, -83.70623083],
[ 42.27313472, -83.70678361],
[ 42.27313389, -83.70732361],
[ 42.27311417, -83.70799861],
[ 42.27310806, -83.70845583],
[ 42.27311278, -83.70891944],
[ 42.273125 , -83.70955917],
[ 42.27309361, -83.709985 ],
[ 42.27309306, -83.71028944],
[ 42.27308222, -83.71067028],
[ 42.27307528, -83.7111575 ],
[ 42.27312222, -83.71189139],
[ 42.27316083, -83.71243333],
[ 42.27319111, -83.71290944],
[ 42.27329083, -83.71352333],
[ 42.27345861, -83.7139375 ],
[ 42.27365194, -83.71428694],
[ 42.27379583, -83.71465861],
[ 42.27393611, -83.71505667],
[ 42.2741 , -83.71565194],
[ 42.27423778, -83.71607444],
[ 42.27437556, -83.71650222],
[ 42.27443528, -83.7168475 ],
[ 42.27446417, -83.71703583],
[ 42.27451528, -83.71717 ],
[ 42.27452139, -83.71728917],
[ 42.27432833, -83.71737556],
[ 42.27392611, -83.71751556],
[ 42.27366417, -83.7176675 ],
[ 42.27346 , -83.71798861],
[ 42.27334583, -83.71839778],
[ 42.27341444, -83.71910528],
[ 42.27341806, -83.71956083],
[ 42.27338528, -83.71975778],
[ 42.273345 , -83.71998444],
[ 42.273395 , -83.72030444],
[ 42.27343667, -83.72076278],
[ 42.27350639, -83.72128861],
[ 42.27357861, -83.72185444],
[ 42.27368556, -83.72266694],
[ 42.27373667, -83.72325028],
[ 42.27378611, -83.72378 ],
[ 42.27383278, -83.72438444],
[ 42.27378722, -83.72482861],
[ 42.27363028, -83.72523528],
[ 42.27345528, -83.72562694],
[ 42.27315111, -83.72618694],
[ 42.27296444, -83.72664778],
[ 42.2728075 , -83.72705083],
[ 42.27268444, -83.72739778],
[ 42.27262694, -83.72759667],
[ 42.27262333, -83.72761 ],
[ 42.27258806, -83.72765333],
[ 42.27258639, -83.72766611],
[ 42.27253556, -83.7278625 ],
[ 42.27253 , -83.72825333],
[ 42.27250444, -83.72873833],
[ 42.27248444, -83.72929056],
[ 42.2724425 , -83.7300725 ],
[ 42.27236694, -83.73068361],
[ 42.27232694, -83.73129083],
[ 42.27229833, -83.73189528],
[ 42.27228278, -83.73250389],
[ 42.27229667, -83.7326825 ],
[ 42.27227917, -83.73272944],
[ 42.27227639, -83.73283667],
[ 42.27227806, -83.73295167],
[ 42.27235944, -83.73305806],
[ 42.27259361, -83.73309083],
[ 42.27302944, -83.73311722],
[ 42.27336472, -83.73313111],
[ 42.27368 , -83.73315639],
[ 42.27401361, -83.7331675 ],
[ 42.27421 , -83.73316694],
[ 42.27437667, -83.73321361],
[ 42.27447361, -83.73327583],
[ 42.2745075 , -83.73331583],
[ 42.27454833, -83.73328722],
[ 42.27458611, -83.73331528],
[ 42.27464167, -83.73330806],
[ 42.2746975 , -83.73324306],
[ 42.2747675 , -83.73333028],
[ 42.27480917, -83.73324639],
[ 42.27483722, -83.73311806],
[ 42.27482528, -83.732975 ],
[ 42.27481944, -83.73272083],
[ 42.27477833, -83.73247139],
[ 42.27473833, -83.73215333],
[ 42.27472417, -83.73191333],
[ 42.27471861, -83.73186 ],
[ 42.27470611, -83.73185083],
[ 42.27477694, -83.73178889],
[ 42.27484167, -83.73174028],
[ 42.27484667, -83.73163583],
[ 42.27480528, -83.73142528],
[ 42.27464861, -83.73111111],
[ 42.27449361, -83.73086333],
[ 42.27431167, -83.73059417],
[ 42.27409917, -83.73027861],
[ 42.27385083, -83.72994639],
[ 42.27346667, -83.72944194],
[ 42.27316361, -83.72909417],
[ 42.27293444, -83.72880361],
[ 42.2727825 , -83.72866889],
[ 42.27257333, -83.72874139],
[ 42.27249333, -83.72884583],
[ 42.27243583, -83.72910333],
[ 42.27239833, -83.72949306],
[ 42.27237806, -83.72988889],
[ 42.27234556, -83.73036056],
[ 42.27230778, -83.73070083],
[ 42.27229222, -83.73105417],
[ 42.27228361, -83.73142028],
[ 42.27227889, -83.73174917],
[ 42.27227861, -83.73208694],
[ 42.2722775 , -83.73235444],
[ 42.27227833, -83.73255583],
[ 42.27227167, -83.73261583],
[ 42.27225667, -83.73270667],
[ 42.27223944, -83.73279278],
[ 42.27230639, -83.73290917],
[ 42.27256222, -83.73296917],
[ 42.27286222, -83.73298444],
[ 42.27314278, -83.732985 ],
[ 42.27336972, -83.73300528],
[ 42.27360722, -83.73300472],
[ 42.27375806, -83.73301 ],
[ 42.27389667, -83.73302583],
[ 42.27397806, -83.73302861],
[ 42.27402889, -83.73304028],
[ 42.27404278, -83.73302389],
[ 42.27413472, -83.73301222],
[ 42.2741525 , -83.73302417],
[ 42.27419611, -83.73305389],
[ 42.27426 , -83.73298528],
[ 42.27429944, -83.73293361],
[ 42.27419722, -83.73297583],
[ 42.274225 , -83.73297111],
[ 42.2742375 , -83.73300861],
[ 42.27428472, -83.73287833],
[ 42.27428833, -83.73286361],
[ 42.27428889, -83.73286417],
[ 42.27431861, -83.73288 ],
[ 42.27434028, -83.73289639],
[ 42.27440611, -83.73294833],
[ 42.27448361, -83.73295778],
[ 42.27454083, -83.73293944],
[ 42.27486 , -83.73271889],
[ 42.27490361, -83.73268167],
[ 42.27482611, -83.73274333],
[ 42.27483917, -83.73271583],
[ 42.27479028, -83.73271306],
[ 42.27478028, -83.73271556],
[ 42.274825 , -83.73277639],
[ 42.27489667, -83.73287833],
[ 42.27497861, -83.73299639],
[ 42.27495944, -83.73305944],
[ 42.27478917, -83.73309111],
[ 42.27483556, -83.73315556],
[ 42.27492556, -83.73317306],
[ 42.27512167, -83.73317194],
[ 42.27537278, -83.73303583],
[ 42.27553167, -83.73291139],
[ 42.27560611, -83.73284472],
[ 42.27562194, -83.73283944],
[ 42.27571944, -83.732725 ],
[ 42.27576194, -83.73266278],
[ 42.27590222, -83.73238444],
[ 42.276035 , -83.73200528],
[ 42.27619167, -83.73162556],
[ 42.27641278, -83.73135278],
[ 42.27668556, -83.73115667],
[ 42.27696861, -83.73105 ],
[ 42.27704694, -83.73102861],
[ 42.27711944, -83.73097333],
[ 42.2771 , -83.73080167],
[ 42.27700417, -83.73049444],
[ 42.27690389, -83.73007722],
[ 42.2767675 , -83.72951722],
[ 42.27665639, -83.72909444],
[ 42.27654389, -83.72868556],
[ 42.27643778, -83.72829806],
[ 42.27627694, -83.72772778],
[ 42.27615389, -83.72729028],
[ 42.27604056, -83.72687306],
[ 42.27588722, -83.72632972],
[ 42.27580833, -83.72591861],
[ 42.27576583, -83.725525 ],
[ 42.27571417, -83.72510333],
[ 42.27566917, -83.72464028],
[ 42.27558972, -83.72403694],
[ 42.27552028, -83.72359222],
[ 42.27544583, -83.72317528],
[ 42.27539556, -83.72275694],
[ 42.27534417, -83.72236167],
[ 42.27528528, -83.72183278],
[ 42.27521778, -83.72143333],
[ 42.27515972, -83.72101667],
[ 42.2750925 , -83.72057361],
[ 42.27499944, -83.72010556],
[ 42.27485333, -83.71949611],
[ 42.27477111, -83.71898639],
[ 42.27462861, -83.71853583],
[ 42.2744825 , -83.71806944],
[ 42.27437667, -83.71755778],
[ 42.27425083, -83.71707333],
[ 42.27408139, -83.716445 ],
[ 42.27395167, -83.71598833],
[ 42.27380889, -83.715485 ],
[ 42.27363667, -83.71501056],
[ 42.27340333, -83.71441417],
[ 42.27325 , -83.71395333],
[ 42.27314556, -83.71350694],
[ 42.27305222, -83.71290472],
[ 42.27297861, -83.71245806],
[ 42.2729225 , -83.712 ],
[ 42.27291556, -83.71154722],
[ 42.27291333, -83.71100111],
[ 42.27290917, -83.71063361],
[ 42.27292417, -83.71026583],
[ 42.27293611, -83.70987389],
[ 42.27296167, -83.70945028],
[ 42.27297917, -83.70885167],
[ 42.27298111, -83.70840361],
[ 42.2729875 , -83.70795083],
[ 42.27299806, -83.70749083],
[ 42.27300667, -83.70686417],
[ 42.27301944, -83.70639056],
[ 42.27303917, -83.70589167],
[ 42.27307278, -83.70540389],
[ 42.27313417, -83.70493611],
[ 42.27333056, -83.70437972],
[ 42.2735925 , -83.70402028],
[ 42.27386778, -83.70371028],
[ 42.27414167, -83.703415 ],
[ 42.27441889, -83.703105 ],
[ 42.27449361, -83.70298861],
[ 42.27454333, -83.7029 ],
[ 42.27460333, -83.70272 ],
[ 42.27462111, -83.70246611],
[ 42.27451361, -83.70192333],
[ 42.27438306, -83.7014 ],
[ 42.27425417, -83.70087 ],
[ 42.27413222, -83.70032778],
[ 42.27395694, -83.69959528],
[ 42.27382528, -83.69902167],
[ 42.27368778, -83.69847528],
[ 42.27352444, -83.69810611],
[ 42.27332806, -83.69783833],
[ 42.27313333, -83.69774 ],
[ 42.27308417, -83.69771917],
[ 42.27310111, -83.69763528],
[ 42.27300667, -83.69769167],
[ 42.27282472, -83.69791528],
[ 42.27272972, -83.69811889],
[ 42.27258778, -83.69823139],
[ 42.27238694, -83.69816722],
[ 42.27204944, -83.69793778],
[ 42.27147056, -83.69752528],
[ 42.27101917, -83.69729833],
[ 42.27055944, -83.69724139],
[ 42.27009278, -83.69741333],
[ 42.26963972, -83.69765722],
[ 42.26904556, -83.69791083],
[ 42.2685775 , -83.69796778],
[ 42.26810806, -83.69791833],
[ 42.26765889, -83.69776028],
[ 42.26704861, -83.69735944],
[ 42.26661361, -83.69685722],
[ 42.26623278, -83.69629583],
[ 42.26586361, -83.69575167],
[ 42.2653875 , -83.69503083],
[ 42.26502528, -83.69446833],
[ 42.26463111, -83.69385528],
[ 42.2641825 , -83.69328778],
[ 42.26347083, -83.69277917],
[ 42.26290944, -83.69263806],
[ 42.26240056, -83.69269139],
[ 42.26195667, -83.69287278],
[ 42.26153583, -83.69312444],
[ 42.26104944, -83.69357972],
[ 42.2606725 , -83.6939825 ],
[ 42.26030111, -83.69438667],
[ 42.25991861, -83.69481833],
[ 42.25941778, -83.69516361],
[ 42.2590175 , -83.69532611],
[ 42.25865111, -83.69540667],
[ 42.25835028, -83.69544639],
[ 42.25818667, -83.69546111],
[ 42.25812139, -83.6954825 ],
[ 42.25805861, -83.69546861],
[ 42.25810389, -83.69547528],
[ 42.25811861, -83.69548167],
[ 42.25809528, -83.695485 ],
[ 42.25796083, -83.69550611],
[ 42.25765333, -83.69554389],
[ 42.25726833, -83.69559444],
[ 42.25700833, -83.69561889],
[ 42.25691972, -83.69563028],
[ 42.25688333, -83.69557778],
[ 42.25688444, -83.69562694],
[ 42.25700528, -83.69569861],
[ 42.25696583, -83.69569806],
[ 42.25691833, -83.69569167],
[ 42.25678361, -83.69567194],
[ 42.25662278, -83.69531639],
[ 42.25649944, -83.69489417],
[ 42.25636194, -83.69429722],
[ 42.25622111, -83.69362861],
[ 42.25605583, -83.69295167],
[ 42.25598083, -83.6926175 ],
[ 42.25591833, -83.69237333],
[ 42.25588611, -83.69220889],
[ 42.25586972, -83.69214028],
[ 42.25597194, -83.69209833],
[ 42.25597194, -83.69208778],
[ 42.255955 , -83.69194639],
[ 42.25592611, -83.69169444],
[ 42.25588194, -83.69142278],
[ 42.25583528, -83.69111306],
[ 42.2558075 , -83.69080139],
[ 42.255745 , -83.69029194],
[ 42.25569278, -83.68984861],
[ 42.25563361, -83.68939222],
[ 42.25556917, -83.68893194],
[ 42.25548 , -83.68845444],
[ 42.25545583, -83.68825611],
[ 42.25544444, -83.68820111],
[ 42.25542583, -83.68818361],
[ 42.25542611, -83.68814417],
[ 42.25539139, -83.6879725 ],
[ 42.2554775 , -83.68771639],
[ 42.25563667, -83.68762722],
[ 42.25583222, -83.68754583],
[ 42.25604194, -83.68750583],
[ 42.25626889, -83.68746361],
[ 42.25639278, -83.68744611],
[ 42.25650306, -83.68743556],
[ 42.25670667, -83.68739944],
[ 42.25693167, -83.68735694],
[ 42.25718417, -83.68733361],
[ 42.25743583, -83.68734083],
[ 42.25767611, -83.68734694],
[ 42.25787389, -83.68735833],
[ 42.25796861, -83.68737778],
[ 42.25799361, -83.68749 ],
[ 42.25799639, -83.68763528],
[ 42.25801917, -83.68786639],
[ 42.25796417, -83.687935 ],
[ 42.2579 , -83.68788139],
[ 42.25791167, -83.68782306],
[ 42.25790806, -83.68782556],
[ 42.25786778, -83.68782917],
[ 42.25783167, -83.68785667],
[ 42.25782083, -83.6878575 ],
[ 42.25781583, -83.68788833],
[ 42.2578275 , -83.6878625 ],
[ 42.25781778, -83.687875 ],
[ 42.25782583, -83.68785778],
[ 42.25781583, -83.68788389],
[ 42.25782778, -83.68785833],
[ 42.25779139, -83.68780444],
[ 42.25766083, -83.68779278],
[ 42.25745306, -83.68779639],
[ 42.25720111, -83.687785 ],
[ 42.25710167, -83.68781417],
[ 42.25706667, -83.68795333],
[ 42.25708389, -83.68821417],
[ 42.25707972, -83.68852861],
[ 42.25707611, -83.68894194],
[ 42.25707111, -83.68913528],
[ 42.25707833, -83.68915333],
[ 42.25706667, -83.68917889],
[ 42.25691 , -83.68922583],
[ 42.25671583, -83.68922861],
[ 42.25659639, -83.68921083],
[ 42.25651833, -83.68921528],
[ 42.25644444, -83.68929306],
[ 42.25644444, -83.68967139],
[ 42.25644611, -83.68994639],
[ 42.25642694, -83.69011944],
[ 42.25627444, -83.69024361],
[ 42.25606417, -83.6903125 ],
[ 42.25602583, -83.69033278],
[ 42.25600444, -83.69033833],
[ 42.25593278, -83.69031333],
[ 42.25597 , -83.69041361],
[ 42.25599667, -83.690485 ],
[ 42.25598056, -83.69046583],
[ 42.25595083, -83.69047778],
[ 42.25582167, -83.69047778],
[ 42.25571083, -83.69031944],
[ 42.25566028, -83.69000333],
[ 42.25559083, -83.68954444],
[ 42.25550528, -83.68898167],
[ 42.25537333, -83.68818583],
[ 42.25526306, -83.68756333],
[ 42.25513278, -83.68689 ],
[ 42.25499639, -83.68617194],
[ 42.25486028, -83.68545611],
[ 42.2546875 , -83.68455944],
[ 42.25455861, -83.68392083],
[ 42.25444861, -83.68335722],
[ 42.25430944, -83.68275639],
[ 42.25420722, -83.68235361],
[ 42.25400722, -83.6820675 ],
[ 42.25370361, -83.68194417],
[ 42.25339833, -83.68210222],
[ 42.25319861, -83.68266417],
[ 42.25331833, -83.68312611],
[ 42.25362222, -83.68343722],
[ 42.25408333, -83.68352667],
[ 42.25483167, -83.68360611],
[ 42.25548 , -83.68365 ],
[ 42.25619 , -83.68368472],
[ 42.25694389, -83.68371917],
[ 42.25798194, -83.68375694],
[ 42.25878417, -83.68368833],
[ 42.25960472, -83.6834325 ],
[ 42.26038583, -83.68302778],
[ 42.26135444, -83.68219833],
[ 42.26200194, -83.68140333],
[ 42.26262889, -83.680565 ],
[ 42.26325028, -83.67973 ],
[ 42.26406667, -83.67863056],
[ 42.26466833, -83.67782167],
[ 42.26531111, -83.67710083],
[ 42.26628861, -83.67637389],
[ 42.26709194, -83.67602944],
[ 42.26792528, -83.67584528],
[ 42.26877361, -83.67579278],
[ 42.26989 , -83.67578278],
[ 42.27066944, -83.67577583],
[ 42.27140111, -83.67572806],
[ 42.27208972, -83.67563056],
[ 42.27287028, -83.67524833],
[ 42.27337917, -83.67487028],
[ 42.27378528, -83.67458194],
[ 42.27404944, -83.67439056],
[ 42.27417028, -83.67427111]])
后记
我看了别人还有其他的优化方法，但感觉有点难理解，我整明白再来更新，利用啥稀疏矩阵和其他的东西配合，似乎速度还能提高几倍
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）