Coverage for pygeodesy/frechet.py: 96%

217 statements  

« prev     ^ index     » next       coverage.py v7.2.2, created at 2024-06-01 11:43 -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, \ 

88 _xkwds_get 

89import pygeodesy.formy as _formy 

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

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

92from pygeodesy.lazily import _ALL_LAZY, _FOR_DOCS 

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

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

95from pygeodesy.points import _distanceTo, _fractional, isscalar, \ 

96 PhiLam2Tuple, points2 as _points2, radians 

97from pygeodesy.props import Property, property_doc_, property_RO 

98from pygeodesy.units import FIx, Float, Number_, _xUnit, _xUnits 

99from pygeodesy.unitsBase import _Str_degrees, _Str_meter, _Str_NN, \ 

100 _Str_radians, _Str_radians2 

101 

102from collections import defaultdict as _defaultdict 

103# from math import radians # from .points 

104 

105__all__ = _ALL_LAZY.frechet 

106__version__ = '24.05.26' 

107 

108 

109def _fraction(fraction, n): 

110 f = 1 # int, no fractional indices 

111 if fraction in (None, 1): 

112 pass 

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

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

115 raise FrechetError(fraction=fraction) 

116 elif fraction < EPS1: 

117 f = float(fraction) 

118 return f 

119 

120 

121class FrechetError(PointsError): 

122 '''Fréchet issue. 

123 ''' 

124 pass 

125 

126 

127class Frechet(_Named): 

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

129 be overloaded. 

130 ''' 

131 _datum = _WGS84 

132 _func = None # formy function/property 

133 _f1 = 1 

134 _kwds = {} # func_ options 

135 _n1 = 0 

136 _ps1 = None 

137 _units = _Str_NN # XXX Str to _Pass and for backward compatibility 

138 

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

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

141 

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

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

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

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

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

147 I{fractional} indices. 

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

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

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

151 retrievable with property C{kwds}. 

152 

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

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

155 ''' 

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

157 if name: 

158 self.name = name 

159 

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

161 if fraction: 

162 self.fraction = fraction 

163 if units: # and not self.units: 

164 self.units = units 

165 if kwds: 

166 self._kwds = kwds 

167 

168 @property_RO 

169 def adjust(self): 

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

171 ''' 

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

173 

174 @property_RO 

175 def datum(self): 

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

177 ''' 

178 return self._datum 

179 

180 def _datum_setter(self, datum): 

181 '''(INTERNAL) Set the datum. 

182 ''' 

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

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

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

186 

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

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

189 

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

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

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

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

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

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

196 

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

198 

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

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

201 

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

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

204 ''' 

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

206 

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

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

209 ''' 

210 n2, ps2 = self._points2(point2s) 

211 

212 f2 = _fraction(fraction, n2) 

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

214 

215 f1 = self.fraction 

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

217 

218 def _dF(fi1, fi2): 

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

220 

221 try: 

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

223 except TypeError as x: 

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

225 raise FrechetError(t, cause=x) 

226 

227 def distance(self, point1, point2): 

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

229 subject to the supplied optional keyword arguments, see 

230 property C{kwds}. 

231 ''' 

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

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

234 

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

236 def fraction(self): 

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

238 ''' 

239 return self._f1 

240 

241 @fraction.setter # PYCHOK setter! 

242 def fraction(self, fraction): 

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

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

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

246 

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

248 ''' 

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

250 

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

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

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

254 

255 @Property 

256 def _func(self): 

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

258 self._notOverloaded(**self.kwds) 

259 

260 @_func.setter_ # PYCHOK setter_underscore! 

261 def _func(self, func): 

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

263 

264 @property_RO 

265 def kwds(self): 

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

267 ''' 

268 return self._kwds 

269 

270 def point(self, point): 

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

272 

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

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

275 

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

277 ''' 

278 return point # pass thru 

279 

280 def points_(self, points, i): 

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

282 

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

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

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

286 

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

288 ''' 

289 return self.point(points[i]) 

290 

291 def points_fraction(self, points, fi): 

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

293 

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

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

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

297 

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

299 ''' 

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

301 

302 def _points2(self, points): 

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

304 ''' 

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

306 

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

308 def units(self): 

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

310 ''' 

311 return self._units 

312 

313 @units.setter # PYCHOK setter! 

314 def units(self, units): 

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

316 

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

318 ''' 

319 self._units = _xUnits(units, Base=Float) 

320 

321 @property_RO 

322 def wrap(self): 

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

324 ''' 

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

326 

327 

328class FrechetDegrees(Frechet): 

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

330 ''' 

331 _units = _Str_degrees 

332 

333 if _FOR_DOCS: 

334 __init__ = Frechet.__init__ 

