Coverage for pygeodesy/frechet.py: 96%

215 statements  

« prev     ^ index     » next       coverage.py v7.6.0, created at 2024-08-02 18:24 -0400

1 

2# -*- coding: utf-8 -*- 

3 

4u'''Fréchet distances. 

5 

6Classes L{Frechet}, L{FrechetDegrees}, L{FrechetRadians}, 

7L{FrechetCosineAndoyerLambert}, L{FrechetCosineForsytheAndoyerLambert}, 

8L{FrechetCosineLaw}, L{FrechetDistanceTo}< L{FrechetEquirectangular}, 

9L{FrechetEuclidean}, L{FrechetExact}, L{FrechetFlatLocal}, L{FrechetFlatPolar}, 

10L{FrechetHaversine}, L{FrechetHubeny}, L{FrechetKarney}, L{FrechetThomas} 

11and L{FrechetVincentys} to compute I{discrete} U{Fréchet 

12<https://WikiPedia.org/wiki/Frechet_distance>} distances between two sets 

13of C{LatLon}, C{NumPy}, C{tuples} or other types of points. 

14 

15Only L{FrechetDistanceTo} -iff used with L{ellipsoidalKarney.LatLon} 

16points- and L{FrechetKarney} requires installation of I{Charles Karney}'s 

17U{geographiclib<https://PyPI.org/project/geographiclib>}. 

18 

19Typical usage is as follows. First, create a C{Frechet} calculator 

20from one set of C{LatLon} points. 

21 

22C{f = FrechetXyz(point1s, ...)} 

23 

24Get the I{discrete} Fréchet distance to another set of C{LatLon} points 

25by 

26 

27C{t6 = f.discrete(point2s)} 

28 

29Or, use function C{frechet_} with a proper C{distance} function passed 

30as keyword arguments as follows 

31 

32C{t6 = frechet_(point1s, point2s, ..., distance=...)}. 

33 

34In both cases, the returned result C{t6} is a L{Frechet6Tuple}. 

35 

36For C{(lat, lon, ...)} points in a C{NumPy} array or plain C{tuples}, 

37wrap the points in a L{Numpy2LatLon} respectively L{Tuple2LatLon} 

38instance, more details in the documentation thereof. 

39 

40For other points, create a L{Frechet} sub-class with the appropriate 

41C{distance} method overloading L{Frechet.distance} as in this example. 

42 

43 >>> from pygeodesy import Frechet, hypot_ 

44 >>> 

45 >>> class F3D(Frechet): 

46 >>> """Custom Frechet example. 

47 >>> """ 

48 >>> def distance(self, p1, p2): 

49 >>> return hypot_(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z) 

50 >>> 

51 >>> f3D = F3D(xyz1, ..., units="...") 

52 >>> t6 = f3D.discrete(xyz2) 

53 

54Transcribed from the original U{Computing Discrete Fréchet Distance 

55<https://www.kr.TUWien.ac.AT/staff/eiter/et-archive/cdtr9464.pdf>} by 

56Eiter, T. and Mannila, H., 1994, April 25, Technical Report CD-TR 94/64, 

57Information Systems Department/Christian Doppler Laboratory for Expert 

58Systems, Technical University Vienna, Austria. 

59 

60This L{Frechet.discrete} implementation optionally generates intermediate 

61points for each point set separately. For example, using keyword argument 

62C{fraction=0.5} adds one additional point halfway between each pair of 

63points. Or using C{fraction=0.1} interpolates nine additional points 

64between each points pair. 

65 

66The L{Frechet6Tuple} attributes C{fi1} and/or C{fi2} will be I{fractional} 

67indices of type C{float} if keyword argument C{fraction} is used. Otherwise, 

68C{fi1} and/or C{fi2} are simply type C{int} indices into the respective 

69points set. 

70 

71For example, C{fractional} index value 2.5 means an intermediate point 

72halfway between points[2] and points[3]. Use function L{fractional} 

73to obtain the intermediate point for a I{fractional} index in the 

74corresponding set of points. 

75 

76The C{Fréchet} distance was introduced in 1906 by U{Maurice Fréchet 

77<https://WikiPedia.org/wiki/Maurice_Rene_Frechet>}, see U{reference 

78[6]<https://www.kr.TUWien.ac.AT/staff/eiter/et-archive/cdtr9464.pdf>}. 

79It is a measure of similarity between curves that takes into account the 

80location and ordering of the points. Therefore, it is often a better metric 

81than the well-known C{Hausdorff} distance, see the L{hausdorff} module. 

82''' 

83 

84# from pygeodesy.basics import isscalar # from .points 

85from pygeodesy.constants import EPS, EPS1, INF, NINF 

86from pygeodesy.datums import _ellipsoidal_datum, _WGS84 

87from pygeodesy.errors import PointsError, _xattr, _xcallable, _xkwds, _xkwds_get 

88import pygeodesy.formy as _formy 

89from pygeodesy.interns import NN, _DOT_, _n_, _units_ 

