Coverage for pygeodesy/frechet.py: 96%

205 statements  

« prev     ^ index     » next       coverage.py v7.2.2, created at 2024-05-15 16:36 -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 _Named, _NamedTuple, _Pass 

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

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

95 PhiLam2Tuple, points2 as _points2, radians 

96from pygeodesy.props import property_doc_, property_RO 

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

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

99 _Str_radians, _Str_radians2 

100 

101from collections import defaultdict as _defaultdict 

102# from math import radians # from .points 

103 

104__all__ = _ALL_LAZY.frechet 

105__version__ = '24.04.07' 

106 

107 

108def _fraction(fraction, n): 

109 f = 1 # int, no fractional indices 

110 if fraction in (None, 1): 

111 pass 

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

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

114 raise FrechetError(fraction=fraction) 

115 elif fraction < EPS1: 

116 f = float(fraction) 

117 return f 

118 

119 

120class FrechetError(PointsError): 

121 '''Fréchet issue. 

122 ''' 

123 pass 

124 

125 

126class Frechet(_Named): 

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

128 be overloaded. 

129 ''' 

130 _datum = _WGS84 

131 _func = None # formy function 

132 _f1 = 1 

133 _kwds = {} # func_ options 

134 _n1 = 0 

135 _ps1 = None 

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

137 

138 def __init__(self, point1s, fraction=None, name=NN, units=NN, **kwds): 

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

140 

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

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

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

144 interpolate intermediate B{C{point1s}} or use 

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

146 B{C{point1s}} and no I{fractional} indices. 

147 @kwarg name: Optional calculator/interpolator name (C{str}). 

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

149 @kwarg kwds: Optional keyword argument for distance function, 

150 retrievable with property C{kwds}. 

151 

152 @raise FrechetError: Insufficient number of B{C{point1s}} or 

153 an invalid B{C{point1}}, B{C{fraction}} 

154 or B{C{units}}. 

155 ''' 

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

157 if fraction: 

158 self.fraction = fraction 

159 if name: 

160 self.name = name 

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_RO 

254 def kwds(self): 

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

256 ''' 

257 return self._kwds 

258 

259 def point(self, point): 

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

261 

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

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

264 

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

266 ''' 

267 return point # pass thru 

268 

269 def points_(self, points, i): 

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

271 

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

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

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

275 

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

277 ''' 

278 return self.point(points[i]) 

279 

280 def points_fraction(self, points, fi): 

281 '''Get and convert a I{fractional} 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 fi: The I{fractional} index in B{C{points}} (C{float} or C{int}). 

286 

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

288 ''' 

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

290 

291 def _points2(self, points): 

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

293 ''' 

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

295 

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

297 def units(self): 

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

299 ''' 

300 return self._units 

301 

302 @units.setter # PYCHOK setter! 

303 def units(self, units): 

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

305 

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

307 ''' 

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

309 

310 @property_RO 

311 def wrap(self): 

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

313 ''' 

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

315 

316 

317class FrechetDegrees(Frechet): 

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

319 ''' 

320 _units = _Str_degrees 

321 

322 if _FOR_DOCS: 

323 __init__ = Frechet.__init__ 

324 discrete = Frechet.discrete 

325 

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

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

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

329 

330 

331class FrechetRadians(Frechet): 

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

333 ''' 

334 _units = _Str_radians 

335 

336 if _FOR_DOCS: 

337 __init__ = Frechet.__init__ 

338 discrete = Frechet.discrete 

339 

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

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

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

343 

344 def point(self, point): 

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

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

347 

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

349 ''' 

350 try: 

351 return point.philam 

352 except AttributeError: 

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

354 

355 

356class _FrechetMeterRadians(Frechet): 

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

358 the optional keyword arguments supplied at instantiation 

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

360 ''' 

361 _units = _Str_meter 

362 _units_ = _Str_radians 

363 

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

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

366 the distance function and units from the optional 

367 keyword arguments given at this instantiation, see 

368 property C{kwds}. 

369 

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

371 ''' 

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

373 

374 def _func_(self, *args, **kwds): # PYCHOK no cover 

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

376 self._notOverloaded(*args, **kwds) 

377 

378 

379class FrechetCosineAndoyerLambert(_FrechetMeterRadians): 

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

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

382 ''' 

383 def __init__(self, point1s, fraction=None, name=NN, **datum_wrap): 

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

385 

386 @kwarg datum_wrap: Optional keyword arguments for function 

387 L{pygeodesy.cosineAndoyerLambert}. 

388 

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

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

391 ''' 

392 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

393 **datum_wrap) 

394 self._func = _formy.cosineAndoyerLambert 

395 self._func_ = _formy.cosineAndoyerLambert_ 

396 

397 if _FOR_DOCS: 

398 discrete = Frechet.discrete 

399 

400 

401class FrechetCosineForsytheAndoyerLambert(_FrechetMeterRadians): 

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

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

