1

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

3

4 u'''Hausdorff distances.

5

6 Classes L{Hausdorff}, L{HausdorffDegrees}, L{HausdorffRadians},

7 L{HausdorffCosineAndoyerLambert}, L{HausdorffCosineForsytheAndoyerLambert},

8 L{HausdorffCosineLaw}, L{HausdorffDistanceTo}, L{HausdorffEquirectangular},

9 L{HausdorffEuclidean}, L{HausdorffFlatLocal}, L{HausdorffFlatPolar},

10 L{HausdorffHaversine}, L{HausdorffHubeny}, L{HausdorffKarney},

11 L{HausdorffThomas} and L{HausdorffVincentys} to compute U{Hausdorff

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

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

14

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

16 points- and L{HausdorffKarney} 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{Hausdorff} calculator

20 from a given set of C{LatLon} points, called the C{model} or C{template}

21 points.

22

23 C{h = HausdorffXyz(points1, ...)}

24

25 Get the C{directed} or C{symmetric} Hausdorff distance to a second set

26 of C{LatLon} points, named the C{target} points, by using

27

28 C{t6 = h.directed(points2)}

29

30 respectively

31

32 C{t6 = h.symmetric(points2)}.

33

34 Or, use function C{hausdorff_} with a proper C{distance} function and

35 optionally a C{point} function passed as keyword arguments as follows

36

37 C{t6 = hausdorff_(points1, points2, ..., distance=..., point=...)}.

38

39 In all cases, the returned result C{t6} is a L{Hausdorff6Tuple}.

40

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

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

43 instance, more details in the documentation thereof.

44

45 For other points, create a L{Hausdorff} sub-class with the appropriate

46 C{distance} method overloading L{Hausdorff.distance} and optionally a

47 C{point} method overriding L{Hausdorff.point} as the next example.

48

49 >>> from pygeodesy import Hausdorff, hypot_

50 >>>

51 >>> class H3D(Hausdorff):

52 >>> """Custom Hausdorff example.

53 >>> """

54 >>> def distance(self, p1, p2):

55 >>> return hypot_(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z)

56 >>>

57 >>> h3D = H3D(xyz1, ..., units="...")

58 >>> d6 = h3D.directed(xyz2)

59

60 Transcribed from the original SciPy U{Directed Hausdorff Code

61<https://GitHub.com/scipy/scipy/blob/master/scipy/spatial/_hausdorff.pyx>}

62 version 0.19.0, Copyright (C) Tyler Reddy, Richard Gowers, and Max Linke,

63 2016, distributed under the same BSD license as SciPy, including C{early

64 breaking} and C{random sampling} as in U{Abdel Aziz Taha, Allan Hanbury

65"An Efficient Algorithm for Calculating the Exact Hausdorff Distance"

66<https://Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}, IEEE Trans. Pattern

67 Analysis Machine Intelligence (PAMI), vol 37, no 11, pp 2153-2163, Nov 2015.

68'''

69

70 from pygeodesy.constants import INF, NINF, _0_0

71 from pygeodesy.datums import _ellipsoidal_datum, _WGS84

72 from pygeodesy.errors import _IsnotError, PointsError

73# from pygeodesy.fmath import hypot2 # from .formy

74 from pygeodesy.formy import cosineAndoyerLambert_, cosineForsytheAndoyerLambert_, \

75 cosineLaw_, euclidean_, flatPolar_, haversine_, \

76 hypot2, thomas_, vincentys_, _scale_rad, unrollPI

77 from pygeodesy.interns import NN, _datum_, _distanceTo_, _i_, _j_, _points_, _units_

78# from pygeodesy.iters import points2 # from .points

79 from pygeodesy.lazily import _ALL_LAZY, _FOR_DOCS

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

81 from pygeodesy.namedTuples import PhiLam2Tuple

82 from pygeodesy.points import points2, Property_RO, property_doc_

83# from pygeodesy.props import Property_RO, property_doc_ # from .points

84 from pygeodesy.streprs import _boolkwds, Fmt

85 from pygeodesy.units import Float, Number_, _xUnit, _xUnits

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

87 _Str_radians, _Str_radians2

88# from pygeodesy.utily import unrollPI # from .formy

89

90 from math import radians

91 from random import Random

92

93__all__ = _ALL_LAZY.hausdorff

94__version__ = '22.09.24'

95

96

97 class HausdorffError(PointsError):

98 '''Hausdorff issue.

99 '''

100 pass

101

102

103 class Hausdorff(_Named):

104 '''Hausdorff base class, requires method L{Hausdorff.distance} to

105 be overloaded.

106 '''

107 _adjust = None # not applicable

108 _datum = None # not applicable

109 _model = ()

110 _seed = None

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

112 _wrap = None # not applicable

113

114 def __init__(self, points, seed=None, name=NN, units=NN, **wrap_adjust):

115 '''New C{Hausdorff...} calculator.

116

117 @arg points: Initial set of points, aka the C{model} or

118 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

119 C{Tuple2LatLon}[] or C{other}[]).

120 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

121 or C{False} for no U{random sampling<https://

122 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

123 @kwarg name: Optional name for this interpolator (C{str}).

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

125 @kwarg wrap_adjust: Optionally, C{wrap} and unroll longitudes, iff

126 applicable (C{bool}) and C{adjust} wrapped,

127 unrolled longitudinal delta by the cosine

128 of the mean latitude, iff applicable.

129

130 @raise HausdorffError: Insufficient number of B{C{points}} or

131 an invalid B{C{point}}, B{C{seed}} or

132 B{C{wrap}} or B{C{ajust}} not applicable.

133 '''