90# from pygeodesy.iters import points2 as _points2 # from .points 

91from pygeodesy.lazily import _ALL_LAZY, _FOR_DOCS 

92from pygeodesy.named import _name2__, _Named, _NamedTuple, _Pass 

93# from pygeodesy.namedTuples import PhiLam2Tuple # from .points 

94from pygeodesy.points import _distanceTo, _fractional, isscalar, PhiLam2Tuple, \ 

95 points2 as _points2, radians 

96from pygeodesy.props import Property, property_doc_, property_RO 

97from pygeodesy.units import FIx, Float, Number_ 

98from pygeodesy import unitsBase as _unitsBase # _Str_..., _xUnit, _xUnits 

99 

100from collections import defaultdict as _defaultdict 

101# from math import radians # from .points 

102 

103__all__ = _ALL_LAZY.frechet 

104__version__ = '24.06.15' 

105 

106 

107def _fraction(fraction, n): 

108 f = 1 # int, no fractional indices 

109 if fraction in (None, 1): 

110 pass 

111 elif not (isscalar(fraction) and EPS < fraction < EPS1 

112 and (float(n) - fraction) < n): 

113 raise FrechetError(fraction=fraction) 

114 elif fraction < EPS1: 

115 f = float(fraction) 

116 return f 

117 

118 

119class FrechetError(PointsError): 

120 '''Fréchet issue. 

121 ''' 

122 pass 

123 

124 

125class Frechet(_Named): 

126 '''Frechet base class, requires method L{Frechet.distance} to 

127 be overloaded. 

128 ''' 

129 _datum = _WGS84 

130 _func = None # formy function/property 

131 _f1 = 1 

132 _kwds = {} # func_ options 

133 _n1 = 0 

134 _ps1 = None 

135 _units = _unitsBase._Str_NN # XXX Str to _Pass and for backward compatibility 

136 

137 def __init__(self, point1s, fraction=None, units=NN, **name__kwds): 

138 '''New C{Frechet...} calculator/interpolator. 

139 

140 @arg point1s: First set of points (C{LatLon}[], L{Numpy2LatLon}[], 

141 L{Tuple2LatLon}[] or C{other}[]). 

142 @kwarg fraction: Index fraction (C{float} in L{EPS}..L{EPS1}) to 

143 interpolate intermediate B{C{point1s}} or use C{None}, 

144 C{0} or C{1} for no intermediate B{C{point1s}} and no 

145 I{fractional} indices. 

146 @kwarg units: Optional distance units (C{Unit} or C{str}). 

147 @kwarg name__kwds: Optional C{B{name}=NN} for this calculator/interpolator 

148 (C{str}) and any keyword arguments for the distance function, 

149 retrievable with property C{kwds}. 

150 

151 @raise FrechetError: Insufficient number of B{C{point1s}} or an invalid 

152 B{C{point1}}, B{C{fraction}} or B{C{units}}. 

153 ''' 

154 name, kwds = _name2__(**name__kwds) # name__=self.__class__ 

155 if name: 

156 self.name = name 

157 

158 self._n1, self._ps1 = self._points2(point1s) 

159 if fraction: 

160 self.fraction = fraction 

161 if units: # and not self.units: 

162 self.units = units 

163 if kwds: 

164 self._kwds = kwds 

165 

166 @property_RO 

167 def adjust(self): 

168 '''Get the C{adjust} setting (C{bool} or C{None}). 

169 ''' 

170 return _xkwds_get(self._kwds, adjust=None) 

171 

172 @property_RO 

173 def datum(self): 

174 '''Get the datum (L{Datum} or C{None} if not applicable). 

175 ''' 

176 return self._datum 

177 

178 def _datum_setter(self, datum): 

179 '''(INTERNAL) Set the datum. 

180 ''' 

181 d = datum or _xattr(self._ps1[0], datum=None) 

182 if d and d is not self._datum: # PYCHOK no cover 

183 self._datum = _ellipsoidal_datum(d, name=self.name) 

184 

185 def discrete(self, point2s, fraction=None): 

186 '''Compute the C{forward, discrete Fréchet} distance. 

187 

188 @arg point2s: Second set of points (C{LatLon}[], L{Numpy2LatLon}[], 

189 L{Tuple2LatLon}[] or C{other}[]). 

190 @kwarg fraction: Index fraction (C{float} in L{EPS}..L{EPS1}) to 

191 interpolate intermediate B{C{point2s}} or use 

192 C{None}, C{0} or C{1} for no intermediate 

193 B{C{point2s}} and no I{fractional} indices. 

194 

195 @return: A L{Frechet6Tuple}C{(fd, fi1, fi2, r, n, units)}. 

196 

197 @raise FrechetError: Insufficient number of B{C{point2s}} or 

198 an invalid B{C{point2}} or B{C{fraction}}. 

199 

200 @raise RecursionError: Recursion depth exceeded, see U{sys.getrecursionlimit 

201 <https://docs.Python.org/3/library/sys.html#sys.getrecursionlimit>}. 

202 ''' 

