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 _IsnotError, PointsError, _xattr, \

88 _xkwds, _xkwds_get

89 import pygeodesy.formy as _formy

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

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

92 from pygeodesy.lazily import _ALL_LAZY, _FOR_DOCS

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

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

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

96 PhiLam2Tuple, points2 as _points2, radians

97 from pygeodesy.props import property_doc_, property_RO

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

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

100 _Str_radians, _Str_radians2

101

102 from collections import defaultdict as _defaultdict

103# from math import radians # from .points

104

105__all__ = _ALL_LAZY.frechet

106__version__ = '23.10.31'

107

108

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

121 class FrechetError(PointsError):

122 '''Fréchet issue.

123 '''

124 pass

125

126

127 class Frechet(_Named):

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

129 be overloaded.

130 '''

131 _datum = _WGS84

132 _func = None # formy function

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, name=NN, units=NN, **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

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

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

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

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

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

151 retrievable with property C{kwds}.

152

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

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

155 or B{C{units}}.

156 '''

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

158 if fraction:

159 self.fraction = fraction

160 if name:

161 self.name = name

162 if units: # and not self.units:

163 self.units = units

164 if kwds:

165 self._kwds = kwds

166

167 @property_RO

168 def adjust(self):

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

170 '''

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

172

173 @property_RO

174 def datum(self):

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

176 '''

177 return self._datum

178

179 def _datum_setter(self, datum):

180 '''(INTERNAL) Set the datum.

181 '''

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

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

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

185

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

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

188

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

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

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

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

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

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

195

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

197

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

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

200

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

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

203 '''

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

205

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

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

208 '''

209 n2, ps2 = self._points2(point2s)

210

211 f2 = _fraction(fraction, n2)

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

213

214 f1 = self.fraction

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

216

217 def _dF(fi1, fi2):

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

219

220 try:

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

222 except TypeError as x:

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

224 raise FrechetError(t, cause=x)

225

226 def distance(self, point1, point2):

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

228 subject to the supplied optional keyword arguments, see

229 property C{kwds}.

230 '''

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

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

233

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

235 def fraction(self):

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

237 '''

238 return self._f1

239

240 @fraction.setter # PYCHOK setter!

241 def fraction(self, fraction):

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

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

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

245

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

247 '''

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

249

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

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

252 notOverloaded(self, *args, **kwds)

253

254 @property_RO

255 def kwds(self):

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

257 '''

258 return self._kwds

259

260 def point(self, point):

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

262

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

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

265

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

267 '''

268 return point # pass thru

269

270 def points_(self, points, i):

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

272

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

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

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

276

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

278 '''

279 return self.point(points[i])

280

281 def points_fraction(self, points, fi):

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

283

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

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

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

287

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

289 '''

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

291

292 def _points2(self, points):

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

294 '''

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

296

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

298 def units(self):

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

300 '''

301 return self._units

302

303 @units.setter # PYCHOK setter!

304 def units(self, units):

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

306

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

308 '''

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

310

311 @property_RO

312 def wrap(self):

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

314 '''

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

316

317

318 class FrechetDegrees(Frechet):

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

320 '''

321 _units = _Str_degrees

322

323 if _FOR_DOCS:

324 __init__ = Frechet.__init__

325 discrete = Frechet.discrete

326

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

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

329 notOverloaded(self, point1, point2, *args, **kwds)

330

331

332 class FrechetRadians(Frechet):

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

334 '''

335 _units = _Str_radians

336

337 if _FOR_DOCS:

338 __init__ = Frechet.__init__

339 discrete = Frechet.discrete

340

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

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

343 notOverloaded(self, point1, point2, *args, **kwds)

344

345 def point(self, point):

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

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

348

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

350 '''

351 try:

352 return point.philam

353 except AttributeError:

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

355

356

357 class _FrechetMeterRadians(Frechet):

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

359 the optional keyword arguments supplied at instantiation

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

361 '''

362 _units = _Str_meter

363 _units_ = _Str_radians

364

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

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

367 the distance function and units from the optional

368 keyword arguments given at this instantiation, see

369 property C{kwds}.

370

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

372 '''

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

374

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

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

377 notOverloaded(self, *args, **kwds)

378

379

380 class FrechetCosineAndoyerLambert(_FrechetMeterRadians):

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

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