134 _, self._model = self._points2(points)

135 if seed:

136 self.seed = seed

137 if name:

138 self.name = name

139 if units: # and not self.units:

140 self.units = units

141 if wrap_adjust:

142 _boolkwds(self, **wrap_adjust)

143

144 @Property_RO

145 def adjust(self):

146 '''Get the adjust setting (C{bool} or C{None} if not applicable).

147 '''

148 return self._adjust

149

150 @Property_RO

151 def datum(self):

152 '''Get the datum of this calculator (L{Datum} or C{None} if not applicable).

153 '''

154 return self._datum

155

156 def _datum_setter(self, datum):

157 '''(INTERNAL) Set the datum.

158

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

160 '''

161 d = datum or getattr(self._model[0], _datum_, datum)

162 if d not in (None, self._datum): # PYCHOK no cover

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

164

165 def directed(self, points, early=True):

166 '''Compute only the C{forward Hausdorff} distance.

167

168 @arg points: Second set of points, aka the C{target} (C{LatLon}[],

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

170 @kwarg early: Enable or disable U{early breaking<https://

171 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>} (C{bool}).

172

173 @return: A L{Hausdorff6Tuple}C{(hd, i, j, mn, md, units)}.

174

175 @raise HausdorffError: Insufficient number of B{C{points}} or

176 an invalid B{C{point}}.

177

178 @note: See B{C{points}} note at L{HausdorffDistanceTo}.

179 '''

180 _, ps2 = self._points2(points)

181 return _hausdorff_(self._model, ps2, False, early, self.seed,

182 self.units, self.distance, self.point)

183

184 def distance(self, point1, point2):

185 '''(INTERNAL) I{Must be overloaded}, see function C{notOverloaded}.

186 '''

187 notOverloaded(self, point1, point2) # PYCHOK no cover

188

189 def point(self, point):

190 '''Convert a C{model} or C{target} point for the C{.distance} method.

191 '''

192 return point # pass thru

193

194 def _points2(self, points):

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

196 '''

197 return points2(points, closed=False, Error=HausdorffError)

198

199 @property_doc_(''' the random sampling seed (C{Random}).''')

200 def seed(self):

201 '''Get the random sampling seed (C{any} or C{None}).

202 '''

203 return self._seed

204

205 @seed.setter # PYCHOK setter!

206 def seed(self, seed):

207 '''Set the random sampling seed (C{Random(seed)}) or

208 C{None}, C{0} or C{False} for no U{random sampling

209 <https://Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

210

211 @raise HausdorffError: Invalid B{C{seed}}.

212 '''

213 if seed:

214 try:

215 Random(seed)

216 except (TypeError, ValueError) as x:

217 raise HausdorffError(seed=seed, cause=x)

218 self._seed = seed

219 else:

220 self._seed = None

221

222 def symmetric(self, points, early=True):

223 '''Compute the combined C{forward and reverse Hausdorff} distance.

224

225 @arg points: Second set of points, aka the C{target} (C{LatLon}[],

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

227 @kwarg early: Enable or disable U{early breaking<https://

228 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>} (C{bool}).

229

230 @return: A L{Hausdorff6Tuple}C{(hd, i, j, mn, md, units)}.

231

232 @raise HausdorffError: Insufficient number of B{C{points}} or

233 an invalid B{C{point}}.

234

235 @note: See B{C{points}} note at L{HausdorffDistanceTo}.

236 '''

237 _, ps2 = self._points2(points)

238 return _hausdorff_(self._model, ps2, True, early, self.seed,

239 self.units, self.distance, self.point)

240

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

242 def units(self):

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

244 '''

245 return self._units

246

247 @units.setter # PYCHOK setter!

248 def units(self, units):

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

250

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

252 '''

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

254

255 @Property_RO

256 def wrap(self):

257 '''Get the wrap setting (C{bool} or C{None} if not applicable).

258 '''

259 return self._wrap

260

261

262 class HausdorffDegrees(Hausdorff):

263 '''L{Hausdorff} base class for distances from C{LatLon}

264 points in C{degrees}.

265 '''

266 _units = _Str_degrees

267

268 if _FOR_DOCS:

269 __init__ = Hausdorff.__init__

270 directed = Hausdorff.directed

271 symmetric = Hausdorff.symmetric

272

273

274 class HausdorffRadians(Hausdorff):

275 '''L{Hausdorff} base class for distances from C{LatLon}

276 points converted from C{degrees} to C{radians}.

277 '''

278 _units = _Str_radians

279

280 if _FOR_DOCS:

281 __init__ = Hausdorff.__init__

282 directed = Hausdorff.directed

283 symmetric = Hausdorff.symmetric

284

285 def point(self, point):

286 '''Convert C{(lat, lon)} point in degrees to C{(a, b)}

287 in radians.

288

289 @return: An L{PhiLam2Tuple}C{(phi, lam)}.

290 '''

291 try:

292 return point.philam

293 except AttributeError:

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

295

296

297 class HausdorffCosineAndoyerLambert(HausdorffRadians):

298 '''Compute the C{Hausdorff} distance based on the I{angular} distance

299 in C{radians} from function L{pygeodesy.cosineAndoyerLambert_}.

300

301 @see: L{HausdorffCosineForsytheAndoyerLambert}, L{HausdorffDistanceTo},

302 L{HausdorffExact}, L{HausdorffFlatLocal}, L{HausdorffHubeny},

303 L{HausdorffThomas} and L{HausdorffKarney}.

304 '''

305 _datum = _WGS84

306 _wrap = False

307

308 def __init__(self, points, datum=None, wrap=False, seed=None, name=NN):

309 '''New L{HausdorffCosineAndoyerLambert} calculator.

310

311 @arg points: Initial set of points, aka the C{model} or

312 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

313 C{Tuple2LatLon}[] or C{other}[]).

314 @kwarg datum: Optional datum overriding the default C{Datums.WGS84}

315 and first B{C{points}}' datum (L{Datum}, L{Ellipsoid},

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

317 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI} longitudes