203 return self._discrete(point2s, fraction, self.distance) 

204 

205 def _discrete(self, point2s, fraction, distance): 

206 '''(INTERNAL) Detailed C{discrete} with C{disance}. 

207 ''' 

208 n2, ps2 = self._points2(point2s) 

209 

210 f2 = _fraction(fraction, n2) 

211 p2 = self.points_fraction if f2 < EPS1 else self.points_ # PYCHOK expected 

212 

213 f1 = self.fraction 

214 p1 = self.points_fraction if f1 < EPS1 else self.points_ # PYCHOK expected 

215 

216 def _dF(fi1, fi2): 

217 return distance(p1(self._ps1, fi1), p2(ps2, fi2)) 

218 

219 try: 

220 return _frechet_(self._n1, f1, n2, f2, _dF, self.units) 

221 except TypeError as x: 

222 t = _DOT_(self.classname, self.discrete.__name__) 

223 raise FrechetError(t, cause=x) 

224 

225 def distance(self, point1, point2): 

226 '''Return the distance between B{C{point1}} and B{C{point2s}}, 

227 subject to the supplied optional keyword arguments, see 

228 property C{kwds}. 

229 ''' 

230 return self._func(point1.lat, point1.lon, 

231 point2.lat, point2.lon, **self._kwds) 

232 

233 @property_doc_(''' the index fraction (C{float}).''') 

234 def fraction(self): 

235 '''Get the index fraction (C{float} or C{1}). 

236 ''' 

237 return self._f1 

238 

239 @fraction.setter # PYCHOK setter! 

240 def fraction(self, fraction): 

241 '''Set the index fraction (C{float} in C{EPS}..L{EPS1}) to interpolate 

242 intermediate B{C{point1s}} or use C{None}, C{0} or C{1} for no 

243 intermediate B{C{point1s}} and no I{fractional} indices. 

244 

245 @raise FrechetError: Invalid B{C{fraction}}. 

246 ''' 

247 self._f1 = _fraction(fraction, self._n1) 

248 

249# def _func(self, *args, **kwds): # PYCHOK no cover 

250# '''(INTERNAL) I{Must be overloaded}.''' 

251# self._notOverloaded(*args, **kwds) 

252 

253 @Property 

254 def _func(self): 

255 '''(INTERNAL) I{Must be overloaded}.''' 

256 self._notOverloaded(**self.kwds) 

257 

258 @_func.setter_ # PYCHOK setter_underscore! 

259 def _func(self, func): 

260 return _formy._Propy(func, 4, self.kwds) 

261 

262 @property_RO 

263 def kwds(self): 

264 '''Get the supplied, optional keyword arguments (C{dict}). 

265 ''' 

266 return self._kwds 

267 

268 def point(self, point): 

269 '''Convert a point for the C{.distance} method. 

270 

271 @arg point: The point to convert ((C{LatLon}, L{Numpy2LatLon}, 

272 L{Tuple2LatLon} or C{other}). 

273 

274 @return: The converted B{C{point}}. 

275 ''' 

276 return point # pass thru 

277 

278 def points_(self, points, i): 

279 '''Get and convert a point for the C{.distance} method. 

280 

281 @arg points: The orignal B{C{points}} to convert ((C{LatLon}[], 

282 L{Numpy2LatLon}[], L{Tuple2LatLon}[] or C{other}[]). 

283 @arg i: The B{C{points}} index (C{int}). 

284 

285 @return: The converted B{C{points[i]}}. 

286 ''' 

287 return self.point(points[i]) 

288 

289 def points_fraction(self, points, fi): 

290 '''Get and convert a I{fractional} point for the C{.distance} method. 

291 

292 @arg points: The orignal B{C{points}} to convert ((C{LatLon}[], 

293 L{Numpy2LatLon}[], L{Tuple2LatLon}[] or C{other}[]). 

294 @arg fi: The I{fractional} index in B{C{points}} (C{float} or C{int}). 

295 

296 @return: The interpolated, converted, intermediate B{C{points[fi]}}. 

297 ''' 

298 return self.point(_fractional(points, fi, None, wrap=None)) # was=self.wrap 

299 

300 def _points2(self, points): 

301 '''(INTERNAL) Check a set of points, overloaded in L{FrechetDistanceTo}. 

302 ''' 

303 return _points2(points, closed=False, Error=FrechetError) 

304 

305 @property_doc_(''' the distance units (C{Unit} or C{str}).''') 

306 def units(self): 

307 '''Get the distance units (C{Unit} or C{str}). 

308 ''' 

309 return self._units 

310 

311 @units.setter # PYCHOK setter! 

312 def units(self, units): 

313 '''Set the distance units (C{Unit} or C{str}). 

314 

315 @raise TypeError: Invalid B{C{units}}. 

316 ''' 

317 self._units = _unitsBase._xUnits(units, Base=Float) 

318 

319 @property_RO 

320 def wrap(self): 

321 '''Get the C{wrap} setting (C{bool} or C{None}). 

322 ''' 

