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, \

88 _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 _name2__, _Named, _NamedTuple, _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, 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__ = '24.05.26'

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/property

133 _f1 = 1

134 _kwds = {} # func_ options

135 _n1 = 0

136 _ps1 = None

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

138

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

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

141

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

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

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

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

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

147 I{fractional} indices.

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

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

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

151 retrievable with property C{kwds}.

152

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

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

155 '''

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

157 if name:

158 self.name = name

159

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

161 if fraction:

162 self.fraction = fraction

163 if units: # and not self.units:

164 self.units = units

165 if kwds:

166 self._kwds = kwds

167

168 @property_RO

169 def adjust(self):

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

171 '''

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

173

174 @property_RO

175 def datum(self):

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

177 '''

178 return self._datum

179

180 def _datum_setter(self, datum):

181 '''(INTERNAL) Set the datum.

182 '''

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

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

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

186

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

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

189

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

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

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

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

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

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

196

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

198

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

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

201

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

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

204 '''

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

206

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

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

209 '''

210 n2, ps2 = self._points2(point2s)

211

212 f2 = _fraction(fraction, n2)

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

214

215 f1 = self.fraction

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

217

218 def _dF(fi1, fi2):

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

220

221 try:

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

223 except TypeError as x:

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

225 raise FrechetError(t, cause=x)

226

227 def distance(self, point1, point2):

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

229 subject to the supplied optional keyword arguments, see

230 property C{kwds}.

231 '''

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

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

234

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

236 def fraction(self):

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

238 '''

239 return self._f1

240

241 @fraction.setter # PYCHOK setter!

242 def fraction(self, fraction):

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

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

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

246

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

248 '''

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

250

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

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

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

254

255 @Property

256 def _func(self):

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

258 self._notOverloaded(**self.kwds)

259

260 @_func.setter_ # PYCHOK setter_underscore!

261 def _func(self, func):

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

263

264 @property_RO

265 def kwds(self):

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

267 '''

268 return self._kwds

269

270 def point(self, point):

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

272

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

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

275

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

277 '''

278 return point # pass thru

279

280 def points_(self, points, i):

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

282

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

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

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

286

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

288 '''

289 return self.point(points[i])

290

291 def points_fraction(self, points, fi):

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

293

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

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

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

297

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

299 '''

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

301

302 def _points2(self, points):

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

304 '''

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

306

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

308 def units(self):

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

310 '''

311 return self._units

312

313 @units.setter # PYCHOK setter!

314 def units(self, units):

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

316

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

318 '''

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

320

321 @property_RO

322 def wrap(self):

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

324 '''

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

326

327

328 class FrechetDegrees(Frechet):

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

330 '''

331 _units = _Str_degrees

332

333 if _FOR_DOCS:

334 __init__ = Frechet.__init__

335 discrete = Frechet.discrete

336

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

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

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

340

341

342 class FrechetRadians(Frechet):

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

344 '''

345 _units = _Str_radians

346

347 if _FOR_DOCS:

348 __init__ = Frechet.__init__

349 discrete = Frechet.discrete

350

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

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

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

354

355 def point(self, point):

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

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

358

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

360 '''

361 try:

362 return point.philam

363 except AttributeError:

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

365

366

367 class _FrechetMeterRadians(Frechet):

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

369 the optional keyword arguments supplied at instantiation

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

371 '''

372 _units = _Str_meter

373 _units_ = _Str_radians

374

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

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

377 the distance function and units from the optional

378 keyword arguments given at this instantiation, see

379 property C{kwds}.

380

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

382 '''

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

384

385 @Property

386 def _func_(self):

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

388 self._notOverloaded(**self.kwds)

389

390 @_func_.setter_ # PYCHOK setter_underscore!

391 def _func_(self, func):

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

393

394

395 class FrechetCosineAndoyerLambert(_FrechetMeterRadians):

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

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

398 '''

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

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

401

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

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

404 function L{pygeodesy.cosineAndoyerLambert}.

405

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

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

408 '''

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

410 self._func = _formy.cosineAndoyerLambert

411 self._func_ = _formy.cosineAndoyerLambert_

412

413 if _FOR_DOCS:

414 discrete = Frechet.discrete

415

416

417 class FrechetCosineForsytheAndoyerLambert(_FrechetMeterRadians):

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

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

420 '''

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

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

423

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

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

426 L{pygeodesy.cosineForsytheAndoyerLambert}.

427

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

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

430 '''

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

432 self._func = _formy.cosineForsytheAndoyerLambert

433 self._func_ = _formy.cosineForsytheAndoyerLambert_

434

435 if _FOR_DOCS:

436 discrete = Frechet.discrete

437

438

439 class FrechetCosineLaw(_FrechetMeterRadians):

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

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

442

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

444 '''

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

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

447

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

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

450 for function L{pygeodesy.cosineLaw}.

451

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

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

454 '''

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

456 self._func = _formy.cosineLaw

457 self._func_ = _formy.cosineLaw_

458

459 if _FOR_DOCS:

460 discrete = Frechet.discrete

461

462

463 class FrechetDistanceTo(Frechet): # FrechetMeter

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

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

466 '''

467 _units = _Str_meter

468

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

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

471

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

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

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

475

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

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

478

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

480 or spherical C{LatLon} class.

481 '''

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

483

484 if _FOR_DOCS:

485 discrete = Frechet.discrete

486

487 def distance(self, p1, p2):

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

489 '''

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

491

492 def _points2(self, points):

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

494 '''

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

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

497

498

499 class FrechetEquirectangular(Frechet):

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

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

502 '''