318 (C{bool}).

319 @kwarg seed: Random seed (C{any}) or C{None}, C{0} or

320 C{False} for no U{random sampling<https://

321 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

322 @kwarg name: Optional name for this interpolator (C{str}).

323

324 @raise HausdorffError: Insufficient number of B{C{points}} or

325 invalid B{C{seed}}.

326

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

328 '''

329 HausdorffRadians.__init__(self, points, seed=seed, name=name,

330 wrap=wrap)

331 self._datum_setter(datum)

332

333 if _FOR_DOCS:

334 directed = Hausdorff.directed

335 symmetric = Hausdorff.symmetric

336

337 def distance(self, p1, p2):

338 '''Return the L{pygeodesy.cosineAndoyerLambert_} distance in C{radians}.

339 '''

340 r, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

341 return cosineAndoyerLambert_(p2.phi, p1.phi, r, datum=self._datum)

342

343

344 class HausdorffCosineForsytheAndoyerLambert(HausdorffRadians):

345 '''Compute the C{Hausdorff} distance based on the I{angular} distance

346 in C{radians} from function L{pygeodesy.cosineForsytheAndoyerLambert_}.

347

348 @see: L{HausdorffCosineAndoyerLambert}, L{HausdorffDistanceTo},

349 L{HausdorffExact}, L{HausdorffFlatLocal}, L{HausdorffHubeny},

350 L{HausdorffThomas} and L{HausdorffKarney}.

351 '''

352 _datum = _WGS84

353 _wrap = False

354

355 def __init__(self, points, datum=None, wrap=False, seed=None, name=NN):

356 '''New L{HausdorffCosineForsytheAndoyerLambert} calculator.

357

358 @arg points: Initial set of points, aka the C{model} or

359 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

360 C{Tuple2LatLon}[] or C{other}[]).

361 @kwarg datum: Optional datum overriding the default C{Datums.WGS84}

362 and first B{C{points}}' datum (L{Datum}, L{Ellipsoid},

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

364 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI} longitudes

365 (C{bool}).

366 @kwarg seed: Random seed (C{any}) or C{None}, C{0} or

367 C{False} for no U{random sampling<https://

368 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

369 @kwarg name: Optional name for this interpolator (C{str}).

370

371 @raise HausdorffError: Insufficient number of B{C{points}} or

372 invalid B{C{seed}}.

373

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

375 '''

376 HausdorffRadians.__init__(self, points, seed=seed, name=name,

377 wrap=wrap)

378 self._datum_setter(datum)

379

380 if _FOR_DOCS:

381 directed = Hausdorff.directed

382 symmetric = Hausdorff.symmetric

383

384 def distance(self, p1, p2):

385 '''Return the L{pygeodesy.cosineForsytheAndoyerLambert_} distance in C{radians}.

386 '''

387 r, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

388 return cosineForsytheAndoyerLambert_(p2.phi, p1.phi, r, datum=self._datum)

389

390

391 class HausdorffCosineLaw(HausdorffRadians):

392 '''Compute the C{Hausdorff} distance based on the I{angular}

393 distance in C{radians} from function L{pygeodesy.cosineLaw_}.

394

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

396

397 @see: L{HausdorffEquirectangular}, L{HausdorffEuclidean},

398 L{HausdorffExact}, L{HausdorffFlatLocal}, L{HausdorffHubeny},

399 L{HausdorffFlatPolar}, L{HausdorffHaversine}, L{HausdorffKarney}

400 and L{HausdorffVincentys}.

401 '''

402 _wrap = False

403

404 def __init__(self, points, wrap=False, seed=None, name=NN):

405 '''New L{HausdorffCosineLaw} calculator.

406

407 @arg points: Initial set of points, aka the C{model} or

408 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

409 C{Tuple2LatLon}[] or C{other}[]).

410 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI}

411 longitudes (C{bool}).

412 @kwarg seed: Random seed (C{any}) or C{None}, C{0} or