404 ''' 

405 def __init__(self, point1s, fraction=None, name=NN, **datum_wrap): 

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

407 

408 @kwarg datum_wrap: Optional keyword arguments for function 

409 L{pygeodesy.cosineAndoyerLambert}. 

410 

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

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

413 ''' 

414 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

415 **datum_wrap) 

416 self._func = _formy.cosineForsytheAndoyerLambert 

417 self._func_ = _formy.cosineForsytheAndoyerLambert_ 

418 

419 if _FOR_DOCS: 

420 discrete = Frechet.discrete 

421 

422 

423class FrechetCosineLaw(_FrechetMeterRadians): 

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

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

426 

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

428 ''' 

429 def __init__(self, point1s, fraction=None, name=NN, **radius_wrap): 

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

431 

432 @kwarg radius_wrap: Optional keyword arguments for function 

433 L{pygeodesy.cosineLaw}. 

434 

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

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

437 ''' 

438 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

439 **radius_wrap) 

440 self._func = _formy.cosineLaw 

441 self._func_ = _formy.cosineLaw_ 

442 

443 if _FOR_DOCS: 

444 discrete = Frechet.discrete 

445 

446 

447class FrechetDistanceTo(Frechet): # FrechetMeter 

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

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

450 ''' 

451 _units = _Str_meter 

452 

453 def __init__(self, point1s, fraction=None, name=NN, **distanceTo_kwds): 

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

455 

456 @kwarg distanceTo_kwds: Optional keyword arguments for each 

457 B{C{point1s}}' C{LatLon.distanceTo} 

458 method. 

459 

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

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

462 

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

464 ellipsoidal or spherical C{LatLon} class. 

465 ''' 

466 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

467 **distanceTo_kwds) 

468 

469 if _FOR_DOCS: 

470 discrete = Frechet.discrete 

471 

472 def distance(self, p1, p2): 

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

474 ''' 

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

476 

477 def _points2(self, points): 

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

479 ''' 

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

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

482 

483 

484class FrechetEquirectangular(Frechet): 

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

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

487 ''' 

488 _units = _Str_radians2 

489 

490 def __init__(self, point1s, fraction=None, name=NN, **adjust_limit_wrap): 

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

492 

493 @kwarg adjust_limit_wrap: Optional keyword arguments for function 

494 L{pygeodesy.equirectangular_} I{with default} 

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

496 

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

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

499 ''' 

500 adjust_limit_wrap = _xkwds(adjust_limit_wrap, limit=0) 

501 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

502 **adjust_limit_wrap) 

503 self._func = _formy._equirectangular # helper 

504 

505 if _FOR_DOCS: 

506 discrete = Frechet.discrete 

507 

508 

509class FrechetEuclidean(_FrechetMeterRadians): 

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

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

512 ''' 

513 def __init__(self, point1s, fraction=None, name=NN, **adjust_radius_wrap): # was=True 

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

515 

516 @kwarg adjust_radius_wrap: Optional keyword arguments for 

517 function L{pygeodesy.euclidean}. 

518 

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

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

521 ''' 

522 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

523 **adjust_radius_wrap) 

524 self._func = _formy.euclidean 

525 self._func_ = _formy.euclidean_ 

526 

527 if _FOR_DOCS: 

528 discrete = Frechet.discrete 

529 

530 

531class FrechetExact(Frechet): 

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

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

534 ''' 

535 _units = _Str_degrees 

536 

537 def __init__(self, point1s, fraction=None, name=NN, datum=None, **wrap): 

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

539 

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

541 first B{C{point1s}}' datum (L{Datum}, L{Ellipsoid}, 

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

543 @kwarg wrap: Optional keyword argument for method C{Inverse1} 

544 of class L{geodesicx.GeodesicExact}. 

545 

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

547 

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

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

550 ''' 

551 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

552 **wrap) 

553 self._datum_setter(datum) 

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

555 

556 if _FOR_DOCS: 

557 discrete = Frechet.discrete 

558 

559 

560class FrechetFlatLocal(_FrechetMeterRadians): 

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

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

563 ''' 

564 _units_ = _Str_radians2 # see L{flatLocal_} 

565 

566 def __init__(self, point1s, fraction=None, name=NN, **datum_scaled_wrap): 

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

568 

569 @kwarg datum_scaled_wrap: Optional keyword arguments for 

570 function L{pygeodesy.flatLocal}. 

571 

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

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

574 

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

576 ''' 

577 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

578 **datum_scaled_wrap) 

579 self._func = _formy.flatLocal 

580 self._func_ = self.datum.ellipsoid._hubeny_2 

581 

582 if _FOR_DOCS: 

583 discrete = Frechet.discrete 

584 

585 

586class FrechetFlatPolar(_FrechetMeterRadians): 

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

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

589 ''' 

590 def __init__(self, point1s, fraction=None, name=NN, **radius_wrap): 

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

592 

593 @kwarg radius_wrap: Optional keyword arguments for function 

594 L{pygeodesy.flatPolar}. 

595 

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

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

598 ''' 

599 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

600 **radius_wrap) 

601 self._func = _formy.flatPolar 