323 return _xkwds_get(self._kwds, wrap=None) 

324 

325 

326class FrechetDegrees(Frechet): 

327 '''DEPRECATED, use an other C{Frechet*} class. 

328 ''' 

329 _units = _unitsBase._Str_degrees 

330 

331 if _FOR_DOCS: 

332 __init__ = Frechet.__init__ 

333 discrete = Frechet.discrete 

334 

335 def distance(self, point1, point2, *args, **kwds): # PYCHOK no cover 

336 '''I{Must be overloaded}.''' 

337 self._notOverloaded(point1, point2, *args, **kwds) 

338 

339 

340class FrechetRadians(Frechet): 

341 '''DEPRECATED, use an other C{Frechet*} class. 

342 ''' 

343 _units = _unitsBase._Str_radians 

344 

345 if _FOR_DOCS: 

346 __init__ = Frechet.__init__ 

347 discrete = Frechet.discrete 

348 

349 def distance(self, point1, point2, *args, **kwds): # PYCHOK no cover 

350 '''I{Must be overloaded}.''' 

351 self._notOverloaded(point1, point2, *args, **kwds) 

352 

353 def point(self, point): 

354 '''Return B{C{point}} as L{PhiLam2Tuple} to maintain 

355 I{backward compatibility} of L{FrechetRadians}. 

356 

357 @return: A L{PhiLam2Tuple}C{(phi, lam)}. 

358 ''' 

359 try: 

360 return point.philam 

361 except AttributeError: 

362 return PhiLam2Tuple(radians(point.lat), radians(point.lon)) 

363 

364 

365class _FrechetMeterRadians(Frechet): 

366 '''(INTERNAL) Returning C{meter} or C{radians} depending on 

367 the optional keyword arguments supplied at instantiation 

368 of the C{Frechet*} sub-class. 

369 ''' 

370 _units = _unitsBase._Str_meter 

371 _units_ = _unitsBase._Str_radians 

372 

373 def discrete(self, point2s, fraction=None): 

374 '''Overloaded method L{Frechet.discrete} to determine 

375 the distance function and units from the optional 

376 keyword arguments given at this instantiation, see 

377 property C{kwds}. 

378 

379 @see: L{Frechet.discrete} for other details. 

380 ''' 

381 return self._discrete(point2s, fraction, _formy._radistance(self)) 

382 

383 @Property 

384 def _func_(self): 

385 '''(INTERNAL) I{Must be overloaded}.''' 

386 self._notOverloaded(**self.kwds) 

387 

388 @_func_.setter_ # PYCHOK setter_underscore! 

389 def _func_(self, func): 

390 return _formy._Propy(func, 3, self.kwds) 

391 

392 

393class FrechetCosineAndoyerLambert(_FrechetMeterRadians): 

394 '''Compute the C{Frechet} distance based on the I{angular} distance 

395 in C{radians} from function L{pygeodesy.cosineAndoyerLambert}. 

396 ''' 

397 def __init__(self, point1s, **fraction_name__datum_wrap): 

398 '''New L{FrechetCosineAndoyerLambert} calculator/interpolator. 

399 

400 @kwarg fraction_name__datum_wrap: Optional C{B{fraction}=None} 

401 and C{B{name}=NN} and keyword arguments for 

402 function L{pygeodesy.cosineAndoyerLambert}. 

403 

404 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

405 B{C{fraction}}, B{C{name}} and other exceptions. 

406 ''' 

407 Frechet.__init__(self, point1s, **fraction_name__datum_wrap) 

408 self._func = _formy.cosineAndoyerLambert 

409 self._func_ = _formy.cosineAndoyerLambert_ 

410 

411 if _FOR_DOCS: 

412 discrete = Frechet.discrete 

413 

414 

415class FrechetCosineForsytheAndoyerLambert(_FrechetMeterRadians): 

416 '''Compute the C{Frechet} distance based on the I{angular} distance 

417 in C{radians} from function L{pygeodesy.cosineForsytheAndoyerLambert}. 

418 ''' 

419 def __init__(self, point1s, **fraction_name__datum_wrap): 

420 '''New L{FrechetCosineForsytheAndoyerLambert} calculator/interpolator. 

421 

422 @kwarg fraction_name__datum_wrap: Optional C{B{fraction}=None} and 

423 C{B{name}=NN} and keyword arguments for function 

424 L{pygeodesy.cosineForsytheAndoyerLambert}. 

425 

426 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

427 B{C{fraction}}, B{C{name}} and other exceptions. 

428 ''' 

429 Frechet.__init__(self, point1s, **fraction_name__datum_wrap) 

430 self._func = _formy.cosineForsytheAndoyerLambert 

431 self._func_ = _formy.cosineForsytheAndoyerLambert_ 

432 

433 if _FOR_DOCS: 

434 discrete = Frechet.discrete 

435 

436 

437class FrechetCosineLaw(_FrechetMeterRadians): 