413 C{False} for no U{random sampling<https://

414 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

415 @kwarg name: Optional name for this interpolator (C{str}).

416

417 @raise HausdorffError: Insufficient number of B{C{points}} or

418 invalid B{C{seed}}.

419 '''

420 HausdorffRadians.__init__(self, points, seed=seed, name=name,

421 wrap=wrap)

422

423 if _FOR_DOCS:

424 directed = Hausdorff.directed

425 symmetric = Hausdorff.symmetric

426

427 def distance(self, p1, p2):

428 '''Return the L{pygeodesy.cosineLaw_} distance in C{radians}.

429 '''

430 d, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

431 return cosineLaw_(p2.phi, p1.phi, d)

432

433

434 class HausdorffDistanceTo(Hausdorff):

435 '''Compute the C{Hausdorff} distance based on the distance from the

436 points' C{LatLon.distanceTo} method, conventionally in C{meter}.

437

438 @see: L{HausdorffCosineAndoyerLambert},

439 L{HausdorffCosineForsytheAndoyerLambert},

440 L{HausdorffExact}, L{HausdorffFlatLocal},

441 L{HausdorffHubeny}, L{HausdorffThomas} and

442 L{HausdorffKarney}.

443 '''

444 _distanceTo_kwds = {}

445 _units = _Str_meter

446

447 def __init__(self, points, seed=None, name=NN, **distanceTo_kwds):

448 '''New L{HausdorffDistanceTo} calculator.

449

450 @arg points: Initial set of points, aka the C{model} or

451 C{template} (C{LatLon}[]).

452 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

453 or C{False} for no U{random sampling<https://

454 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

455 @kwarg name: Optional name for this interpolator (C{str}).

456 @kwarg distanceTo_kwds: Optional keyword arguments for the

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

458 method.

459

460 @raise HausdorffError: Insufficient number of B{C{points}} or

461 an invalid B{C{point}} or B{C{seed}}.

462

463 @raise ImportError: Package U{geographiclib

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

465 iff B{C{points}} are L{ellipsoidalKarney.LatLon}s.

466

467 @note: All C{model}, C{template} and C{target} B{C{points}}

468 I{must} be instances of the same ellipsoidal or

469 spherical C{LatLon} class.

470 '''

471 Hausdorff.__init__(self, points, seed=seed, name=name)

472 if distanceTo_kwds:

473 self._distanceTo_kwds = distanceTo_kwds

474

475 if _FOR_DOCS:

476 directed = Hausdorff.directed

477 symmetric = Hausdorff.symmetric

478

479 def distance(self, p1, p2):

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

481 '''

482 return p1.distanceTo(p2, **self._distanceTo_kwds)

483

484 def _points2(self, points):

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

486 '''

487 np, ps = Hausdorff._points2(self, points)

488 for i, p in enumerate(ps):

489 if not callable(getattr(p, _distanceTo_, None)):

490 i = Fmt.SQUARE(_points_, i)

491 raise HausdorffError(i, p, txt=_distanceTo_)

492 return np, ps

493

494

495 class HausdorffEquirectangular(HausdorffRadians):

496 '''Compute the C{Hausdorff} distance based on the C{equirectangular} distance

497 in C{radians squared} like function L{pygeodesy.equirectangular_}.

498

499 @see: L{HausdorffCosineLaw}, L{HausdorffEuclidean}

500 L{HausdorffExact}, L{HausdorffFlatPolar},

501 L{HausdorffHaversine} and L{HausdorffVincentys}.

502 '''

503 _adjust = True

504 _units = _Str_radians2

505 _wrap = False

506

507 def __init__(self, points, adjust=True, wrap=False, seed=None, name=NN):

508 '''New L{HausdorffEquirectangular} calculator.

509

510 @arg points: Initial set of points, aka the C{model} or

511 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

512 C{Tuple2LatLon}[] or C{other}[]).

513 @kwarg adjust: Adjust the wrapped, unrolled longitudinal

514 delta by the cosine of the mean latitude (C{bool}).

515 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI} longitudes

516 (C{bool}).

517 @kwarg seed: Random seed (C{any}) or C{None}, C{0} or

518 C{False} for no U{random sampling<https://

519 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

520 @kwarg name: Optional name for this interpolator (C{str}).

521

522 @raise HausdorffError: Insufficient number of B{C{points}} or

523 invalid B{C{seed}}.

524 '''

525 HausdorffRadians.__init__(self, points, seed=seed, name=name,

526 adjust=adjust, wrap=wrap)

527

528 if _FOR_DOCS:

529 directed = Hausdorff.directed

530 symmetric = Hausdorff.symmetric

531

532 def distance(self, p1, p2):

533 '''Return the L{pygeodesy.equirectangular_} distance in C{radians squared}.

534 '''

535 r, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

536 if self._adjust:

537 r *= _scale_rad(p1.phi, p2.phi)

538 return hypot2(r, p2.phi - p1.phi) # like equirectangular_ d2

539

540

541 class HausdorffEuclidean(HausdorffRadians):

542 '''Compute the C{Hausdorff} distance based on the C{Euclidean}

543 distance in C{radians} from function L{pygeodesy.euclidean_}.

544

545 @see: L{HausdorffCosineLaw}, L{HausdorffEquirectangular},

546 L{HausdorffExact}, L{HausdorffFlatPolar},

547 L{HausdorffHaversine} and L{HausdorffVincentys}.

548 '''

549 _adjust = True

550 _wrap = True

551

552 def __init__(self, points, adjust=True, seed=None, name=NN):

553 '''New L{HausdorffEuclidean} calculator.

554

555 @arg points: Initial set of points, aka the C{model} or

556 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

557 C{Tuple2LatLon}[] or C{other}[]).

558 @kwarg adjust: Adjust the wrapped, unrolled longitudinal

559 delta by the cosine of the mean latitude (C{bool}).

560 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

561 or C{False} for no U{random sampling<https://

562 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

563 @kwarg name: Optional name for this interpolator (C{str}).

564

565 @raise HausdorffError: Insufficient number of B{C{points}} or

566 invalid B{C{seed}}.

567 '''

568 HausdorffRadians.__init__(self, points, seed=seed, name=name,

569 wrap=True)

570 if not adjust:

571 self._adjust = False

572

573 if _FOR_DOCS:

574 directed = Hausdorff.directed

575 symmetric = Hausdorff.symmetric

576

577 def distance(self, p1, p2):

578 '''Return the L{pygeodesy.euclidean_} distance in C{radians}.

579 '''

580 return euclidean_(p2.phi, p1.phi, p2.lam - p1.lam, adjust=self._adjust)

581

582

583 class HausdorffExact(HausdorffDegrees):

584 '''Compute the C{Hausdorff} distance based on the I{angular}

585 distance in C{degrees} from method L{GeodesicExact}C{.Inverse}.

586

587 @see: L{HausdorffCosineAndoyerLambert},

588 L{HausdorffCosineForsytheAndoyerLambert},

589 L{HausdorffDistanceTo}, L{HausdorffFlatLocal},

590 L{HausdorffHubeny}, L{HausdorffKarney} and

591 L{HausdorffThomas}.

592 '''

593 _datum = _WGS84

594 _Inverse1 = None

595 _units = _Str_degrees

596 _wrap = False

597

598 def __init__(self, points, datum=None, wrap=False, seed=None, name=NN):

599 '''New L{HausdorffKarney} calculator.

600

601 @arg points: Initial set of points, aka the C{model} or

602 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

603 C{Tuple2LatLon}[] or C{other}[]).

604 @kwarg datum: Optional datum overriding the default C{Datums.WGS84}

605 and first B{C{points}}' datum (L{Datum}, L{Ellipsoid},

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

607 @kwarg wrap: Optionally, wrap and L{pygeodesy.unroll180} longitudes

608 (C{bool}).

609 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

610 or C{False} for no U{random sampling<https://

611 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

612 @kwarg name: Optional name for this interpolator (C{str}).

613

614 @raise HausdorffError: Insufficient number of B{C{points}} or

615 invalid B{C{seed}}.

616

617 @raise ImportError: Package U{geographiclib

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

619

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

621 '''

622 HausdorffDegrees.__init__(self, points, seed=seed, name=name,

623 wrap=wrap)

624 self._datum_setter(datum)

625 self._Inverse1 = self.datum.ellipsoid.geodesicx.Inverse1 # note -x

626

627 if _FOR_DOCS:

628 directed = Hausdorff.directed

629 symmetric = Hausdorff.symmetric

630

631 def distance(self, p1, p2):

632 '''Return the non-negative I{angular} distance in C{degrees}.

633 '''

634 return self._Inverse1(p1.lat, p1.lon, p2.lat, p2.lon, wrap=self._wrap)

635

636

637 class HausdorffFlatLocal(HausdorffRadians):

638 '''Compute the C{Hausdorff} distance based on the I{angular} distance in

639 C{radians squared} like function L{pygeodesy.flatLocal_}/L{pygeodesy.hubeny_}.

640

641 @see: L{HausdorffCosineAndoyerLambert},

642 L{HausdorffCosineForsytheAndoyerLambert},

643 L{HausdorffDistanceTo}, L{HausdorffExact},

644 L{HausdorffHubeny}, L{HausdorffThomas} and

645 L{HausdorffKarney}.

646 '''

647 _datum = _WGS84

648 _units = _Str_radians2

649 _wrap = False

650

651 def __init__(self, points, datum=None, wrap=False, seed=None, name=NN):

652 '''New L{HausdorffFlatLocal}/L{HausdorffHubeny} calculator.

653

654 @arg points: Initial set of points, aka the C{model} or

655 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

656 C{Tuple2LatLon}[] or C{other}[]).

657 @kwarg datum: Optional datum overriding the default C{Datums.WGS84}

658 and first B{C{points}}' datum (L{Datum}, L{Ellipsoid},

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

660 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI} longitudes

661 (C{bool}).

662 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

663 or C{False} for no U{random sampling<https://

664 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

665 @kwarg name: Optional name for this interpolator (C{str}).

666

667 @raise HausdorffError: Insufficient number of B{C{points}} or

668 invalid B{C{seed}}.

669

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

671 '''

672 HausdorffRadians.__init__(self, points, seed=seed, name=name,

673 wrap=wrap)

674 self._datum_setter(datum)

675

676 if _FOR_DOCS:

677 directed = Hausdorff.directed

678 symmetric = Hausdorff.symmetric

679

680 def distance(self, p1, p2):

681 '''Return the L{pygeodesy.flatLocal_}/L{pygeodesy.hubeny_} distance

682 in C{radians squared}.

683 '''

684 d, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

685 return self._hubeny_2(p2.phi, p1.phi, d)

686

687 @Property_RO

688 def _hubeny_2(self):

689 '''(INTERNAL) Get and cache the C{.datum.ellipsoid._hubeny_2} method.

690 '''

691 return self.datum.ellipsoid._hubeny_2

692

693

694 class HausdorffFlatPolar(HausdorffRadians):

695 '''Compute the C{Hausdorff} distance based on the I{angular}

696 distance in C{radians} from function L{pygeodesy.flatPolar_}.

697

698 @see: L{HausdorffCosineLaw}, L{HausdorffEquirectangular},

699 L{HausdorffEuclidean}, L{HausdorffExact},

700 L{HausdorffHaversine} and L{HausdorffVincentys}.

701 '''

702 _wrap = False

703

704 def __init__(self, points, wrap=False, seed=None, name=NN):

705 '''New L{HausdorffFlatPolar} calculator.

706

707 @arg points: Initial set of points, aka the C{model} or

708 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

709 C{Tuple2LatLon}[] or C{other}[]).

710 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI} longitudes