602 self._func_ = _formy.flatPolar_ 

603 

604 if _FOR_DOCS: 

605 discrete = Frechet.discrete 

606 

607 

608class FrechetHaversine(_FrechetMeterRadians): 

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

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

611 

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

613 ''' 

614 def __init__(self, point1s, fraction=None, name=NN, **radius_wrap): 

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

616 

617 @kwarg radius_wrap: Optional keyword arguments for function 

618 L{pygeodesy.haversine}. 

619 

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

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

622 ''' 

623 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

624 **radius_wrap) 

625 self._func = _formy.haversine 

626 self._func_ = _formy.haversine_ 

627 

628 if _FOR_DOCS: 

629 discrete = Frechet.discrete 

630 

631 

632class FrechetHubeny(FrechetFlatLocal): # for Karl Hubeny 

633 if _FOR_DOCS: 

634 __doc__ = FrechetFlatLocal.__doc__ 

635 __init__ = FrechetFlatLocal.__init__ 

636 discrete = FrechetFlatLocal.discrete 

637 distance = FrechetFlatLocal.discrete 

638 

639 

640class FrechetKarney(Frechet): 

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

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

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

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

645 C{Inverse} method. 

646 ''' 

647 _units = _Str_degrees 

648 

649 def __init__(self, point1s, fraction=None, name=NN, datum=None, **wrap): 

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

651 

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

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

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

655 @kwarg wrap: Optional keyword argument for method C{Inverse1} 

656 of class L{geodesicw.Geodesic}. 

657 

658 @raise ImportError: Package U{geographiclib 

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

660 

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

662 

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

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

665 ''' 

666 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

667 **wrap) 

668 self._datum_setter(datum) 

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

670 

671 if _FOR_DOCS: 

672 discrete = Frechet.discrete 

673 

674 

675class FrechetThomas(_FrechetMeterRadians): 

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

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

678 ''' 

679 def __init__(self, point1s, fraction=None, name=NN, **datum_wrap): 

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

681 

682 @kwarg datum_wrap: Optional keyword argument for function 

683 L{pygeodesy.thomas}. 

684 

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

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

687 ''' 

688 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

689 **datum_wrap) 

690 self._func = _formy.thomas 

691 self._func_ = _formy.thomas_ 

692 

693 if _FOR_DOCS: 

694 discrete = Frechet.discrete 

695 

696 

697class FrechetVincentys(_FrechetMeterRadians): 

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

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

700 

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

702 ''' 

703 def __init__(self, point1s, fraction=None, name=NN, **radius_wrap): 

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

705 

706 @kwarg radius_wrap: Optional keyword arguments for function 

707 L{pygeodesy.vincentys}. 

708 

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

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

711 ''' 

712 Frechet.__init__(self, point1s, fraction=fraction, name=name, 

713 **radius_wrap) 

714 self._func = _formy.vincentys 

715 self._func_ = _formy.vincentys_ 

716 

717 if _FOR_DOCS: 

718 discrete = Frechet.discrete 

719 

720 

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

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

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

724 ''' 

725 iFs = {} 

726 

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

728 return iFs.setdefault(i, i) 

729 

730 cF = _defaultdict(dict) 

731 

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

733 i = iF(i) 

734 j = iF(j) 

735 try: 

736 t = cF[i][j] 

737 except KeyError: 

738 r = iF(r + 1) 

739 try: 

740 if i > 0: 

741 if j > 0: 

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

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

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

745 elif j < 0: 

746 raise IndexError 

747 else: # j == 0 

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

749 elif i < 0: 

750 raise IndexError 

751 

752 elif j > 0: # i == 0 

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

754 elif j < 0: # i == 0 

755 raise IndexError 

756 else: # i == j == 0 

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

758 

759 d = dF(i, j) 

760 if d > t[0]: 

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

762 except IndexError: 

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

764 cF[i][j] = t 

765 return t 

766 

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

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

769# del cF, iFs 

770 return Frechet6Tuple(t) # *t 

771 

772 

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

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

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

776 

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

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

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

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

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

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

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

784 

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

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

787 B{C{point2s}}. 

788 

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

790 

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

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

793 

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

795 

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

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

798 ''' 

799 _xcallable(distance=distance) 

800 

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

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

803 

804 def _dF(i1, i2): 

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

806 

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

808 

809 

810class Frechet6Tuple(_NamedTuple): 

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

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

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

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

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

816 

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

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

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

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

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

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

823 

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

825 I{fractional} index. 

826 ''' 

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

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

829 

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

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

832 ''' 

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

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

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

836 

837# def __gt__(self, other): 

838# _xinstanceof(Frechet6Tuple, other=other) 

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

840# 

841# def __lt__(self, other): 

842# _xinstanceof(Frechet6Tuple, other=other) 

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

844 

845# **) MIT License 

846# 

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

848# 

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

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

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

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

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

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

855# 

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

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

858# 

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

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

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

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

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

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

865# OTHER DEALINGS IN THE SOFTWARE.