335 discrete = Frechet.discrete 

336 

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

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

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

340 

341 

342class FrechetRadians(Frechet): 

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

344 ''' 

345 _units = _Str_radians 

346 

347 if _FOR_DOCS: 

348 __init__ = Frechet.__init__ 

349 discrete = Frechet.discrete 

350 

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

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

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

354 

355 def point(self, point): 

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

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

358 

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

360 ''' 

361 try: 

362 return point.philam 

363 except AttributeError: 

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

365 

366 

367class _FrechetMeterRadians(Frechet): 

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

369 the optional keyword arguments supplied at instantiation 

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

371 ''' 

372 _units = _Str_meter 

373 _units_ = _Str_radians 

374 

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

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

377 the distance function and units from the optional 

378 keyword arguments given at this instantiation, see 

379 property C{kwds}. 

380 

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

382 ''' 

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

384 

385 @Property 

386 def _func_(self): 

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

388 self._notOverloaded(**self.kwds) 

389 

390 @_func_.setter_ # PYCHOK setter_underscore! 

391 def _func_(self, func): 

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

393 

394 

395class FrechetCosineAndoyerLambert(_FrechetMeterRadians): 

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

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

398 ''' 

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

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

401 

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

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

404 function L{pygeodesy.cosineAndoyerLambert}. 

405 

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

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

408 ''' 

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

410 self._func = _formy.cosineAndoyerLambert 

411 self._func_ = _formy.cosineAndoyerLambert_ 

412 

413 if _FOR_DOCS: 

414 discrete = Frechet.discrete 

415 

416 

417class FrechetCosineForsytheAndoyerLambert(_FrechetMeterRadians): 

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

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

420 ''' 

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

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

423 

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

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

426 L{pygeodesy.cosineForsytheAndoyerLambert}. 

427 

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

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

430 ''' 

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

432 self._func = _formy.cosineForsytheAndoyerLambert 

433 self._func_ = _formy.cosineForsytheAndoyerLambert_ 

434 

435 if _FOR_DOCS: 

436 discrete = Frechet.discrete 

437 

438 

439class FrechetCosineLaw(_FrechetMeterRadians): 

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

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

442 

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

444 ''' 

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

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

447 

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

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

450 for function L{pygeodesy.cosineLaw}. 

451 

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

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

454 ''' 

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

456 self._func = _formy.cosineLaw 

457 self._func_ = _formy.cosineLaw_ 

458 

459 if _FOR_DOCS: 

460 discrete = Frechet.discrete 

461 

462 

463class FrechetDistanceTo(Frechet): # FrechetMeter 

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

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

466 ''' 

467 _units = _Str_meter 

468 

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

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

471 

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

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

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

475 

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

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

478 

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

480 or spherical C{LatLon} class. 

481 ''' 

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

483 

484 if _FOR_DOCS: 

485 discrete = Frechet.discrete 

486 

487 def distance(self, p1, p2): 

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

489 ''' 

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

491 

492 def _points2(self, points): 

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

494 ''' 

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

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

497 

498 

499class FrechetEquirectangular(Frechet): 

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

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

502 ''' 

503 _units = _Str_radians2 

504 

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

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

507 

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

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

510 function L{pygeodesy.equirectangular} I{with 

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

512 

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

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

515 ''' 

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

517 limit=0)) 

518 self._func = _formy._equirectangular # helper 

519 

520 if _FOR_DOCS: 

521 discrete = Frechet.discrete 

522 

523 

524class FrechetEuclidean(_FrechetMeterRadians): 

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

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

527 ''' 

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

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

530 

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

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

533 function L{pygeodesy.euclidean}. 

534 

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

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

537 ''' 

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

539 self._func = _formy.euclidean 

540 self._func_ = _formy.euclidean_ 

541 

542 if _FOR_DOCS: 

543 discrete = Frechet.discrete 

544 

545 

546class FrechetExact(Frechet): 

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

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

549 ''' 

550 _units = _Str_degrees 

551 

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

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

554 

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

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

557 or L{a_f2Tuple}). 

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

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

560 L{geodesicx.GeodesicExact}. 

561 

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

563 

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

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

566 ''' 

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

568 self._datum_setter(datum) 

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

570 

571 if _FOR_DOCS: 

572 discrete = Frechet.discrete 

573 

574 

575class FrechetFlatLocal(_FrechetMeterRadians): 

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

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

578 ''' 

579 _units_ = _Str_radians2 # see L{flatLocal_} 

580 

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

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

583 

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

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

586 function L{pygeodesy.flatLocal}. 

587 

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

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

590 

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

592 ''' 

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

594 self._func = _formy.flatLocal 

595 self._func_ = self.datum.ellipsoid._hubeny_2 

596 