711 (C{bool}).

712 @kwarg seed: Random seed (C{any}) or C{None}, C{0} or

713 C{False} for no U{random sampling<https://

714 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

715 @kwarg name: Optional name for this interpolator (C{str}).

716

717 @raise HausdorffError: Insufficient number of B{C{points}} or

718 invalid B{C{seed}}.

719 '''

720 HausdorffRadians.__init__(self, points, seed=seed, name=name,

721 wrap=wrap)

722

723 if _FOR_DOCS:

724 directed = Hausdorff.directed

725 symmetric = Hausdorff.symmetric

726

727 def distance(self, p1, p2):

728 '''Return the L{pygeodesy.flatPolar_} distance in C{radians}.

729 '''

730 r, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

731 return flatPolar_(p2.phi, p1.phi, r)

732

733

734 class HausdorffHaversine(HausdorffRadians):

735 '''Compute the C{Hausdorff} distance based on the I{angular}

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

737

738 @note: See note under L{HausdorffVincentys}.

739

740 @see: L{HausdorffEquirectangular}, L{HausdorffEuclidean},

741 L{HausdorffExact}, L{HausdorffFlatPolar} and

742 L{HausdorffVincentys}.

743 '''

744 _wrap = False

745

746 def __init__(self, points, wrap=False, seed=None, name=NN):

747 '''New L{HausdorffHaversine} calculator.

748

749 @arg points: Initial set of points, aka the C{model} or

750 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

751 C{Tuple2LatLon}[] or C{other}[]).

