1

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

3

4 u'''Fréchet distances.

5

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

7 L{FrechetCosineAndoyerLambert}, L{FrechetCosineForsytheAndoyerLambert},

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

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

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

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

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

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

14

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

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

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

18

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

20 from one set of C{LatLon} points.

21

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

23

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

25 by

26

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

28

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

30 as keyword arguments as follows

31

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

33

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

35

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

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

38 instance, more details in the documentation thereof.

39

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

41 C{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

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

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

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

57 Information Systems Department/Christian Doppler Laboratory for Expert

58 Systems, Technical University Vienna, Austria.

59

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

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

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

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

64 between each points pair.

65

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

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

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

69 points set.

70

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

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

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

74 corresponding set of points.

75

76 The 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>}.

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

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

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

82'''

83

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

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

86 from pygeodesy.datums import _ellipsoidal_datum, _WGS84

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

88 import pygeodesy.formy as _formy

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

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

91 from pygeodesy.lazily import _ALL_LAZY, _FOR_DOCS

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

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

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

95 points2 as _points2, radians

96 from pygeodesy.props import Property, property_doc_, property_RO

97 from pygeodesy.units import FIx, Float, Number_

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

99

100 from 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

107 def _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

119 class FrechetError(PointsError):

120 '''Fréchet issue.

121 '''

122 pass

123

124

125 class 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

326 class 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

340 class 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

365 class _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

393 class 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

415 class 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

437 class 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

461 class 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

497 class 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

522 class 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

544 class 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

573 class 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

599 class 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

621 class 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

645 class 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

653 class 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

688 class 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

710 class 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

734 def _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

786 def 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

823 class 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-2025 -- 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.