383 '''

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

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

386

387 @kwarg datum_wrap: Optional keyword arguments for function

388 L{pygeodesy.cosineAndoyerLambert}.

389

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

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

392 '''

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

394 **datum_wrap)

395 self._func = _formy.cosineAndoyerLambert

396 self._func_ = _formy.cosineAndoyerLambert_

397

398 if _FOR_DOCS:

399 discrete = Frechet.discrete

400

401

402 class FrechetCosineForsytheAndoyerLambert(_FrechetMeterRadians):

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

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

405 '''

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

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

408

409 @kwarg datum_wrap: Optional keyword arguments for function

410 L{pygeodesy.cosineAndoyerLambert}.

411

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

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

414 '''

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

416 **datum_wrap)

417 self._func = _formy.cosineForsytheAndoyerLambert

418 self._func_ = _formy.cosineForsytheAndoyerLambert_

419

420 if _FOR_DOCS:

421 discrete = Frechet.discrete

422

423

424 class FrechetCosineLaw(_FrechetMeterRadians):

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

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

427

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

429 '''

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

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

432

433 @kwarg radius_wrap: Optional keyword arguments for function

434 L{pygeodesy.cosineLaw}.

435

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

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

438 '''

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

440 **radius_wrap)

441 self._func = _formy.cosineLaw

442 self._func_ = _formy.cosineLaw_

443

444 if _FOR_DOCS:

445 discrete = Frechet.discrete

446

447

448 class FrechetDistanceTo(Frechet): # FrechetMeter

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

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

451 '''

452 _units = _Str_meter

453

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

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

456

457 @kwarg distanceTo_kwds: Optional keyword arguments for each

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

459 method.

460

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

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

463

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

465 ellipsoidal or spherical C{LatLon} class.

466 '''

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

468 **distanceTo_kwds)

469

470 if _FOR_DOCS:

471 discrete = Frechet.discrete

472

473 def distance(self, p1, p2):

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

475 '''

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

477

478 def _points2(self, points):

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

480 '''

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

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

483

484

485 class FrechetEquirectangular(Frechet):

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

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

488 '''

489 _units = _Str_radians2

490

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

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

493

494 @kwarg adjust_limit_wrap: Optional keyword arguments for function

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

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

497

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

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

500 '''

501 adjust_limit_wrap = _xkwds(adjust_limit_wrap, limit=0)

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

503 **adjust_limit_wrap)

504 self._func = _formy._equirectangular # helper

505

506 if _FOR_DOCS:

507 discrete = Frechet.discrete

508

509

510 class FrechetEuclidean(_FrechetMeterRadians):

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

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

513 '''

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

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

516

517 @kwarg adjust_radius_wrap: Optional keyword arguments for

518 function L{pygeodesy.euclidean}.

519

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

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

522 '''

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

524 **adjust_radius_wrap)

525 self._func = _formy.euclidean

526 self._func_ = _formy.euclidean_

527

528 if _FOR_DOCS:

529 discrete = Frechet.discrete

530

531

532 class FrechetExact(Frechet):

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

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

535 '''

536 _units = _Str_degrees

537

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

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

540

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

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

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

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

545 of class L{geodesicx.GeodesicExact}.

546

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

548

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

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

551 '''

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

553 **wrap)

554 self._datum_setter(datum)

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

556

557 if _FOR_DOCS:

558 discrete = Frechet.discrete

559

560

561 class FrechetFlatLocal(_FrechetMeterRadians):

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

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

564 '''

565 _units_ = _Str_radians2 # see L{flatLocal_}

566

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

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

569

570 @kwarg datum_scaled_wrap: Optional keyword arguments for

571 function L{pygeodesy.flatLocal}.

572

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

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

575

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

577 '''

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

579 **datum_scaled_wrap)

580 self._func = _formy.flatLocal

581 self._func_ = self.datum.ellipsoid._hubeny_2

582

583 if _FOR_DOCS:

584 discrete = Frechet.discrete

585

586

587 class FrechetFlatPolar(_FrechetMeterRadians):

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

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

590 '''

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

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

593

594 @kwarg radius_wrap: Optional keyword arguments for function

595 L{pygeodesy.flatPolar}.

596

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

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

599 '''

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

601 **radius_wrap)