438 '''Compute the C{Frechet} distance based on the I{angular} distance 

439 in C{radians} from function L{pygeodesy.cosineLaw}. 

440 

441 @note: See note at function L{pygeodesy.vincentys_}. 

442 ''' 

443 def __init__(self, point1s, **fraction_name__radius_wrap): 

444 '''New L{FrechetCosineLaw} calculator/interpolator. 

445 

446 @kwarg fraction_name__radius_wrap: Optional C{B{fraction}=None} 

447 and C{B{name}=NN} and keyword arguments 

448 for function L{pygeodesy.cosineLaw}. 

449 

450 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

451 B{C{fraction}}, B{C{name}} and other exceptions. 

452 ''' 

453 Frechet.__init__(self, point1s, **fraction_name__radius_wrap) 

454 self._func = _formy.cosineLaw 

455 self._func_ = _formy.cosineLaw_ 

456 

457 if _FOR_DOCS: 

458 discrete = Frechet.discrete 

459 

460 

461class FrechetDistanceTo(Frechet): # FrechetMeter 

462 '''Compute the C{Frechet} distance based on the distance from the 

463 point1s' C{LatLon.distanceTo} method, conventionally in C{meter}. 

464 ''' 

465 _units = _unitsBase._Str_meter 

466 

467 def __init__(self, point1s, **fraction_name__distanceTo_kwds): 

468 '''New L{FrechetDistanceTo} calculator/interpolator. 

469 

470 @kwarg fraction_name__distanceTo_kwds: Optional C{B{fraction}=None} 

471 and C{B{name}=NN} and keyword arguments for 

472 each B{C{point1s}}' C{LatLon.distanceTo} method. 

473 

474 @see: L{Frechet.__init__} for details about B{C{point1s}}, B{C{fraction}}, 

475 B{C{name}} and other exceptions. 

476 

477 @note: All B{C{point1s}} I{must} be instances of the same ellipsoidal 

478 or spherical C{LatLon} class. 

479 ''' 

480 Frechet.__init__(self, point1s, **fraction_name__distanceTo_kwds) 

481 

482 if _FOR_DOCS: 

483 discrete = Frechet.discrete 

484 

485 def distance(self, p1, p2): 

486 '''Return the distance in C{meter}. 

487 ''' 

488 return p1.distanceTo(p2, **self._kwds) 

489 

490 def _points2(self, points): 

491 '''(INTERNAL) Check a set of points. 

492 ''' 

493 np, ps = Frechet._points2(self, points) 

494 return np, _distanceTo(FrechetError, points=ps) 

495 

496 

497class FrechetEquirectangular(Frechet): 

498 '''Compute the C{Frechet} distance based on the I{equirectangular} 

499 distance in C{radians squared} like function L{pygeodesy.equirectangular}. 

500 ''' 

501 _units = _unitsBase._Str_radians2 

502 

503 def __init__(self, point1s, **fraction_name__adjust_limit_wrap): 

504 '''New L{FrechetEquirectangular} calculator/interpolator. 

505 

506 @kwarg fraction_name__adjust_limit_wrap: Optional C{B{fraction}=None} 

507 and C{B{name}=NN} and keyword arguments for 

508 function L{pygeodesy.equirectangular} I{with 

509 default} C{B{limit}=0} for I{backward compatibility}. 

510 

511 @see: L{Frechet.__init__} for details about B{C{point1s}}, B{C{fraction}}, 

512 B{C{name}} and other exceptions. 

513 ''' 

514 Frechet.__init__(self, point1s, **_xkwds(fraction_name__adjust_limit_wrap, 

515 limit=0)) 

516 self._func = _formy._equirectangular # helper 

517 

518 if _FOR_DOCS: 

519 discrete = Frechet.discrete 

520 

521 

522class FrechetEuclidean(_FrechetMeterRadians): 

523 '''Compute the C{Frechet} distance based on the I{Euclidean} 

524 distance in C{radians} from function L{pygeodesy.euclidean}. 

525 ''' 

526 def __init__(self, point1s, **fraction_name__adjust_radius_wrap): # was=True 

527 '''New L{FrechetEuclidean} calculator/interpolator. 

528 

529 @kwarg fraction_name__adjust_radius_wrap: Optional C{B{fraction}=None} 

530 and C{B{name}=NN} and keyword arguments for 

531 function L{pygeodesy.euclidean}. 

532 

533 @see: L{Frechet.__init__} for details about B{C{point1s}}, B{C{fraction}}, 

534 B{C{name}} and other exceptions. 

535 ''' 

536 Frechet.__init__(self, point1s, **fraction_name__adjust_radius_wrap) 

537 self._func = _formy.euclidean 

538 self._func_ = _formy.euclidean_ 

539 

540 if _FOR_DOCS: 

541 discrete = Frechet.discrete 

542 

543 

544class FrechetExact(Frechet): 

545 '''Compute the C{Frechet} distance based on the I{angular} distance 

546 in C{degrees} from method L{GeodesicExact}C{.Inverse}. 

547 ''' 

548 _units = _unitsBase._Str_degrees 

549 