503 _units = _Str_radians2

504

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

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

507

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

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

510 function L{pygeodesy.equirectangular} I{with

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

512

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

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

515 '''

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

517 limit=0))

518 self._func = _formy._equirectangular # helper

519

520 if _FOR_DOCS:

521 discrete = Frechet.discrete

522

523

524 class FrechetEuclidean(_FrechetMeterRadians):

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

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

527 '''

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

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

530

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

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

533 function L{pygeodesy.euclidean}.

534

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

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

537 '''

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

539 self._func = _formy.euclidean

540 self._func_ = _formy.euclidean_

541

542 if _FOR_DOCS:

543 discrete = Frechet.discrete

544

545

546 class FrechetExact(Frechet):

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

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

549 '''

550 _units = _Str_degrees

551

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

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

554

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

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

557 or L{a_f2Tuple}).

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

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

560 L{geodesicx.GeodesicExact}.

561

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

563

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

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

566 '''

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

568 self._datum_setter(datum)

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

570

571 if _FOR_DOCS:

572 discrete = Frechet.discrete

573

574

575 class FrechetFlatLocal(_FrechetMeterRadians):

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

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

578 '''

579 _units_ = _Str_radians2 # see L{flatLocal_}

580

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

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

583

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

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

586 function L{pygeodesy.flatLocal}.

587

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

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

590

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

592 '''

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

594 self._func = _formy.flatLocal

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

596

597 if _FOR_DOCS:

598 discrete = Frechet.discrete

599

600

601 class FrechetFlatPolar(_FrechetMeterRadians):

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

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

604 '''

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

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

607

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

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

610 for function L{pygeodesy.flatPolar}.

611

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

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

614 '''

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

616 self._func = _formy.flatPolar

617 self._func_ = _formy.flatPolar_

618

619 if _FOR_DOCS:

620 discrete = Frechet.discrete

621

622

623 class FrechetHaversine(_FrechetMeterRadians):

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

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

626

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

628 '''

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

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

631

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

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

634 for function L{pygeodesy.haversine}.

635

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

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

638 '''

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

640 self._func = _formy.haversine

641 self._func_ = _formy.haversine_

642

643 if _FOR_DOCS:

644 discrete = Frechet.discrete

645

646

647 class FrechetHubeny(FrechetFlatLocal): # for Karl Hubeny

648 if _FOR_DOCS:

649 __doc__ = FrechetFlatLocal.__doc__

650 __init__ = FrechetFlatLocal.__init__

651 discrete = FrechetFlatLocal.discrete

652 distance = FrechetFlatLocal.discrete

653

654

655 class FrechetKarney(Frechet):

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

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

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

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

660 C{Inverse} method.

661 '''

662 _units = _Str_degrees

663

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

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

666

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

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

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

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

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

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

673

674 @raise ImportError: Package U{geographiclib

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

676

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

678

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

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

681 '''

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

683 self._datum_setter(datum)

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

685

686 if _FOR_DOCS:

687 discrete = Frechet.discrete

688

689

690 class FrechetThomas(_FrechetMeterRadians):

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

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

693 '''

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

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

696

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

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

699 for function L{pygeodesy.thomas}.

700

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

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

703 '''

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

705 self._func = _formy.thomas

706 self._func_ = _formy.thomas_

707

708 if _FOR_DOCS:

709 discrete = Frechet.discrete

710

711

712 class FrechetVincentys(_FrechetMeterRadians):

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

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

715

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

717 '''

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

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

720

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

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

723 for function L{pygeodesy.vincentys}.

724

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

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

727 '''

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

729 self._func = _formy.vincentys

730 self._func_ = _formy.vincentys_

731

732 if _FOR_DOCS:

733 discrete = Frechet.discrete

734

735

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

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

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

739 '''

740 iFs = {}

741

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

743 return iFs.setdefault(i, i)

744

745 cF = _defaultdict(dict)

746

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

748 i = iF(i)

749 j = iF(j)

750 try:

751 t = cF[i][j]

752 except KeyError:

753 r = iF(r + 1)

754 try:

755 if i > 0:

756 if j > 0:

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

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

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

760 elif j < 0:

761 raise IndexError

762 else: # j == 0

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

764 elif i < 0:

765 raise IndexError

766

767 elif j > 0: # i == 0

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

769 elif j < 0: # i == 0

770 raise IndexError

771 else: # i == j == 0

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

773

774 d = dF(i, j)

775 if d > t[0]:

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

777 except IndexError:

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

779 cF[i][j] = t

780 return t

781

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

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

784# del cF, iFs

785 return Frechet6Tuple(t) # *t

786

787

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

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

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

791

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

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

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

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

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

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

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

799

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

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

802 B{C{point2s}}.

803

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

805

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

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

808

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

810

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

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

813 '''

814 _xcallable(distance=distance)

815

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

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

818

819 def _dF(i1, i2):

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

821

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

823

824

825 class Frechet6Tuple(_NamedTuple):

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

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

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

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

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

831

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

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

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

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

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

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

838

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

840 I{fractional} index.

841 '''

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

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

844

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

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

847 '''

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

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

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

851

852# def __gt__(self, other):

853# _xinstanceof(Frechet6Tuple, other=other)

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

855#

856# def __lt__(self, other):

857# _xinstanceof(Frechet6Tuple, other=other)

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

859

860# **) MIT License

861#

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

863#

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

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

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

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

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

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

870#

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

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

873#

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

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

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

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

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

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

880# OTHER DEALINGS IN THE SOFTWARE.