602 self._func = _formy.flatPolar

603 self._func_ = _formy.flatPolar_

604

605 if _FOR_DOCS:

606 discrete = Frechet.discrete

607

608

609 class FrechetHaversine(_FrechetMeterRadians):

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

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

612

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

614 '''

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

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

617

618 @kwarg radius_wrap: Optional keyword arguments for function

619 L{pygeodesy.haversine}.

620

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

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

623 '''

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

625 **radius_wrap)

626 self._func = _formy.haversine

627 self._func_ = _formy.haversine_

628

629 if _FOR_DOCS:

630 discrete = Frechet.discrete

631

632

633 class FrechetHubeny(FrechetFlatLocal): # for Karl Hubeny

634 if _FOR_DOCS:

635 __doc__ = FrechetFlatLocal.__doc__

636 __init__ = FrechetFlatLocal.__init__

637 discrete = FrechetFlatLocal.discrete

638 distance = FrechetFlatLocal.discrete

639

640

641 class FrechetKarney(Frechet):

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

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

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

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

646 C{Inverse} method.

647 '''

648 _units = _Str_degrees

649

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

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

652

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

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

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

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

657 of class L{geodesicw.Geodesic}.

658

659 @raise ImportError: Package U{geographiclib

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

661

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

663

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

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

666 '''

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

668 **wrap)

669 self._datum_setter(datum)

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

671

672 if _FOR_DOCS:

673 discrete = Frechet.discrete

674

675

676 class FrechetThomas(_FrechetMeterRadians):

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

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

679 '''

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

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

682

683 @kwarg datum_wrap: Optional keyword argument for function

684 L{pygeodesy.thomas}.

685

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

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

688 '''

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

690 **datum_wrap)

691 self._func = _formy.thomas

692 self._func_ = _formy.thomas_

693

694 if _FOR_DOCS:

695 discrete = Frechet.discrete

696

697

698 class FrechetVincentys(_FrechetMeterRadians):

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

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

701

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

703 '''

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

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

706

707 @kwarg radius_wrap: Optional keyword arguments for function

708 L{pygeodesy.vincentys}.

709

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

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

712 '''

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

714 **radius_wrap)

715 self._func = _formy.vincentys

716 self._func_ = _formy.vincentys_

717

718 if _FOR_DOCS:

719 discrete = Frechet.discrete

720

721

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

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

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

725 '''

726 iFs = {}

727

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

729 return iFs.setdefault(i, i)

730

731 cF = _defaultdict(dict)

732

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

734 i = iF(i)

735 j = iF(j)

736 try:

737 t = cF[i][j]

738 except KeyError:

739 r = iF(r + 1)

740 try:

741 if i > 0:

742 if j > 0:

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

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

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

746 elif j < 0:

747 raise IndexError

748 else: # j == 0

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

750 elif i < 0:

751 raise IndexError

752

753 elif j > 0: # i == 0

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

755 elif j < 0: # i == 0

756 raise IndexError

757 else: # i == j == 0

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

759

760 d = dF(i, j)

761 if d > t[0]:

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

763 except IndexError:

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

765 cF[i][j] = t

766 return t

767

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

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

770# del cF, iFs

771 return Frechet6Tuple(t) # *t

772

773

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

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

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

777

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

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

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

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

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

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

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

785

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

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

788 B{C{point2s}}.

789

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

791

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

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

794

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

796

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

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

799 '''

800 if not callable(distance):

801 raise _IsnotError(callable.__name__, distance=distance)

802

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

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

805

806 def _dF(i1, i2):

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

808

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

810

811

812 class Frechet6Tuple(_NamedTuple):

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

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

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

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

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

818

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

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

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

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

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

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

825

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

827 I{fractional} index.

828 '''

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

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

831

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

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

834 '''

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

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

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

838

839# def __gt__(self, other):

840# _xinstanceof(Frechet6Tuple, other=other)

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

842#

843# def __lt__(self, other):

844# _xinstanceof(Frechet6Tuple, other=other)

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

846

847# **) MIT License

848#

849# Copyright (C) 2016-2023 -- mrJean1 at Gmail -- All Rights Reserved.

850#

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

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

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

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

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

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

857#

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

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

860#

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

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

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

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

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

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

867# OTHER DEALINGS IN THE SOFTWARE.