752 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI}

753 longitudes (C{bool}).

754 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

755 or C{False} for no U{random sampling<https://

756 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

757 @kwarg name: Optional name for this interpolator (C{str}).

758

759 @raise HausdorffError: Insufficient number of B{C{points}} or

760 invalid B{C{seed}}.

761 '''

762 HausdorffRadians.__init__(self, points, seed=seed, name=name,

763 wrap=wrap)

764

765 if _FOR_DOCS:

766 directed = Hausdorff.directed

767 symmetric = Hausdorff.symmetric

768

769 def distance(self, p1, p2):

770 '''Return the L{pygeodesy.haversine_} distance in C{radians}.

771 '''

772 r, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

773 return haversine_(p2.phi, p1.phi, r)

774

775

776 class HausdorffHubeny(HausdorffFlatLocal): # for Karl Hubeny

777 if _FOR_DOCS:

778 __doc__ = HausdorffFlatLocal.__doc__

779 __init__ = HausdorffFlatLocal.__init__

780 directed = HausdorffFlatLocal.directed

781 distance = HausdorffFlatLocal.distance

782 symmetric = HausdorffFlatLocal.symmetric

783

784

785 class HausdorffKarney(HausdorffExact):

786 '''Compute the C{Hausdorff} distance based on the I{angular}

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

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

789 <https://GeographicLib.SourceForge.io/C++/doc/python/code.html>}

790 Inverse method.

791

792 @see: L{HausdorffCosineAndoyerLambert},

793 L{HausdorffCosineForsytheAndoyerLambert},

794 L{HausdorffDistanceTo}, L{HausdorffExact},

795 L{HausdorffFlatLocal}, L{HausdorffHubeny} and

796 L{HausdorffThomas}.

797 '''

798 def __init__(self, points, datum=None, wrap=False, seed=None, name=NN):

799 '''New L{HausdorffKarney} calculator.

800

801 @arg points: Initial set of points, aka the C{model} or

802 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

803 C{Tuple2LatLon}[] or C{other}[]).

804 @kwarg datum: Optional datum overriding the default C{Datums.WGS84}

805 and first B{C{points}}' datum (L{Datum}, L{Ellipsoid},

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

807 @kwarg wrap: Optionally, wrap and L{pygeodesy.unroll180} longitudes

808 (C{bool}).

809 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

