Coverage for pygeodesy/frechet.py: 96%
215 statements
« prev ^ index » next coverage.py v7.6.1, created at 2024-11-12 16:17 -0500
« prev ^ index » next coverage.py v7.6.1, created at 2024-11-12 16:17 -0500
2# -*- coding: utf-8 -*-
4u'''Fréchet distances.
6Classes L{Frechet}, L{FrechetDegrees}, L{FrechetRadians},
7L{FrechetCosineAndoyerLambert}, L{FrechetCosineForsytheAndoyerLambert},
8L{FrechetCosineLaw}, L{FrechetDistanceTo}< L{FrechetEquirectangular},
9L{FrechetEuclidean}, L{FrechetExact}, L{FrechetFlatLocal}, L{FrechetFlatPolar},
10L{FrechetHaversine}, L{FrechetHubeny}, L{FrechetKarney}, L{FrechetThomas}
11and L{FrechetVincentys} to compute I{discrete} U{Fréchet
12<https://WikiPedia.org/wiki/Frechet_distance>} distances between two sets
13of C{LatLon}, C{NumPy}, C{tuples} or other types of points.
15Only L{FrechetDistanceTo} -iff used with L{ellipsoidalKarney.LatLon}
16points- and L{FrechetKarney} requires installation of I{Charles Karney}'s
17U{geographiclib<https://PyPI.org/project/geographiclib>}.
19Typical usage is as follows. First, create a C{Frechet} calculator
20from one set of C{LatLon} points.
22C{f = FrechetXyz(point1s, ...)}
24Get the I{discrete} Fréchet distance to another set of C{LatLon} points
25by
27C{t6 = f.discrete(point2s)}
29Or, use function C{frechet_} with a proper C{distance} function passed
30as keyword arguments as follows
32C{t6 = frechet_(point1s, point2s, ..., distance=...)}.
34In both cases, the returned result C{t6} is a L{Frechet6Tuple}.
36For C{(lat, lon, ...)} points in a C{NumPy} array or plain C{tuples},
37wrap the points in a L{Numpy2LatLon} respectively L{Tuple2LatLon}
38instance, more details in the documentation thereof.
40For other points, create a L{Frechet} sub-class with the appropriate
41C{distance} method overloading L{Frechet.distance} as in this example.
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)
54Transcribed from the original U{Computing Discrete Fréchet Distance
55<https://www.kr.TUWien.ac.AT/staff/eiter/et-archive/cdtr9464.pdf>} by
56Eiter, T. and Mannila, H., 1994, April 25, Technical Report CD-TR 94/64,
57Information Systems Department/Christian Doppler Laboratory for Expert
58Systems, Technical University Vienna, Austria.
60This L{Frechet.discrete} implementation optionally generates intermediate
61points for each point set separately. For example, using keyword argument
62C{fraction=0.5} adds one additional point halfway between each pair of
63points. Or using C{fraction=0.1} interpolates nine additional points
64between each points pair.
66The L{Frechet6Tuple} attributes C{fi1} and/or C{fi2} will be I{fractional}
67indices of type C{float} if keyword argument C{fraction} is used. Otherwise,
68C{fi1} and/or C{fi2} are simply type C{int} indices into the respective
69points set.
71For example, C{fractional} index value 2.5 means an intermediate point
72halfway between points[2] and points[3]. Use function L{fractional}
73to obtain the intermediate point for a I{fractional} index in the
74corresponding set of points.
76The C{Fréchet} distance was introduced in 1906 by U{Maurice Fréchet
77<https://WikiPedia.org/wiki/Maurice_Rene_Frechet>}, see U{reference
78[6]<https://www.kr.TUWien.ac.AT/staff/eiter/et-archive/cdtr9464.pdf>}.
79It is a measure of similarity between curves that takes into account the
80location and ordering of the points. Therefore, it is often a better metric
81than the well-known C{Hausdorff} distance, see the L{hausdorff} module.
82'''
84# from pygeodesy.basics import isscalar # from .points
85from pygeodesy.constants import EPS, EPS1, INF, NINF
86from pygeodesy.datums import _ellipsoidal_datum, _WGS84
87from pygeodesy.errors import PointsError, _xattr, _xcallable, _xkwds, _xkwds_get
88import pygeodesy.formy as _formy
89from pygeodesy.interns import NN, _DOT_, _n_, _units_
90# from pygeodesy.iters import points2 as _points2 # from .points
91from pygeodesy.lazily import _ALL_LAZY, _FOR_DOCS
92from pygeodesy.named import _name2__, _Named, _NamedTuple, _Pass
93# from pygeodesy.namedTuples import PhiLam2Tuple # from .points
94from pygeodesy.points import _distanceTo, _fractional, isscalar, PhiLam2Tuple, \
95 points2 as _points2, radians
96from pygeodesy.props import Property, property_doc_, property_RO
97from pygeodesy.units import FIx, Float, Number_
98from pygeodesy import unitsBase as _unitsBase # _Str_..., _xUnit, _xUnits
100from collections import defaultdict as _defaultdict
101# from math import radians # from .points
103__all__ = _ALL_LAZY.frechet
104__version__ = '24.06.15'
107def _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
119class FrechetError(PointsError):
120 '''Fréchet issue.
121 '''
122 pass
125class 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
137 def __init__(self, point1s, fraction=None, units=NN, **name__kwds):
138 '''New C{Frechet...} calculator/interpolator.
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}.
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
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
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)
172 @property_RO
173 def datum(self):
174 '''Get the datum (L{Datum} or C{None} if not applicable).
175 '''
176 return self._datum
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)
185 def discrete(self, point2s, fraction=None):
186 '''Compute the C{forward, discrete Fréchet} distance.
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.
195 @return: A L{Frechet6Tuple}C{(fd, fi1, fi2, r, n, units)}.
197 @raise FrechetError: Insufficient number of B{C{point2s}} or
198 an invalid B{C{point2}} or B{C{fraction}}.
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)
205 def _discrete(self, point2s, fraction, distance):
206 '''(INTERNAL) Detailed C{discrete} with C{disance}.
207 '''
208 n2, ps2 = self._points2(point2s)
210 f2 = _fraction(fraction, n2)
211 p2 = self.points_fraction if f2 < EPS1 else self.points_ # PYCHOK expected
213 f1 = self.fraction
214 p1 = self.points_fraction if f1 < EPS1 else self.points_ # PYCHOK expected
216 def _dF(fi1, fi2):
217 return distance(p1(self._ps1, fi1), p2(ps2, fi2))
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)
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)
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
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.
245 @raise FrechetError: Invalid B{C{fraction}}.
246 '''
247 self._f1 = _fraction(fraction, self._n1)
249# def _func(self, *args, **kwds): # PYCHOK no cover
250# '''(INTERNAL) I{Must be overloaded}.'''
251# self._notOverloaded(*args, **kwds)
253 @Property
254 def _func(self):
255 '''(INTERNAL) I{Must be overloaded}.'''
256 self._notOverloaded(**self.kwds)
258 @_func.setter_ # PYCHOK setter_underscore!
259 def _func(self, func):
260 return _formy._Propy(func, 4, self.kwds)
262 @property_RO
263 def kwds(self):
264 '''Get the supplied, optional keyword arguments (C{dict}).
265 '''
266 return self._kwds
268 def point(self, point):
269 '''Convert a point for the C{.distance} method.
271 @arg point: The point to convert ((C{LatLon}, L{Numpy2LatLon},
272 L{Tuple2LatLon} or C{other}).
274 @return: The converted B{C{point}}.
275 '''
276 return point # pass thru
278 def points_(self, points, i):
279 '''Get and convert a point for the C{.distance} method.
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}).
285 @return: The converted B{C{points[i]}}.
286 '''
287 return self.point(points[i])
289 def points_fraction(self, points, fi):
290 '''Get and convert a I{fractional} point for the C{.distance} method.
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}).
296 @return: The interpolated, converted, intermediate B{C{points[fi]}}.
297 '''
298 return self.point(_fractional(points, fi, None, wrap=None)) # was=self.wrap
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)
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
311 @units.setter # PYCHOK setter!
312 def units(self, units):
313 '''Set the distance units (C{Unit} or C{str}).
315 @raise TypeError: Invalid B{C{units}}.
316 '''
317 self._units = _unitsBase._xUnits(units, Base=Float)
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)
326class FrechetDegrees(Frechet):
327 '''DEPRECATED, use an other C{Frechet*} class.
328 '''
329 _units = _unitsBase._Str_degrees
331 if _FOR_DOCS:
332 __init__ = Frechet.__init__
333 discrete = Frechet.discrete
335 def distance(self, point1, point2, *args, **kwds): # PYCHOK no cover
336 '''I{Must be overloaded}.'''
337 self._notOverloaded(point1, point2, *args, **kwds)
340class FrechetRadians(Frechet):
341 '''DEPRECATED, use an other C{Frechet*} class.
342 '''
343 _units = _unitsBase._Str_radians
345 if _FOR_DOCS:
346 __init__ = Frechet.__init__
347 discrete = Frechet.discrete
349 def distance(self, point1, point2, *args, **kwds): # PYCHOK no cover
350 '''I{Must be overloaded}.'''
351 self._notOverloaded(point1, point2, *args, **kwds)
353 def point(self, point):
354 '''Return B{C{point}} as L{PhiLam2Tuple} to maintain
355 I{backward compatibility} of L{FrechetRadians}.
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))
365class _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
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}.
379 @see: L{Frechet.discrete} for other details.
380 '''
381 return self._discrete(point2s, fraction, _formy._radistance(self))
383 @Property
384 def _func_(self):
385 '''(INTERNAL) I{Must be overloaded}.'''
386 self._notOverloaded(**self.kwds)
388 @_func_.setter_ # PYCHOK setter_underscore!
389 def _func_(self, func):
390 return _formy._Propy(func, 3, self.kwds)
393class 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.
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}.
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_
411 if _FOR_DOCS:
412 discrete = Frechet.discrete
415class 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.
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}.
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_
433 if _FOR_DOCS:
434 discrete = Frechet.discrete
437class FrechetCosineLaw(_FrechetMeterRadians):
438 '''Compute the C{Frechet} distance based on the I{angular} distance
439 in C{radians} from function L{pygeodesy.cosineLaw}.
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.
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}.
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_
457 if _FOR_DOCS:
458 discrete = Frechet.discrete
461class 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
467 def __init__(self, point1s, **fraction_name__distanceTo_kwds):
468 '''New L{FrechetDistanceTo} calculator/interpolator.
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.
474 @see: L{Frechet.__init__} for details about B{C{point1s}}, B{C{fraction}},
475 B{C{name}} and other exceptions.
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)
482 if _FOR_DOCS:
483 discrete = Frechet.discrete
485 def distance(self, p1, p2):
486 '''Return the distance in C{meter}.
487 '''
488 return p1.distanceTo(p2, **self._kwds)
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)
497class 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
503 def __init__(self, point1s, **fraction_name__adjust_limit_wrap):
504 '''New L{FrechetEquirectangular} calculator/interpolator.
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}.
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
518 if _FOR_DOCS:
519 discrete = Frechet.discrete
522class 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.
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}.
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_
540 if _FOR_DOCS:
541 discrete = Frechet.discrete
544class 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
550 def __init__(self, point1s, datum=None, **fraction_name__wrap):
551 '''New L{FrechetExact} calculator/interpolator.
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}.
560 @raise TypeError: Invalid B{C{datum}}.
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
569 if _FOR_DOCS:
570 discrete = Frechet.discrete
573class 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_}
579 def __init__(self, point1s, **fraction_name__datum_scaled_wrap):
580 '''New L{FrechetFlatLocal}/L{FrechetHubeny} calculator/interpolator.
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}.
586 @see: L{Frechet.__init__} for details about B{C{point1s}}, B{C{fraction}},
587 B{C{name}} and other exceptions.
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
595 if _FOR_DOCS:
596 discrete = Frechet.discrete
599class 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.
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}.
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_
617 if _FOR_DOCS:
618 discrete = Frechet.discrete
621class FrechetHaversine(_FrechetMeterRadians):
622 '''Compute the C{Frechet} distance based on the I{angular}
623 distance in C{radians} from function L{pygeodesy.haversine_}.
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.
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}.
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_
641 if _FOR_DOCS:
642 discrete = Frechet.discrete
645class 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
653class 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
662 def __init__(self, point1s, datum=None, **fraction_name__wrap):
663 '''New L{FrechetKarney} calculator/interpolator.
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}.
672 @raise ImportError: Package U{geographiclib
673 <https://PyPI.org/project/geographiclib>} missing.
675 @raise TypeError: Invalid B{C{datum}}.
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
684 if _FOR_DOCS:
685 discrete = Frechet.discrete
688class 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.
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}.
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_
706 if _FOR_DOCS:
707 discrete = Frechet.discrete
710class FrechetVincentys(_FrechetMeterRadians):
711 '''Compute the C{Frechet} distance based on the I{angular}
712 distance in C{radians} from function L{pygeodesy.vincentys_}.
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.
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}.
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_
730 if _FOR_DOCS:
731 discrete = Frechet.discrete
734def _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 = {}
740 def iF(i): # cache index, depth ints and floats
741 return iFs.setdefault(i, i)
743 cF = _defaultdict(dict)
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
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)
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
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
786def 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.
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}).
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}}.
802 @raise FrechetError: Insufficient number of B{C{point1s}} or B{C{point2s}}.
804 @raise RecursionError: Recursion depth exceeded, see U{sys.getrecursionlimit()
805 <https://docs.Python.org/3/library/sys.html#sys.getrecursionlimit>}.
807 @raise TypeError: If B{C{distance}} is not a callable.
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)
814 n1, ps1 = _points2(point1s, closed=False, Error=FrechetError)
815 n2, ps2 = _points2(point2s, closed=False, Error=FrechetError)
817 def _dF(i1, i2):
818 return distance(ps1[i1], ps2[i2])
820 return _frechet_(n1, 1, n2, 1, _dF, units)
823class 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}.
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]}.
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)
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
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]
857# **) MIT License
858#
859# Copyright (C) 2016-2024 -- 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.