550 def __init__(self, point1s, datum=None, **fraction_name__wrap): 

551 '''New L{FrechetExact} calculator/interpolator. 

552 

553 @kwarg datum: Datum to override the default C{Datums.WGS84} and first 

554 B{C{point1s}}' datum (L{Datum}, L{Ellipsoid}, L{Ellipsoid2} 

555 or L{a_f2Tuple}). 

556 @kwarg fraction_name__wrap: Optional C{B{fraction}=None} and C{B{name}=NN} 

557 and keyword argument for method C{Inverse1} of class 

558 L{geodesicx.GeodesicExact}. 

559 

560 @raise TypeError: Invalid B{C{datum}}. 

561 

562 @see: L{Frechet.__init__} for details about B{C{point1s}}, B{C{fraction}}, 

563 B{C{name}} and other exceptions. 

564 ''' 

565 Frechet.__init__(self, point1s, **fraction_name__wrap) 

566 self._datum_setter(datum) 

567 self._func = self.datum.ellipsoid.geodesicx.Inverse1 # note -x 

568 

569 if _FOR_DOCS: 

570 discrete = Frechet.discrete 

571 

572 

573class FrechetFlatLocal(_FrechetMeterRadians): 

574 '''Compute the C{Frechet} distance based on the I{angular} distance in 

575 C{radians squared} like function L{pygeodesy.flatLocal_}/L{pygeodesy.hubeny}. 

576 ''' 

577 _units_ = _unitsBase._Str_radians2 # see L{flatLocal_} 

578 

579 def __init__(self, point1s, **fraction_name__datum_scaled_wrap): 

580 '''New L{FrechetFlatLocal}/L{FrechetHubeny} calculator/interpolator. 

581 

582 @kwarg fraction_name__datum_scaled_wrap: Optional C{B{fraction}=None} 

583 and C{B{name}=NN} and keyword arguments for 

584 function L{pygeodesy.flatLocal}. 

585 

586 @see: L{Frechet.__init__} for details about B{C{point1s}}, B{C{fraction}}, 

587 B{C{name}} and other exceptions. 

588 

589 @note: The distance C{units} are C{radians squared}, not C{radians}. 

590 ''' 

591 Frechet.__init__(self, point1s, **fraction_name__datum_scaled_wrap) 

592 self._func = _formy.flatLocal 

593 self._func_ = self.datum.ellipsoid._hubeny_2 

594 

595 if _FOR_DOCS: 

596 discrete = Frechet.discrete 

597 

598 

599class FrechetFlatPolar(_FrechetMeterRadians): 

600 '''Compute the C{Frechet} distance based on the I{angular} distance 

601 in C{radians} from function L{flatPolar_}. 

602 ''' 

603 def __init__(self, point1s, **fraction_name__radius_wrap): 

604 '''New L{FrechetFlatPolar} calculator/interpolator. 

605 

606 @kwarg fraction_name__radius_wrap: Optional C{B{fraction}=None} 

607 and C{B{name}=NN} and keyword arguments 

608 for function L{pygeodesy.flatPolar}. 

609 

610 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

611 B{C{fraction}}, B{C{name}} and other exceptions. 

612 ''' 

613 Frechet.__init__(self, point1s, **fraction_name__radius_wrap) 

614 self._func = _formy.flatPolar 

615 self._func_ = _formy.flatPolar_ 

616 

617 if _FOR_DOCS: 

618 discrete = Frechet.discrete 

619 

620 

621class FrechetHaversine(_FrechetMeterRadians): 

622 '''Compute the C{Frechet} distance based on the I{angular} 

623 distance in C{radians} from function L{pygeodesy.haversine_}. 

624 

625 @note: See note at function L{pygeodesy.vincentys_}. 

626 ''' 

627 def __init__(self, point1s, **fraction_name__radius_wrap): 

628 '''New L{FrechetHaversine} calculator/interpolator. 

629 

630 @kwarg fraction_name__radius_wrap: Optional C{B{fraction}=None} 

631 and C{B{name}=NN} and keyword arguments 

632 for function L{pygeodesy.haversine}. 

633 

634 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

635 B{C{fraction}}, B{C{name}} and other exceptions. 

636 ''' 

637 Frechet.__init__(self, point1s, **fraction_name__radius_wrap) 

638 self._func = _formy.haversine 

639 self._func_ = _formy.haversine_ 

640 

641 if _FOR_DOCS: 

642 discrete = Frechet.discrete 

643 

644 

645class FrechetHubeny(FrechetFlatLocal): # for Karl Hubeny 

646 if _FOR_DOCS: 

647 __doc__ = FrechetFlatLocal.__doc__ 

648 __init__ = FrechetFlatLocal.__init__ 

649 discrete = FrechetFlatLocal.discrete 

650 distance = FrechetFlatLocal.discrete 

651 

652 

653class FrechetKarney(Frechet): 