810 or C{False} for no U{random sampling<https://

811 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

812 @kwarg name: Optional name for this interpolator (C{str}).

813

814 @raise HausdorffError: Insufficient number of B{C{points}} or

815 invalid B{C{seed}}.

816

817 @raise ImportError: Package U{geographiclib

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

819

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

821 '''

822 HausdorffDegrees.__init__(self, points, seed=seed, name=name,

823 wrap=wrap)

824 self._datum_setter(datum)

825 self._Inverse1 = self.datum.ellipsoid.geodesic.Inverse1

826

827

828 class HausdorffThomas(HausdorffRadians):

829 '''Compute the C{Hausdorff} distance based on the I{angular}

830 distance in C{radians} from function L{pygeodesy.thomas_}.

831

832 @see: L{HausdorffCosineAndoyerLambert},

833 L{HausdorffCosineForsytheAndoyerLambert},

834 L{HausdorffDistanceTo}, L{HausdorffExact},

835 L{HausdorffFlatLocal}, L{HausdorffHubeny}

836 and L{HausdorffKarney}.

837 '''

838 _datum = _WGS84

839 _wrap = False

840

841 def __init__(self, points, datum=None, wrap=False, seed=None, name=NN):

842 '''New L{HausdorffThomas} calculator.

843

844 @arg points: Initial set of points, aka the C{model} or

845 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

846 C{Tuple2LatLon}[] or C{other}[]).

847 @kwarg datum: Optional datum overriding the default C{Datums.WGS84}

848 and first B{C{points}}' datum (L{Datum}, L{Ellipsoid},

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

850 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI} longitudes

851 (C{bool}).

852 @kwarg seed: Random seed (C{any}) or C{None}, C{0} or

853 C{False} for no U{random sampling<https://

854 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

855 @kwarg name: Optional name for this interpolator (C{str}).

856

857 @raise HausdorffError: Insufficient number of B{C{points}} or

858 invalid B{C{seed}}.

859

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

861 '''

862 HausdorffRadians.__init__(self, points, seed=seed, name=name,

863 wrap=wrap)

864 self._datum_setter(datum)

865

866 if _FOR_DOCS:

867 directed = Hausdorff.directed

868 symmetric = Hausdorff.symmetric

869

870 def distance(self, p1, p2):

871 '''Return the L{pygeodesy.thomas_} distance in C{radians}.

872 '''

873 r, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

874 return thomas_(p2.phi, p1.phi, r, datum=self._datum)

875

876

877 class HausdorffVincentys(HausdorffRadians):

878 '''Compute the C{Hausdorff} distance based on the I{angular}

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

880

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

882

883 @see: L{HausdorffCosineLaw}, L{HausdorffEquirectangular},

884 L{HausdorffEuclidean}, L{HausdorffExact},

885 L{HausdorffFlatPolar} and L{HausdorffHaversine}.

886 '''

887 _wrap = False

888

889 def __init__(self, points, wrap=False, seed=None, name=NN):

890 '''New L{HausdorffVincentys} calculator.

891

892 @arg points: Initial set of points, aka the C{model} or

893 C{template} (C{LatLon}[], C{Numpy2LatLon}[],

894 C{Tuple2LatLon}[] or C{other}[]).

895 @kwarg wrap: Optionally, wrap and L{pygeodesy.unrollPI}

896 longitudes (C{bool}).

897 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0}

