1

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

3

4 u'''Simplify or linearize a path.

5

6 Each of the I{simplify} functions is based on a different algorithm and

7 produces different, simplified results in (very) different run times for

8 the same path of C{LatLon} points.

9

10 Function L{simplify1} eliminates points based on edge lengths shorter

11 than a given tolerance.

12

13 The functions L{simplifyRDP} and L{simplifyRDPm} use the original,

14 respectively modified I{Ramer-Douglas-Peucker} (RDP) algorithm, iteratively

15 finding the point farthest from each path edge. The difference is that

16 function L{simplifyRDP} exhaustively searches the most distant point in

17 each iteration, while modified L{simplifyRDPm} stops at the first point

18 exceeding the distance tolerance.

19

20 Function L{simplifyRW} use the I{Reumann-Witkam} method, sliding a "pipe"

21 over each path edge, removing all subsequent points within, closer than

22 the pipe radius up to the first point outside the pipe.

23

24 Functions L{simplifyVW} and L{simplifyVWm} are based on the original,

25 respectively modified I{Visvalingam-Whyatt} (VW) method using the area of

26 the triangle formed by three neigboring points. Function L{simplifyVW}

27 removes only a single point per iteration, while modified L{simplifyVWm}

28 eliminates in each iteration all points with a triangular area not

29 exceeding the tolerance.

30

31 Functions L{simplifyRDP}, L{simplifyRDPm} and L{simplifyRW} provide

32 keyword argument I{shortest} to specify of the distance between a point

33 and a path edge. If C{True}, use the I{shortest} distance to the path

34 edge or edge points, otherwise use the I{perpendicular} distance to

35 the extended line through both path edge points.

36

37 Keyword argument B{C{radius}} of all fuctions is set to the mean earth

38 radius in C{meter}. Other units can be used, provided that the radius

39 and tolerance are always specified in the same units.

40

41 Use keyword argument C{B{indices}=True} in any function to return a

42 list of simplified point I{indices} instead of the simplified points.

43 The first and last index are always the first and last original index.

44

45 Finally, any additional keyword arguments B{C{options}} to all functions

46 are passed thru to function L{pygeodesy.equirectangular4} to specify the

47 distance approximation.

48

49 To process C{NumPy} arrays containing rows of lat-, longitude and

50 possibly other values, use class L{Numpy2LatLon} to wrap the C{NumPy}

51 array into I{on-the-fly-LatLon} points. Pass the L{Numpy2LatLon}

52 instance to any I{simplify} function and the returned result will be

53 a C{NumPy} array containing the simplified subset, a partial copy of

54 the original C{NumPy} array. Use keyword argument C{B{indices}=True}

55 to return a list of array row indices inlieu of the simplified array

56 subset.

57

58 See:

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

74 from __future__ import division as _; del _ # PYCHOK semicolon

75

76# from pygeodesy.basics import len2 # from .fmath

77 from pygeodesy.constants import EPS, R_M, _1_0

78 from pygeodesy.errors import _AttributeError, _ValueError

79 from pygeodesy.fmath import len2, sqrt0

80 from pygeodesy.formy import equirectangular4

81 from pygeodesy.interns import _small_, _too_

82 from pygeodesy.iters import isNumpy2, isTuple2

83# from pygeodesy.lazily import _ALL_LAZY # from .units

84 from pygeodesy.units import _ALL_LAZY, _1mm, Radius_

85

86 from math import degrees, fabs, radians

87

88__all__ = _ALL_LAZY.simplify

89__version__ = '24.08.13'

90

91

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

103 class _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')

109

110 def __init__(self, ix, h2):

111 self.ix = ix

112 self.h2 = h2

113

114

115 class _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

130

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

139

140 if isNumpy2(points) or isTuple2(points): # NOT self.pts

141 self.subset = points.subset

142

143 if indices:

144 self.indices = True

145

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_))

150

151 if options:

152 self.options = options

153

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

159

160 # compute either the shortest or perpendicular distance

161 self.d2i2 = self.d2iS2 if shortest else self.d2iP2 # PYCHOK attr

162

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

169

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

184

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

203

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)

217

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

237

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)

245

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

260

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]

271

272 def rdp(self, modified):

273 '''Ramer-Douglas-Peucker (RDP) simplification of a