654 '''Compute the C{Frechet} distance based on the I{angular} 

655 distance in C{degrees} from I{Karney}'s U{geographiclib 

656 <https://PyPI.org/project/geographiclib>} U{geodesic.Geodesic 

657 <https://GeographicLib.SourceForge.io/Python/doc/code.html>} 

658 C{Inverse} method. 

659 ''' 

660 _units = _unitsBase._Str_degrees 

661 

662 def __init__(self, point1s, datum=None, **fraction_name__wrap): 

663 '''New L{FrechetKarney} calculator/interpolator. 

664 

665 @kwarg datum: Datum to override the default C{Datums.WGS84} and 

666 first B{C{knots}}' datum (L{Datum}, L{Ellipsoid}, 

667 L{Ellipsoid2} or L{a_f2Tuple}). 

668 @kwarg fraction_name__wrap: Optional C{B{fraction}=None} and 

669 C{B{name}=NN} and keyword arguments for 

670 method C{Inverse1} of class L{geodesicw.Geodesic}. 

671 

672 @raise ImportError: Package U{geographiclib 

673 <https://PyPI.org/project/geographiclib>} missing. 

674 

675 @raise TypeError: Invalid B{C{datum}}. 

676 

677 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

678 B{C{fraction}}, B{C{name}} and other exceptions. 

679 ''' 

680 Frechet.__init__(self, point1s, **fraction_name__wrap) 

681 self._datum_setter(datum) 

682 self._func = self.datum.ellipsoid.geodesic.Inverse1 

683 

684 if _FOR_DOCS: 

685 discrete = Frechet.discrete 

686 

687 

688class FrechetThomas(_FrechetMeterRadians): 

689 '''Compute the C{Frechet} distance based on the I{angular} distance 

690 in C{radians} from function L{pygeodesy.thomas_}. 

691 ''' 

692 def __init__(self, point1s, **fraction_name__datum_wrap): 

693 '''New L{FrechetThomas} calculator/interpolator. 

694 

695 @kwarg fraction_name__datum_wrap: Optional C{B{fraction}=None} 

696 and C{B{name}=NN} and keyword arguments 

697 for function L{pygeodesy.thomas}. 

698 

699 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

700 B{C{fraction}}, B{C{name}} and other exceptions. 

701 ''' 

702 Frechet.__init__(self, point1s, **fraction_name__datum_wrap) 

703 self._func = _formy.thomas 

704 self._func_ = _formy.thomas_ 

705 

706 if _FOR_DOCS: 

707 discrete = Frechet.discrete 

708 

709 

710class FrechetVincentys(_FrechetMeterRadians): 

711 '''Compute the C{Frechet} distance based on the I{angular} 

712 distance in C{radians} from function L{pygeodesy.vincentys_}. 

713 

714 @note: See note at function L{pygeodesy.vincentys_}. 

715 ''' 

716 def __init__(self, point1s, **fraction_name__radius_wrap): 

717 '''New L{FrechetVincentys} calculator/interpolator. 

718 

719 @kwarg fraction_name__radius_wrap: Optional C{B{fraction}=None} 

720 and C{B{name}=NN} and keyword arguments 

721 for function L{pygeodesy.vincentys}. 

722 

723 @see: L{Frechet.__init__} for details about B{C{point1s}}, 

724 B{C{fraction}}, B{C{name}} and other exceptions. 

725 ''' 

726 Frechet.__init__(self, point1s, **fraction_name__radius_wrap) 

727 self._func = _formy.vincentys 

728 self._func_ = _formy.vincentys_ 

729 

730 if _FOR_DOCS: 

731 discrete = Frechet.discrete 

732 

733 

734def _frechet_(ni, fi, nj, fj, dF, units): # MCCABE 14 

735 '''(INTERNAL) Recursive core of function L{frechet_} 

736 and method C{discrete} of C{Frechet...} classes. 

737 ''' 

738 iFs = {} 

739 

740 def iF(i): # cache index, depth ints and floats 

741 return iFs.setdefault(i, i) 

742 

743 cF = _defaultdict(dict) 

744 

745 def _rF(i, j, r): # recursive Fréchet 

746 i = iF(i) 

747 j = iF(j) 

748 try: 

749 t = cF[i][j] 

750 except KeyError: 

751 r = iF(r + 1) 

752 try: 

753 if i > 0: 

754 if j > 0: 

755 t = min(_rF(i - fi, j, r), 

756 _rF(i - fi, j - fj, r), 

757 _rF(i, j - fj, r)) 

758 elif j < 0: 

759 raise IndexError 

760 else: # j == 0 

761 t = _rF(i - fi, 0, r) 

762 elif i < 0: 

763 raise IndexError 

764 

765 elif j > 0: # i == 0 

766 t = _rF(0, j - fj, r) 

767 elif j < 0: # i == 0 

768 raise IndexError 

769 else: # i == j == 0 

770 t = (NINF, i, j, r) 

771 

772 d = dF(i, j) 

773 if d > t[0]: 

774 t = (d, i, j, r) 

775 except IndexError: 

776 t = (INF, i, j, r) 

777 cF[i][j] = t 

778 return t 

779 