597 if _FOR_DOCS: 

598 discrete = Frechet.discrete 

599 

600 

601class FrechetFlatPolar(_FrechetMeterRadians): 

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

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

604 ''' 

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

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

607 

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

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

610 for function L{pygeodesy.flatPolar}. 

611 

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

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

614 ''' 

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

616 self._func = _formy.flatPolar 

617 self._func_ = _formy.flatPolar_ 

618 

619 if _FOR_DOCS: 

620 discrete = Frechet.discrete 

621 

622 

623class FrechetHaversine(_FrechetMeterRadians): 

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

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

626 

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

628 ''' 

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

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

631 

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

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

634 for function L{pygeodesy.haversine}. 

635 

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

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

638 ''' 

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

640 self._func = _formy.haversine 

641 self._func_ = _formy.haversine_ 

642 

643 if _FOR_DOCS: 

644 discrete = Frechet.discrete 

645 

646 

647class FrechetHubeny(FrechetFlatLocal): # for Karl Hubeny 

648 if _FOR_DOCS: 

649 __doc__ = FrechetFlatLocal.__doc__ 

650 __init__ = FrechetFlatLocal.__init__ 

651 discrete = FrechetFlatLocal.discrete 

652 distance = FrechetFlatLocal.discrete 

653 

654 

655class FrechetKarney(Frechet): 

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

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

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

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

660 C{Inverse} method. 

661 ''' 

662 _units = _Str_degrees 

663 

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

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

666 

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

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

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

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

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

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

673 

674 @raise ImportError: Package U{geographiclib 

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

676 

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

678 

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

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

681 ''' 

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

683 self._datum_setter(datum) 

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

685 

686 if _FOR_DOCS: 

687 discrete = Frechet.discrete 

688 

689 

690class FrechetThomas(_FrechetMeterRadians): 

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

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

693 ''' 

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

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

696 

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

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

699 for function L{pygeodesy.thomas}. 

700 

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

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

703 ''' 

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

705 self._func = _formy.thomas 

706 self._func_ = _formy.thomas_ 

707 

708 if _FOR_DOCS: 

709 discrete = Frechet.discrete 

710 

711 

712class FrechetVincentys(_FrechetMeterRadians): 

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

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

715 

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

717 ''' 

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

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

720 

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

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

723 for function L{pygeodesy.vincentys}. 

724 

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

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

727 ''' 

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

729 self._func = _formy.vincentys 

730 self._func_ = _formy.vincentys_ 

731 

732 if _FOR_DOCS: 

733 discrete = Frechet.discrete 

734 

735 

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

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

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

739 ''' 

740 iFs = {} 

741 

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

743 return iFs.setdefault(i, i) 

744 

745 cF = _defaultdict(dict) 

746 

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

748 i = iF(i) 

749 j = iF(j) 

750 try: 

751 t = cF[i][j] 

752 except KeyError: 

753 r = iF(r + 1) 

754 try: 

755 if i > 0: 

756 if j > 0: 

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

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

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

760 elif j < 0: 

761 raise IndexError 

762 else: # j == 0 

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

764 elif i < 0: 

765 raise IndexError 

766 

767 elif j > 0: # i == 0 

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

769 elif j < 0: # i == 0 

770 raise IndexError 

771 else: # i == j == 0 

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

773 

774 d = dF(i, j) 

775 if d > t[0]: 

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

777 except IndexError: 

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

779 cF[i][j] = t 

780 return t 

781 

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

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

784# del cF, iFs 

785 return Frechet6Tuple(t) # *t 

786 

787 

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

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

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

791 

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

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

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

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

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

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

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

799 

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

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

802 B{C{point2s}}. 

803 

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

805 

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

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

808 

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

810 

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

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

813 ''' 

814 _xcallable(distance=distance) 

815 

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

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

818 

819 def _dF(i1, i2): 

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

821 

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

823 

824 

825class Frechet6Tuple(_NamedTuple): 

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

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

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

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

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

831 

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

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

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

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

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

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

838 

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

840 I{fractional} index. 

841 ''' 

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

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

844 

845 def toUnits(self, **Error): # PYCHOK expected 

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

847 ''' 

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

849 self._Units_ = (U,) + Frechet6Tuple._Units_[1:] 

850 return _NamedTuple.toUnits(self, **Error) 

851 

852# def __gt__(self, other): 

853# _xinstanceof(Frechet6Tuple, other=other) 

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

855# 

856# def __lt__(self, other): 

857# _xinstanceof(Frechet6Tuple, other=other) 

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

859 

860# **) MIT License 

861# 

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

863# 

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

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

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

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

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

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

870# 

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

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

873# 

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

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

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

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

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

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

880# OTHER DEALINGS IN THE SOFTWARE.