Coverage for pygeodesy/simplify.py: 99%
227 statements
« prev ^ index » next coverage.py v7.2.2, created at 2024-06-01 11:43 -0400
« prev ^ index » next coverage.py v7.2.2, created at 2024-06-01 11:43 -0400
2# -*- coding: utf-8 -*-
4u'''Simplify or linearize a path.
6Each of the I{simplify} functions is based on a different algorithm and
7produces different, simplified results in (very) different run times for
8the same path of C{LatLon} points.
10Function L{simplify1} eliminates points based on edge lengths shorter
11than a given tolerance.
13The functions L{simplifyRDP} and L{simplifyRDPm} use the original,
14respectively modified I{Ramer-Douglas-Peucker} (RDP) algorithm, iteratively
15finding the point farthest from each path edge. The difference is that
16function L{simplifyRDP} exhaustively searches the most distant point in
17each iteration, while modified L{simplifyRDPm} stops at the first point
18exceeding the distance tolerance.
20Function L{simplifyRW} use the I{Reumann-Witkam} method, sliding a "pipe"
21over each path edge, removing all subsequent points within, closer than
22the pipe radius up to the first point outside the pipe.
24Functions L{simplifyVW} and L{simplifyVWm} are based on the original,
25respectively modified I{Visvalingam-Whyatt} (VW) method using the area of
26the triangle formed by three neigboring points. Function L{simplifyVW}
27removes only a single point per iteration, while modified L{simplifyVWm}
28eliminates in each iteration all points with a triangular area not
29exceeding the tolerance.
31Functions L{simplifyRDP}, L{simplifyRDPm} and L{simplifyRW} provide
32keyword argument I{shortest} to specify of the distance between a point
33and a path edge. If C{True}, use the I{shortest} distance to the path
34edge or edge points, otherwise use the I{perpendicular} distance to
35the extended line through both path edge points.
37Keyword argument B{C{radius}} of all fuctions is set to the mean earth
38radius in C{meter}. Other units can be used, provided that the radius
39and tolerance are always specified in the same units.
41Use keyword argument C{B{indices}=True} in any function to return a
42list of simplified point I{indices} instead of the simplified points.
43The first and last index are always the first and last original index.
45Finally, any additional keyword arguments B{C{options}} to all functions
46are passed thru to function L{pygeodesy.equirectangular4} to specify the
47distance approximation.
49To process C{NumPy} arrays containing rows of lat-, longitude and
50possibly other values, use class L{Numpy2LatLon} to wrap the C{NumPy}
51array into I{on-the-fly-LatLon} points. Pass the L{Numpy2LatLon}
52instance to any I{simplify} function and the returned result will be
53a C{NumPy} array containing the simplified subset, a partial copy of
54the original C{NumPy} array. Use keyword argument C{B{indices}=True}
55to return a list of array row indices inlieu of the simplified array
56subset.
58See:
59 - U{https://Bost.Ocks.org/mike/simplify}
60 - U{https://WikiPedia.org/wiki/Ramer-Douglas-Peucker_algorithm}
61 - U{https://www.ScienceDirect.com/science/article/pii/S0098300402000092}
62 - U{https://hydra.Hull.ac.UK/resources/hull:8338}
63 - U{https://psimpl.SourceForge.net/reumann-witkam.html}
64 - U{https://www.CS.UBC.Ca/cgi-bin/tr/1992/TR-92-07.pdf}
65 - U{https://GitHub.com/FlorianWilhelm/gps_data_with_python}
66 - U{https://www.BDCC.co.UK/Gmaps/GDouglasPeuker.js}
67 - U{https://GitHub.com/mourner/simplify-js}
68 - U{https://GitHub.com/OmarEstrella/simplify.py}
69 - U{https://PyPI.org/project/rdp}
70 - U{https://PyPI.org/project/visvalingam}
71 - U{https://PyPI.org/project/simplification}
72'''
73# make sure int/int division yields float quotient, see .basics
74from __future__ import division as _; del _ # PYCHOK semicolon
76# from pygeodesy.basics import len2 # from .fmath
77from pygeodesy.constants import EPS, R_M, _1_0
78from pygeodesy.errors import _AttributeError, _ValueError
79from pygeodesy.fmath import len2, sqrt0
80from pygeodesy.formy import equirectangular4
81from pygeodesy.interns import _small_, _too_
82from pygeodesy.iters import isNumpy2, isTuple2
83# from pygeodesy.lazily import _ALL_LAZY # from .units
84from pygeodesy.units import _ALL_LAZY, _1mm, Radius_
86from math import degrees, fabs, radians
88__all__ = _ALL_LAZY.simplify
89__version__ = '24.05.25'
92# try:
93# from collections import namedtuple
94# _T2 = namedtuple('_T2', 'ix, h2')
95# except ImportError:
96# class _T2(object):
97# ...
98# namedtuple (and .named._NamedTuple) can not be
99# used because (a) values can not be updated and
100# (b) it produces PyChecker warning "<string>:28:
101# self is not first method argument" which can't
102# be suppressed with command line option --stdlib
103class _T2(object):
104 '''(INTERNAL) VW 2-tuple (index, area).
105 '''
106 # __slots__ are no longer space savers, see
107 # the comments at the class .points.LatLon_
108 # __slots__ = ('ix', 'h2')
110 def __init__(self, ix, h2):
111 self.ix = ix
112 self.h2 = h2
115class _Sy(object):
116 '''(INTERNAL) Simplify state.
117 '''
118 d2i2 = None # d2iP2 or d2iS2
119 d2yxse5 = () # 5-tuple
120 eps = EPS # system epsilon
121 indices = False
122 n = 0
123 options = {}
124 pts = []
125 radius = R_M # mean earth radius
126 r = {} # RDP indices or VW 2-tuples
127 s2 = EPS # tolerance squared
128 s2e = EPS # sentinel
129 subset = None # isNumpy2 or isTuple2
131 def __init__(self, points, tolerance, radius, shortest,
132 indices, **options):
133 '''New C{Simplify} state.
134 '''
135 n, self.pts = len2(points)
136 if n > 0:
137 self.n = n
138 self.r = {0: True, n-1: True} # dict to avoid duplicates
140 if isNumpy2(points) or isTuple2(points): # NOT self.pts
141 self.subset = points.subset
143 if indices:
144 self.indices = True
146 if radius:
147 self.radius = Radius_(radius, low=self.eps)
148 elif self.radius < self.eps:
149 raise _ValueError(radius=radius, txt=_too_(_small_))
151 if options:
152 self.options = options
154 # tolerance converted to degrees squared
155 self.s2 = degrees(tolerance / self.radius)**2
156 if min(self.s2, tolerance) < self.eps:
157 raise _ValueError(tolerance=tolerance, txt=_too_(_small_))
158 self.s2e = self.s2 + 1 # sentinel
160 # compute either the shortest or perpendicular distance
161 self.d2i2 = self.d2iS2 if shortest else self.d2iP2 # PYCHOK attr
163 def d21(self, s, e):
164 '''Set path edge or line thru points[s] to -[e].
165 '''
166 d21, y21, x21, _ = self.d2yxu4(s, e)
167 self.d2yxse5 = d21, y21, x21, s, e
168 return d21 > self.eps
170 def d2ih2(self, n, m, brk):
171 '''Find the tallest distance among all points[n..m]
172 to points[s] to -[e] exceeding the tolerance.
173 '''
174 _, _, _, s, _ = self.d2yxse5
175 eps, _d2yxu4 = self.eps, self.d2yxu4
176 t2, t = self.s2, 0 # tallest
177 for i in range(n, m):
178 d2, _, _, _ = _d2yxu4(s, i)
179 if d2 > t2:
180 t2, t = d2, i
181 if brk and d2 > eps:
182 break
183 return t2, t
185 def d2iP2(self, n, m, brk):
186 '''Find the tallest I{perpendicular} distance among all
187 points[n..m] to the path edge or line thru points[s]
188 to -[e] exceeding the tolerance.
189 '''
190 d21, y21, x21, s, _ = self.d2yxse5
191 eps, _d2yxu4 = self.eps, self.d2yxu4
192 t2, t = self.s2, 0 # tallest
193 for i in range(n, m):
194 d2, y01, x01, _ = _d2yxu4(s, i)
195 if d2 > eps:
196 # perpendicular distance squared
197 d2 = (y01 * x21 - x01 * y21)**2 / d21
198 if d2 > t2:
199 t2, t = d2, i
200 if brk:
201 break
202 return t2, t
204 def d2iS2(self, n, m, brk):
205 '''Find the tallest I{shortest} distance among all
206 points[n..m] to the path edge or line thru points[s]
207 to -[e] exceeding the tolerance.
208 '''
209 # point (x, y) on axis rotated by angle a ccw:
210 # x' = y * sin(a) + x * cos(a)
211 # y' = y * cos(a) - x * sin(a)
212 #
213 # distance (w) along and perpendicular (h) to
214 # a line thru point (dx, dy) and the origin:
215 # w = (y * dy + x * dx) / hypot(dx, dy)
216 # h = (y * dx - x * dy) / hypot(dx, dy)
218 d21, y21, x21, s, e = self.d2yxse5
219 eps, _d2yxu4 = self.eps, self.d2yxu4
220 t2, t = self.s2, 0 # tallest
221 for i in range(n, m):
222 # distance points[i] to -[s]
223 d2, y01, x01, _ = _d2yxu4(s, i)
224 if d2 > eps:
225 w = y01 * y21 + x01 * x21
226 if w > 0:
227 if w < d21:
228 # perpendicular distance squared
229 d2 = (y01 * x21 - x01 * y21)**2 / d21
230 else: # distance points[i] to -[e]
231 d2, _, _, _ = _d2yxu4(e, i)
232 if d2 > t2:
233 t2, t = d2, i
234 if brk:
235 break
236 return t2, t
238 def d2yxu4(self, i, j):
239 '''Return distance I{squared}, points[i] to -[j] deltas
240 and the (longitudinal) unrollment.
241 '''
242 p1, p2= self.pts[i], self.pts[j]
243 return equirectangular4(p1.lat, p1.lon,
244 p2.lat, p2.lon, **self.options)
246 def h2t(self, i1, i0, i2):
247 '''Compute the Visvalingam-Whyatt triangular area,
248 points[i0] is the top and points[i1] to -[i2]
249 form the base of the triangle.
250 '''
251 d21, y21, x21 , _= self.d2yxu4(i1, i2)
252 if d21 > self.eps:
253 d01, y01, x01, _ = self.d2yxu4(i1, i0)
254 if d01 > self.eps:
255 h2 = fabs(y01 * x21 - x01 * y21)
256 # triangle height h = h2 / sqrt(d21) and
257 # the area = h * sqrt(d21) / 2 == h2 / 2
258 return h2 # double triangle area
259 return 0
261 def points(self, r):
262 '''Return the list of simplified points or indices.
263 '''
264 r = sorted(r.keys())
265 if self.indices:
266 return list(r)
267 elif self.subset:
268 return self.subset(r)
269 else:
270 return [self.pts[i] for i in r]
272 def rdp(self, modified):
273 '''Ramer-Douglas-Peucker (RDP) simplification of a
274 path of C{LatLon} points.
276 @arg modified: Use modified RDP (C{bool}).
277 '''
278 n, r = self.n, self.r
279 if n > 1:
280 s2, _d21 = self.s2, self.d21
281 _d2i2, _d2ih2 = self.d2i2, self.d2ih2
283 se = [(0, n-1)]
284 _a = se.append
285 _p = se.pop
286 while se:
287 s, e = _p()
288 s1 = s + 1
289 if e > s1:
290 if _d21(s, e): # points[] to edge [s, e]
291 d2, i = _d2i2(s1, e, modified)
292 else: # points[] to point [s]
293 d2, i = _d2ih2(s1, e, modified)
294 if d2 > s2 and i > 0:
295 r[i] = True
296 _a((i, e))
297 if not modified:
298 _a((s, i))
299 r[s] = True
301 return self.points(r)
303 def rm1(self, m, tol):
304 '''Eliminate one Visvalingam-Whyatt point and recomputes
305 the trangular area of both neighboring points, but
306 removes those too unless the recomputed area exceeds
307 the tolerance.
308 '''
309 _h2t, r = self.h2t, self.r
311 r.pop(m)
312 for n in (m, m - 1):
313 while 0 < n < (len(r) - 1):
314 h2 = _h2t(r[n-1].ix, r[n].ix, r[n+1].ix)
315 if h2 > tol:
316 r[n].h2 = h2
317 break # while
318 else:
319 r.pop(n)
321 def rm2(self, tol):
322 '''Eliminate all Visvalingam-Whyatt points with a
323 triangular area not exceeding the tolerance.
324 '''
325 r, _rm1 = self.r, self.rm1
327 i = len(r) - 1
328 while i > 1:
329 i -= 1
330 if r[i].h2 <= tol:
331 _rm1(i, tol)
332 i = min(i, len(r) - 1)
334 def vwn(self):
335 '''Initialize Visvalingam-Whyatt as list of 2-tuples
336 _T2(ix, h2) where ix is the points[] index and h2
337 is the triangular area I{(times 2)} of that point.
338 '''
339 n, _h2t, s2e, T2 = self.n, self.h2t, self.s2e, _T2
341 self.r = r = []
342 if n > 2:
343 r[:] = [T2(i, _h2t(i-1, i, i+1)) for i in range(1, n-1)]
344 if n > 1:
345 r.append(T2(n-1, s2e))
346 if n > 0:
347 r.insert(0, T2(0, s2e))
348 return len(r)
350 def vwr(self, attr):
351 '''Return the Visvalingam-Whyatt results, optionally
352 including the triangular area (in meters) as
353 attribute attr to each simplified point.
354 '''
355 pts, r = self.pts, self.r
357 # double check the minimal triangular area
358 assert min(t2.h2 for t2 in r) > self.s2 > 0
360 if attr: # return the trangular area (actually
361 # the sqrt of double the triangular area)
362 # converted back from degrees to meter
363 if isNumpy2(pts):
364 raise _AttributeError(attr=attr)
365 m = radians(_1_0) * self.radius
366 r[0].h2 = r[-1].h2 = 0 # zap sentinels
367 for t2 in r: # convert back to meter
368 setattr(pts[t2.ix], attr, sqrt0(t2.h2) * m)
370 # double check for duplicates
371 n = len(r)
372 r = dict((t2.ix, True) for t2 in r)
373 assert len(r) == n
374 return self.points(r)
377def simplify1(points, distance=_1mm, radius=R_M, indices=False, **options):
378 '''Basic simplification of a path of C{LatLon} points.
380 Eliminates any points closer together than the given I{distance}
381 tolerance.
383 @arg points: Path points (C{LatLon}[]).
384 @kwarg distance: Tolerance (C{meter}, same units as B{C{radius}}).
385 @kwarg radius: Mean earth radius (C{meter}).
386 @kwarg indices: If C{True} return the simplified point indices
387 instead of the simplified points (C{bool}).
388 @kwarg options: Optional keyword arguments passed thru to
389 function L{pygeodesy.equirectangular4}.
391 @return: Simplified points (C{LatLon}[]).
393 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},
394 see function L{pygeodesy.equirectangular4}.
396 @raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small.
397 '''
398 S = _Sy(points, distance, radius, True, indices, **options)
400 r, n = S.r, S.n
401 if n > 1:
402 s2, _d2yxu4 = S.s2, S.d2yxu4
404 i = 0
405 for j in range(1, n):
406 d2, _, _, _= _d2yxu4(i, j)
407 if d2 > s2:
408 r[j] = True
409 i = j
411 return S.points(r)
414def simplifyRDP(points, distance=_1mm, radius=R_M, shortest=False,
415 indices=False, **options):
416 '''I{Ramer-Douglas-Peucker} (RDP) simplification of a path of
417 C{LatLon} points.
419 Eliminates any points too close together or closer to an
420 edge than the given I{distance} tolerance.
422 This C{RDP} method exhaustively searches for the point with
423 the largest distance, resulting in worst-case complexity
424 M{O(n**2)} where M{n} is the number of points.
426 @arg points: Path points (C{LatLon}[]).
427 @kwarg distance: Tolerance (C{meter}, same units as B{C{radius}}).
428 @kwarg radius: Mean earth radius (C{meter}).
429 @kwarg shortest: If C{True} use the I{shortest} otherwise the
430 I{perpendicular} distance (C{bool}).
431 @kwarg indices: If C{True} return the simplified point indices
432 instead of the simplified points (C{bool}).
433 @kwarg options: Optional keyword arguments passed thru to
434 function L{pygeodesy.equirectangular4}.
436 @return: Simplified points (C{LatLon}[]).
438 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},
439 see function L{pygeodesy.equirectangular4}.
441 @raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small.
442 '''
443 S = _Sy(points, distance, radius, shortest, indices, **options)
445 return S.rdp(False)
448def simplifyRDPm(points, distance=_1mm, radius=R_M, shortest=False,
449 indices=False, **options):
450 '''Modified I{Ramer-Douglas-Peucker} (RDPm) simplification of a
451 path of C{LatLon} points.
453 Eliminates any points too close together or closer to an edge
454 than the given I{distance} tolerance.
456 This C{RDPm} method stops at the first point farther than the
457 given distance tolerance, significantly reducing the run time
458 (but producing results different from the original C{RDP} method).
460 @arg points: Path points (C{LatLon}[]).
461 @kwarg distance: Tolerance (C{meter}, same units as B{C{radius}}).
462 @kwarg radius: Mean earth radius (C{meter}).
463 @kwarg shortest: If C{True} use the I{shortest} otherwise the
464 I{perpendicular} distance (C{bool}).
465 @kwarg indices: If C{True} return the simplified point indices
466 instead of the simplified points (C{bool}).
467 @kwarg options: Optional keyword arguments passed thru to
468 function L{pygeodesy.equirectangular4}.
470 @return: Simplified points (C{LatLon}[]).
472 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},
473 see function L{pygeodesy.equirectangular4}.
475 @raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small.
476 '''
477 S = _Sy(points, distance, radius, shortest, indices, **options)
479 return S.rdp(True)
482def simplifyRW(points, pipe=_1mm, radius=R_M, shortest=False,
483 indices=False, **options):
484 '''I{Reumann-Witkam} (RW) simplification of a path of C{LatLon}
485 points.
487 Eliminates any points too close together or within the given
488 I{pipe} tolerance along an edge.
490 @arg points: Path points (C{LatLon}[]).
491 @kwarg pipe: Pipe radius, half-width (C{meter}, same units as
492 B{C{radius}}).
493 @kwarg radius: Mean earth radius (C{meter}).
494 @kwarg shortest: If C{True} use the I{shortest} otherwise the
495 I{perpendicular} distance (C{bool}).
496 @kwarg indices: If C{True} return the simplified point indices
497 instead of the simplified points (C{bool}).
498 @kwarg options: Optional keyword arguments passed thru to
499 function L{pygeodesy.equirectangular4}.
501 @return: Simplified points (C{LatLon}[]).
503 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},
504 see function L{pygeodesy.equirectangular4}.
506 @raise ValueError: Tolerance B{C{pipe}} or B{C{radius}} too small.
507 '''
508 S = _Sy(points, pipe, radius, shortest, indices, **options)
510 n, r = S.n, S.r
511 if n > 1:
512 s2, _d21, _d2i2 = S.s2, S.d21, S.d2i2
514 s, e = 0, 1
515 while s < e < n:
516 if _d21(s, e):
517 d2, i = _d2i2(e + 1, n, True)
518 if d2 > s2 and i > 0:
519 r[s] = r[i] = True
520 s, e = i, i + 1
521 else:
522 r[s] = True # r[n-1] = True
523 break # while loop
524 else: # drop points[e]
525 e += 1
527 return S.points(r)
530def simplifyVW(points, area=_1mm, radius=R_M, attr=None,
531 indices=False, **options):
532 '''I{Visvalingam-Whyatt} (VW) simplification of a path of
533 C{LatLon} points.
535 Eliminates any points too close together or with a triangular
536 area not exceeding the given I{area} tolerance I{squared}.
538 This C{VW} method exhaustively searches for the single point
539 with the smallest triangular area, resulting in worst-case
540 complexity M{O(n**2)} where M{n} is the number of points.
542 @arg points: Path points (C{LatLon}[]).
543 @kwarg area: Tolerance (C{meter}, same units as B{C{radius}}).
544 @kwarg radius: Mean earth radius (C{meter}).
545 @kwarg attr: Optional, points attribute to save the area value
546 (C{str}).
547 @kwarg indices: If C{True} return the simplified point indices
548 instead of the simplified points (C{bool}).
549 @kwarg options: Optional keyword arguments passed thru to
550 function L{pygeodesy.equirectangular4}.
552 @return: Simplified points (C{LatLon}[]).
554 @raise AttributeError: If an B{C{attr}} is specified for I{Numpy2}
555 B{C{points}}.
557 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},
558 see function L{pygeodesy.equirectangular4}.
560 @raise ValueError: Tolerance B{C{area}} or B{C{radius}} too small.
561 '''
562 S = _Sy(points, area, radius, False, indices, **options)
564 if S.vwn() > 2:
565 # remove any points too close or
566 # with a zero triangular area
567 S.rm2(0)
569 r, s2, s2e = S.r, S.s2, S.s2e
570 # keep removing the point with the smallest
571 # area until latter exceeds the tolerance
572 while len(r) > 2:
573 m, m2 = 0, s2e
574 for i in range(1, len(r) - 1):
575 h2 = r[i].h2
576 if h2 < m2:
577 m, m2 = i, h2
578 if m2 > s2:
579 break
580 S.rm1(m, 0)
582 return S.vwr(attr)
585def simplifyVWm(points, area=_1mm, radius=R_M, attr=None,
586 indices=False, **options):
587 '''I{Modified Visvalingam-Whyatt} (VWm) simplification of a path
588 of C{LatLon} points.
590 Eliminates any points too close together or with a triangular
591 area not exceeding the given area tolerance I{squared}.
593 This C{VWm} method removes all points with a triangular area
594 below the tolerance in each iteration, significantly reducing
595 the run time (but producing results different from the
596 original C{VW} method).
598 @arg points: Path points (C{LatLon}[]).
599 @kwarg area: Tolerance (C{meter}, same units as B{C{radius}}).
600 @kwarg radius: Mean earth radius (C{meter}).
601 @kwarg attr: Optional, points attribute to save the area value
602 (C{str}).
603 @kwarg indices: If C{True} return the simplified point indices
604 instead of the simplified points (C{bool}).
605 @kwarg options: Optional keyword arguments passed thru to
606 function L{pygeodesy.equirectangular4}.
608 @return: Simplified points (C{LatLon}[]).
610 @raise AttributeError: If an B{C{attr}} is specified for I{Numpy2}
611 B{C{points}}.
613 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},
614 see function L{pygeodesy.equirectangular4}.
616 @raise ValueError: Tolerance B{C{area}} or B{C{radius}} too small.
617 '''
618 S = _Sy(points, area, radius, False, indices, **options)
620 if S.vwn() > 2:
621 # remove all points with an area
622 # not exceeding the tolerance
623 S.rm2(S.s2)
625 return S.vwr(attr)
627# **) MIT License
628#
629# Copyright (C) 2016-2024 -- mrJean1 at Gmail -- All Rights Reserved.
630#
631# Permission is hereby granted, free of charge, to any person obtaining a
632# copy of this software and associated documentation files (the "Software"),
633# to deal in the Software without restriction, including without limitation
634# the rights to use, copy, modify, merge, publish, distribute, sublicense,
635# and/or sell copies of the Software, and to permit persons to whom the
636# Software is furnished to do so, subject to the following conditions:
637#
638# The above copyright notice and this permission notice shall be included
639# in all copies or substantial portions of the Software.
640#
641# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
642# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
643# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
644# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
645# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
646# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
647# OTHER DEALINGS IN THE SOFTWARE.