780 t = _rF(ni - 1, nj - 1, 0) 

781 t += (sum(map(len, cF.values())), units) 

782# del cF, iFs 

783 return Frechet6Tuple(t) # *t 

784 

785 

786def frechet_(point1s, point2s, distance=None, units=NN): 

787 '''Compute the I{discrete} U{Fréchet<https://WikiPedia.org/wiki/Frechet_distance>} 

788 distance between two paths, each given as a set of points. 

789 

790 @arg point1s: First set of points (C{LatLon}[], L{Numpy2LatLon}[], 

791 L{Tuple2LatLon}[] or C{other}[]). 

792 @arg point2s: Second set of points (C{LatLon}[], L{Numpy2LatLon}[], 

793 L{Tuple2LatLon}[] or C{other}[]). 

794 @kwarg distance: Callable returning the distance between a B{C{point1s}} 

795 and a B{C{point2s}} point (signature C{(point1, point2)}). 

796 @kwarg units: Optional, the distance units (C{Unit} or C{str}). 

797 

798 @return: A L{Frechet6Tuple}C{(fd, fi1, fi2, r, n, units)} where C{fi1} 

799 and C{fi2} are type C{int} indices into B{C{point1s}} respectively 

800 B{C{point2s}}. 

801 

802 @raise FrechetError: Insufficient number of B{C{point1s}} or B{C{point2s}}. 

803 

804 @raise RecursionError: Recursion depth exceeded, see U{sys.getrecursionlimit() 

805 <https://docs.Python.org/3/library/sys.html#sys.getrecursionlimit>}. 

806 

807 @raise TypeError: If B{C{distance}} is not a callable. 

808 

809 @note: Function L{frechet_} does I{not} support I{fractional} indices 

810 for intermediate B{C{point1s}} and B{C{point2s}}. 

811 ''' 

812 _xcallable(distance=distance) 

813 

814 n1, ps1 = _points2(point1s, closed=False, Error=FrechetError) 

815 n2, ps2 = _points2(point2s, closed=False, Error=FrechetError) 

816 

817 def _dF(i1, i2): 

818 return distance(ps1[i1], ps2[i2]) 

819 

820 return _frechet_(n1, 1, n2, 1, _dF, units) 

821 

822 

823class Frechet6Tuple(_NamedTuple): 

824 '''6-Tuple C{(fd, fi1, fi2, r, n, units)} with the I{discrete} 

825 U{Fréchet<https://WikiPedia.org/wiki/Frechet_distance>} distance 

826 C{fd}, I{fractional} indices C{fi1} and C{fi2} as C{FIx}, the 

827 recursion depth C{r}, the number of distances computed C{n} and 

828 the L{units} class or class or name of the distance C{units}. 

829 

830 If I{fractional} indices C{fi1} and C{fi2} are C{int}, the 

831 returned C{fd} is the distance between C{point1s[fi1]} and 

832 C{point2s[fi2]}. For C{float} indices, the distance is 

833 between an intermediate point along C{point1s[int(fi1)]} and 

834 C{point1s[int(fi1) + 1]} respectively an intermediate point 

835 along C{point2s[int(fi2)]} and C{point2s[int(fi2) + 1]}. 

836 

837 Use function L{fractional} to compute the point at a 

838 I{fractional} index. 

839 ''' 

840 _Names_ = ('fd', 'fi1', 'fi2', 'r', _n_, _units_) 

841 _Units_ = (_Pass, FIx, FIx, Number_, Number_, _Pass) 

842 

843 def toUnits(self, **Error_name): # PYCHOK expected 

844 '''Overloaded C{_NamedTuple.toUnits} for C{fd} units. 

845 ''' 

846 U = _unitsBase._xUnit(self.units, Float) # PYCHOK expected 

847 return _NamedTuple.toUnits(self.reUnit(U), **Error_name) # PYCHOK self 

848 

849# def __gt__(self, other): 

850# _xinstanceof(Frechet6Tuple, other=other) 

851# return self if self.fd > other.fd else other # PYCHOK .fd=[0] 

852# 

853# def __lt__(self, other): 

854# _xinstanceof(Frechet6Tuple, other=other) 

855# return self if self.fd < other.fd else other # PYCHOK .fd=[0] 

856 

857# **) MIT License 

858# 

859# Copyright (C) 2016-2024 -- mrJean1 at Gmail -- All Rights Reserved. 

860# 

861# Permission is hereby granted, free of charge, to any person obtaining a 

862# copy of this software and associated documentation files (the "Software"), 

863# to deal in the Software without restriction, including without limitation 

864# the rights to use, copy, modify, merge, publish, distribute, sublicense, 

865# and/or sell copies of the Software, and to permit persons to whom the 

866# Software is furnished to do so, subject to the following conditions: 

867# 

868# The above copyright notice and this permission notice shall be included 

869# in all copies or substantial portions of the Software. 

870# 

871# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 

872# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 

873# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 

874# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 

875# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 

876# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 

877# OTHER DEALINGS IN THE SOFTWARE.