898 or C{False} for no U{random sampling<https://

899 Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

900 @kwarg name: Optional name for this interpolator (C{str}).

901

902 @raise HausdorffError: Insufficient number of B{C{points}} or

903 invalid B{C{seed}}.

904 '''

905 HausdorffRadians.__init__(self, points, seed=seed, name=name,

906 wrap=wrap)

907

908 if _FOR_DOCS:

909 directed = Hausdorff.directed

910 symmetric = Hausdorff.symmetric

911

912 def distance(self, p1, p2):

913 '''Return the L{pygeodesy.vincentys_} distance in C{radians}.

914 '''

915 r, _ = unrollPI(p1.lam, p2.lam, wrap=self._wrap)

916 return vincentys_(p2.phi, p1.phi, r)

917

918

919 def _hausdorff_(ps1, ps2, both, early, seed, units, distance, point):

920 '''(INTERNAL) Core of function L{hausdorff_} and methods C{directed}

921 and C{symmetric} of classes C{hausdorff.Hausdorff...}.

922 '''

923 # shuffling the points generally increases the

924 # chance of an early break in the inner j loop

925 rr = randomrangenerator(seed) if seed else range

926

927 hd = NINF

928 hi = hj = m = mn = 0

929 md = _0_0

930

931 # forward or forward and backward

932 for fb in range(2 if both else 1):

933 n = len(ps2)

934 for i in rr(len(ps1)):

935 p1 = point(ps1[i])

936 dh, dj = INF, 0

937 for j in rr(n):

938 p2 = point(ps2[j])

939 d = distance(p1, p2)

940 if early and d < hd:

941 break # early

942 elif d < dh:

943 dh, dj = d, j

944 else: # no early break

945 if hd < dh:

946 hd = dh

947 if fb:

948 hi, hj = dj, i

949 else:

950 hi, hj = i, dj

951 md += dh

952 mn += 1

953 m += 1

954 # swap model and target

955 ps1, ps2 = ps2, ps1

956

957 md = None if mn < m else (md / float(m))

958 return Hausdorff6Tuple(hd, hi, hj, m, md, units)

959

960

961 def _point(p):

962 '''Default B{C{point}} callable for function L{hausdorff_}.

963

964 @arg p: The original C{model} or C{target} point (C{any}).

965

966 @return: The point, suitable for the L{hausdorff_}

967 B{C{distance}} callable.

968 '''

969 return p

970

971

972 def hausdorff_(model, target, both=False, early=True, seed=None, units=NN,

973 distance=None, point=_point):

974 '''Compute the C{directed} or C{symmetric} U{Hausdorff

975 <https://WikiPedia.org/wiki/Hausdorff_distance>} distance between 2 sets of points

976 with or without U{early breaking<https://Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}

977 and U{random sampling<https://Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

978

979 @arg model: First set of points (C{LatLon}[], C{Numpy2LatLon}[],

980 C{Tuple2LatLon}[] or C{other}[]).

981 @arg target: Second set of points (C{LatLon}[], C{Numpy2LatLon}[],

982 C{Tuple2LatLon}[] or C{other}[]).

983 @kwarg both: Return the C{directed} (forward only) or the C{symmetric}

984 (combined forward and reverse) C{Hausdorff} distance (C{bool}).

985 @kwarg early: Enable or disable U{early breaking<https://Publik.TUWien.ac.AT/

986 files/PubDat_247739.pdf>} (C{bool}).

987 @kwarg seed: Random sampling seed (C{any}) or C{None}, C{0} or C{False} for no

988 U{random sampling<https://Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}.

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

990 @kwarg distance: Callable returning the distance between a B{C{model}}

991 and B{C{target}} point (signature C{(point1, point2)}).

992 @kwarg point: Callable returning the B{C{model}} or B{C{target}} point

993 suitable for B{C{distance}} (signature C{(point)}).

994

995 @return: A L{Hausdorff6Tuple}C{(hd, i, j, mn, md, units)}.

996

997 @raise HausdorffError: Insufficient number of B{C{model}} or B{C{target}} points.

998

999 @raise TypeError: If B{C{distance}} or B{C{point}} is not callable.

1000 '''

1001 if not callable(distance):

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

1003 if not callable(point):

1004 raise _IsnotError(callable.__name__, point=point)

1005

1006 _, ps1 = points2(model, closed=False, Error=HausdorffError) # PYCHOK non-sequence

1007 _, ps2 = points2(target, closed=False, Error=HausdorffError) # PYCHOK non-sequence

1008 return _hausdorff_(ps1, ps2, both, early, seed, units, distance, point)

1009

1010

1011 class Hausdorff6Tuple(_NamedTuple):

1012 '''6-Tuple C{(hd, i, j, mn, md, units)} with the U{Hausdorff

1013 <https://WikiPedia.org/wiki/Hausdorff_distance>} distance C{hd},

1014 indices C{i} and C{j}, the total count C{mn}, the C{I{mean}

1015 Hausdorff} distance C{md} and the class or name of both distance

1016 C{units}.

1017

1018 For C{directed Hausdorff} distances, count C{mn} is the number

1019 of model points considered. For C{symmetric Hausdorff} distances

1020 count C{mn} twice that.

1021

1022 Indices C{i} and C{j} are the C{model} respectively C{target}

1023 point with the C{hd} distance.

1024

1025 Mean distance C{md} is C{None} if an C{early break} occurred and

1026 U{early breaking<https://Publik.TUWien.ac.AT/files/PubDat_247739.pdf>}

1027 was enabled by keyword argument C{early=True}.

1028 '''

1029 _Names_ = ('hd', _i_, _j_, 'mn', 'md', _units_)

1030 _Units_ = (_Pass, Number_, Number_, Number_, _Pass, _Pass)

1031

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

1033 '''Overloaded C{_NamedTuple.toUnits} for C{hd} and C{md} units.

1034 '''

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

1036 M = _Pass if self.md is None else U # PYCHOK expected

1037 self._Units_ = (U,) + Hausdorff6Tuple._Units_[1:4] \

1038 + (M,) + Hausdorff6Tuple._Units_[5:]

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

1040

1041

1042 def randomrangenerator(seed):

1043 '''Return a C{seed}ed random range function generator.

1044

1045 @arg seed: Initial, internal L{Random} state (C{hashable}

1046 or C{None}).

1047

1048 @note: L{Random} with C{B{seed} is None} seeds from the

1049 current time or from a platform-specific randomness

1050 source, if available.

1051

1052 @return: A function to generate random ranges.

1053

1054 @example:

1055

1056 >>> rrange = randomrangenerator('R')

1057 >>> for r in rrange(n):

1058 >>> ... # r is random in 0..n-1

1059 '''

1060 R = Random(seed)

1061

1062 def _range(n, *stop_step):

1063 '''Like standard L{range}C{start, stop=..., step=...)},

1064 except the returned values are in random order.

1065

1066 @note: Especially C{range(n)} behaves like standard

1067 L{Random.sample}C{(range(n), n)} but avoids

1068 creating a tuple with the entire C{population}

1069 and a list containing all sample values (for

1070 large C{n}).

1071 '''

1072 if stop_step:

1073 s = range(n, *stop_step)

1074

1075 elif n > 32:

1076 r = R.randrange # Random._randbelow

1077 s = set()

1078 for _ in range(n - 32):

1079 i = r(n)

1080 while i in s:

1081 i = r(n)

1082 s.add(i)

1083 yield i

1084 s = set(range(n)) - s # [i for i in range(n) if i not in s]

1085 else:

1086 s = range(n)

1087

1088 s = list(s)

1089 R.shuffle(s)

1090 while s:

1091 yield s.pop(0)

1092

1093 return _range

1094

1095# **) MIT License

1096#

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

1098#

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

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

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

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

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

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

1105#

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

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

1108#

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

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

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

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

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

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

1115# OTHER DEALINGS IN THE SOFTWARE.