274 path of C{LatLon} points.

275

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

282

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

300

301 return self.points(r)

302

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

310

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)

320

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

326

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)

333

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

340

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)

349

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

356

357 # double check the minimal triangular area

358 assert min(t2.h2 for t2 in r) > self.s2 > 0

359

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)

369

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)

375

376

377 def simplify1(points, distance=_1mm, radius=R_M, indices=False, **options):

378 '''Basic simplification of a path of C{LatLon} points.

379

380 Eliminates any points closer together than the given I{distance}

381 tolerance.

382

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}.

390

391 @return: Simplified points (C{LatLon}[]).

392

393 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},

394 see function L{pygeodesy.equirectangular4}.

395

396 @raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small.

397 '''

398 S = _Sy(points, distance, radius, True, indices, **options)

399

400 r, n = S.r, S.n

401 if n > 1:

402 s2, _d2yxu4 = S.s2, S.d2yxu4

403

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

410

411 return S.points(r)

412

413

414 def 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.

418

419 Eliminates any points too close together or closer to an

420 edge than the given I{distance} tolerance.

421

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.

425

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}.

435

436 @return: Simplified points (C{LatLon}[]).

437

438 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},

439 see function L{pygeodesy.equirectangular4}.

440

441 @raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small.

442 '''

443 S = _Sy(points, distance, radius, shortest, indices, **options)

444

445 return S.rdp(False)

446

447

448 def 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.

452

453 Eliminates any points too close together or closer to an edge

454 than the given I{distance} tolerance.

455

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).

459

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}.

469

470 @return: Simplified points (C{LatLon}[]).

471

472 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},

473 see function L{pygeodesy.equirectangular4}.

474

475 @raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small.

476 '''

477 S = _Sy(points, distance, radius, shortest, indices, **options)

478

479 return S.rdp(True)

480

481

482 def 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.

486

487 Eliminates any points too close together or within the given

488 I{pipe} tolerance along an edge.

489

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}.

500

501 @return: Simplified points (C{LatLon}[]).

502

503 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},

504 see function L{pygeodesy.equirectangular4}.

505

506 @raise ValueError: Tolerance B{C{pipe}} or B{C{radius}} too small.

507 '''

508 S = _Sy(points, pipe, radius, shortest, indices, **options)

509

510 n, r = S.n, S.r

511 if n > 1:

512 s2, _d21, _d2i2 = S.s2, S.d21, S.d2i2

513

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

526

527 return S.points(r)

528

529

530 def 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.

534

535 Eliminates any points too close together or with a triangular

536 area not exceeding the given I{area} tolerance I{squared}.

537

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.

541

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}.

551

552 @return: Simplified points (C{LatLon}[]).

553

554 @raise AttributeError: If an B{C{attr}} is specified for I{Numpy2}

555 B{C{points}}.

556

557 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},

558 see function L{pygeodesy.equirectangular4}.

559

560 @raise ValueError: Tolerance B{C{area}} or B{C{radius}} too small.

561 '''

562 S = _Sy(points, area, radius, False, indices, **options)

563

564 if S.vwn() > 2:

565 # remove any points too close or

566 # with a zero triangular area

567 S.rm2(0)

568

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)

581

582 return S.vwr(attr)

583

584

585 def 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.

589

590 Eliminates any points too close together or with a triangular

591 area not exceeding the given area tolerance I{squared}.

592

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).

597

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}.

607

608 @return: Simplified points (C{LatLon}[]).

609

610 @raise AttributeError: If an B{C{attr}} is specified for I{Numpy2}

611 B{C{points}}.

612

613 @raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}},

614 see function L{pygeodesy.equirectangular4}.

615

616 @raise ValueError: Tolerance B{C{area}} or B{C{radius}} too small.

617 '''

618 S = _Sy(points, area, radius, False, indices, **options)

619

620 if S.vwn() > 2:

621 # remove all points with an area

622 # not exceeding the tolerance

623 S.rm2(S.s2)

624

625 return S.vwr(attr)

626

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.