1

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

3

4 u'''I{Boolean} operations on I{composite} polygons and I{clip}s.

5

6 Classes L{BooleanFHP} and L{BooleanGH} are I{composites} and

7 provide I{boolean} operations C{intersection}, C{difference},

8 C{reverse-difference}, C{sum} and C{union}.

9

10@note: A I{clip} is defined as a single, usually closed polygon,

11 a I{composite} is a collection of one or more I{clip}s.

12

13@see: U{Forster-Hormann-Popa<https://www.ScienceDirect.com/science/

14 article/pii/S259014861930007X>} and U{Greiner-Hormann

15 <http://www.Inf.USI.CH/hormann/papers/Greiner.1998.ECO.pdf>}.

16'''

17# make sure int/int division yields float quotient, see .basics

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

19

20 from pygeodesy.basics import isodd, isscalar, issubclassof, map2

21 from pygeodesy.constants import EPS, EPS2, INT0, _0_0, _0_5, _1_0

22 from pygeodesy.errors import ClipError, _IsnotError, _TypeError, \

23 _ValueError, _xattr, _xkwds_get

24 from pygeodesy.fmath import favg, hypot, hypot2

25# from pygeodesy.fsums import fsum1 # _MODS

26 from pygeodesy.interns import NN, _BANG_, _clip_, _clipid_, _COMMASPACE_, \

27 _composite_, _DOT_, _e_, _ELLIPSIS_, _few_, \

28 _height_, _lat_,_LatLon_, _lon_, _not_, \

29 _points_, _scalar_,_SPACE_, _too_, _X_, _x_, \

30 _B_, _d_, _R_ # PYCHOK used!

31 from pygeodesy.lazily import _ALL_DOCS, _ALL_LAZY, _ALL_MODS as _MODS

32 from pygeodesy.latlonBase import LatLonBase, \

33 LatLon2Tuple, Property_RO, property_RO

34 from pygeodesy.named import Fmt, _Named, _NotImplemented, pairs, unstr

35# from pygeodesy.namedTuples import LatLon2Tupe # from .latlonBase

36# from pygeodesy.points import boundsOf # _MODS

37# from pygeodesy.props import Property_RO, property_RO # from .latlonBase

38# from pygeodesy.streprs import Fmt, pairs, unstr # from .named

39 from pygeodesy.units import Height, HeightX

40 from pygeodesy.utily import fabs, _unrollon, _Wrap

41

42# from math import fabs # from .utily

43

44__all__ = _ALL_LAZY.booleans

45__version__ = '23.08.16'

46

47_0_EPS = EPS # near-zero, positive

48_EPS_0 = -EPS # near-zero, negative

49_1_EPS = _1_0 + EPS # near-one, over

50_EPS_1 = _1_0 - EPS # near-one, under

51_10EPS = EPS * 10 # see ._2Abs, ._10eps

52

53_alpha_ = 'alpha'

54_boolean_ = 'boolean'

55_case_ = 'case'

56_corners_ = 'corners'

57_duplicate_ = 'duplicate'

58_open_ = 'open'

59

60

61 def _Enum(txt, enum): # PYCHOK unused

62 return txt # NN(txt, _TILDE_, enum)

63

64

65 class _L(object): # Intersection labels

66 CROSSING = _Enum(_X_, 1) # C++ enum

67 CROSSING_D = _Enum(_X_ + _d_, 8)

68 CROSSINGs = (CROSSING, CROSSING_D)

69 BOUNCING = _Enum(_B_, 2)

70 BOUNCING_D = _Enum(_B_ + _d_, 9)

71 BOUNCINGs = (BOUNCING, BOUNCING_D) + CROSSINGs

72 LEFT_ON = _Enum('Lo', 3)

73 ON_ON = _Enum('oo', 5)

74 ON_LEFT = _Enum('oL', 6)

75 ON_RIGHT = _Enum('oR', 7)

76 RIGHT_ON = _Enum('Ro', 4)

77 RIGHT_LEFT_ON = (RIGHT_ON, LEFT_ON)

78 # Entry/Exit flags

79 ENTRY = _Enum(_e_, 1)

80 EXIT = _Enum(_x_, 0)

81 Toggle = {ENTRY: EXIT,

82 EXIT: ENTRY,

83 None: None}

84

85_L = _L() # PYCHOK singleton

86

87

88 class _RP(object): # RelativePositions

89 IS_Pm = _Enum('Pm', 2) # C++ enum

90 IS_Pp = _Enum('Pp', 3)

91 LEFT = _Enum('L', 0)

92 RIGHT = _Enum(_R_, 1)

93

94_RP = _RP() # PYCHOK singleton

95

96_RP2L = {(_RP.LEFT, _RP.RIGHT): _L.CROSSING,

97 (_RP.RIGHT, _RP.LEFT): _L.CROSSING,

98 (_RP.LEFT, _RP.LEFT): _L.BOUNCING,

99 (_RP.RIGHT, _RP.RIGHT): _L.BOUNCING,

100 # overlapping cases

101 (_RP.RIGHT, _RP.IS_Pp): _L.LEFT_ON,

102 (_RP.IS_Pp, _RP.RIGHT): _L.LEFT_ON,

103 (_RP.LEFT, _RP.IS_Pp): _L.RIGHT_ON,

104 (_RP.IS_Pp, _RP.LEFT): _L.RIGHT_ON,

105 (_RP.IS_Pm, _RP.IS_Pp): _L.ON_ON,

106 (_RP.IS_Pp, _RP.IS_Pm): _L.ON_ON,

107 (_RP.IS_Pm, _RP.RIGHT): _L.ON_LEFT,

108 (_RP.RIGHT, _RP.IS_Pm): _L.ON_LEFT,

109 (_RP.LEFT, _RP.IS_Pm): _L.ON_RIGHT,

110 (_RP.IS_Pm, _RP.LEFT): _L.ON_RIGHT}

111

112

113 class _LatLonBool(_Named):

114 '''(INTERNAL) Base class for L{LatLonFHP} and L{LatLonGH}.

115 '''

116 _alpha = None # point AND intersection else length

117 _checked = False # checked in phase 3 iff intersection

118 _clipid = INT0 # (polygonal) clip identifier, number

119 _dupof = None # original of a duplicate

120# _e_x_str = NN # shut up PyChecker

121 _height = Height(0) # interpolated height, usually meter

122 _linked = None # link to neighbor iff intersection

123 _next = None # link to the next vertex

124 _prev = None # link to the previous vertex

125

126 def __init__(self, lat_ll, lon=None, height=0, clipid=INT0,

127 wrap=False, name=NN):

128 '''New C{LatLon[FHP|GH]} from separate C{lat}, C{lon}, C{height}

129 and C{clipid} scalars or from a previous C{LatLon[FHP|GH]},

130 a C{Clip[FHP|GH]4Tuple} or some other C{LatLon} instance.

131

132 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude

133 (C{LatLon[FHP|GH]}, aC{Clip[FHP|GH]4Tuple}

134 or some other C{LatLon}).

135 @kwarg lon: Longitude (C{scalar}), iff B{C{lat_ll}} is

136 scalar, ignored otherwise.

137 @kwarg height: Height (C{scalar}), conventionally C{meter}.

138 @kwarg clipid: Clip identifier (C{int}).

139 @kwarg wrap: If C{True}, wrap or I{normalize} B{C{lat}}

140 and B{C{lon}} (C{bool}).

141 @kwarg name: Optional name (C{str}).

142 '''

143 if lon is None:

144 y, x = lat_ll.lat, lat_ll.lon

145 h = _xattr(lat_ll, height=height)

146 c = _xattr(lat_ll, clipid=clipid)

147 else:

148 y, x = lat_ll, lon

149 h, c = height, clipid

150 self.y, self.x = _Wrap.latlon(y, x) if wrap else (y, x)

151 # don't duplicate defaults

152 if self._height != h:

153 self._height = h

154 if self._clipid != c:

155 self._clipid = c

156 if name:

157 self.name = name

158

159 def __abs__(self):

160 return max(fabs(self.x), fabs(self.y))

161

162 def __eq__(self, other):

163 return other is self or bool(_other(self, other) and

164 other.x == self.x and

165 other.y == self.y)

166

167 def __ne__(self, other): # required for Python 2

168 return not self.__eq__(other)

169

170 def __repr__(self):

171 '''String C{repr} of this lat-/longitude.

172 '''

173 if self._prev or self._next:

174 t = _ELLIPSIS_(self._prev, self._next)

175 t = _SPACE_(self, Fmt.ANGLE(t))

176 else:

177 t = str(self)

178 return t

179

180 def __str__(self):

181 '''String C{str} of this lat-/longitude.

182 '''

183 t = (_lat_, self.lat), (_lon_, self.lon)

184 if self._height:

185 X = _X_ if self.isintersection else NN

186 t += (_height_ + X, self._height),

187 if self._clipid:

188 t += (_clipid_, self._clipid),

189 if self._alpha is not None:

190 t += (_alpha_, self._alpha),

191# if self._dupof: # recursion risk

192# t += (_dupof_, self._dupof.name),

193 t = pairs(t, prec=8, fmt=Fmt.g, ints=True)

194 t = Fmt.PAREN(_COMMASPACE_.join(t))

195 if self._linked:

196 k = _DOT_ if self._checked else _BANG_

197 t = NN(t, self._e_x_str(k)) # PYCHOK expected

198 return NN(self.name, t)

199

200 def __sub__(self, other):

201 _other(self, other)

202 return self.__class__(self.y - other.y, # classof

203 self.x - other.x)

204

205 def _2A(self, p2, p3):

206 # I{Signed} area of a triangle, I{doubled}.

207 x, y = self.x, self.y

208 return (p2.x - x) * (p3.y - y) - \

209 (p3.x - x) * (p2.y - y)

210

211 def _2Abs(self, p2, p3, eps=_10EPS):

212 # I{Unsigned} area of a triangle, I{doubled}

213 # or 0 if below the given threshold C{eps}.

214 a = fabs(self._2A(p2, p3))

215 return 0 if a < eps else a

216

217 @property_RO

218 def clipid(self):

219 '''Get the I{clipid} (C{int} or C{0}).

220 '''

221 return self._clipid

222

223 def _equi(self, llb, eps):

224 # Is this LLB I{equivalent} to B{C{llb}} within

225 # the given I{non-negative} tolerance B{C{eps}}?

226 return not (fabs(llb.lon - self.x) > eps or

227 fabs(llb.lat - self.y) > eps)

228

229 @property_RO

230 def height(self):

231 '''Get the I{height} (C{Height} or C{int}).

232 '''

233 h = self._height

234 return HeightX(h) if self.isintersection else (

235 Height(h) if h else _LatLonBool._height)

236

237 def isequalTo(self, other, eps=None):

238 '''Is this point equal to an B{C{other}} within a given,

239 I{non-negative} tolerance, ignoring C{height}?

240

241 @arg other: The other point (C{LatLon}).

242 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).

243

244 @return: C{True} if equivalent, C{False} otherwise (C{bool}).

245

246 @raise TypeError: Invalid B{C{other}}.

247 '''

248 try:

249 return self._equi(other, _eps0(eps))

250 except (AttributeError, TypeError, ValueError):

251 raise _IsnotError(_LatLon_, other=other)

252

253 @property_RO

254 def isintersection(self):

255 '''Is this an intersection? May be C{ispoint} too!

256 '''

257 return bool(self._linked)

258

259 @property_RO

260 def ispoint(self):

261 '''Is this an I{original} point? May be C{isintersection} too!

262 '''

263 return self._alpha is None

264

265 @property_RO

266 def lat(self):

267 '''Get the latitude (C{scalar}).

268 '''

269 return self.y

270

271 @property_RO

272 def latlon(self):

273 '''Get the lat- and longitude (L{LatLon2Tuple}).

274 '''

275 return LatLon2Tuple(self.y, self.x)

276

277 def _link(self, other):

278 # Make this and an other point are neighbors.

279 # assert _other(self, other)

280 self._linked = other

281 other._linked = self

282

283 @property_RO

284 def lon(self):

285 '''Get the longitude (C{scalar}).

286 '''

287 return self.x

288

289 def _toClas(self, Clas, clipid):

290 # Return this vertex as a C{Clas} instance

291 # (L{Clip[FHP|GH]4Tuple} or L{LatLon[FHP|GH]}).

292 return Clas(self.lat, self.lon, self.height, clipid)

293

294

295 class LatLonFHP(_LatLonBool):

296 '''A point or intersection in a L{BooleanFHP} clip or composite.

297 '''

298 _en_ex = None

299 _label = None

300 _2split = None # or C{._Clip}

301 _2xing = False

302

303 def __init__(self, lat_ll, *lon_h_clipid, **wrap_name):

304 '''New C{LatLonFHP} from separate C{lat}, C{lon}, C{h}eight

305 and C{clipid} scalars, or from a previous L{LatLonFHP},

306 a L{ClipFHP4Tuple} or some other C{LatLon} instance.

307

308 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude

309 (L{LatLonFHP}, C{LatLon} or L{ClipFHP4Tuple}).

310 @arg lon_h_clipid: Longitude (C{scalar}), C{h}eight and

311 C{clipid} iff B{C{lat_ll}} is scalar,

312 ignored otherwise.

313 @kwarg wrap_name: Keyword arguments C{B{wrap}=False} and

314 C{B{name}=NN}. If C{B{wrap} is True}, wrap

315 or I{normalize} the lat- and longitude

316 (C{bool}). Optional B{C{name}} (C{str}).

317 '''

318 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **wrap_name)

319

320 def __add__(self, other):

321 _other(self, other)

322 return self.__class__(self.y + other.y, self.x + other.x)

323

324 def __mod__(self, other): # cross product

325 _other(self, other)

326 return self.x * other.y - self.y * other.x

327

328 def __mul__(self, other): # dot product

329 _other(self, other)

330 return self.x * other.x + self.y * other.y

331

332 def __rmul__(self, other): # scalar product

333 if not isscalar(other):

334 raise _IsnotError(_scalar_, other=other)

335 return self.__class__(self.y * other, self.x * other)

336

337 def _e_x_str(self, t): # PYCHOK no cover

338 if self._label:

339 t = NN(self._label, t)

340 if self._en_ex:

341 t = NN(t, self._en_ex)

342 return t

343

344 @property_RO

345 def _isduplicate(self):

346 # Is this point a I{duplicate} intersection?

347 p = self._dupof

348 return bool(p and self._linked

349 and p is not self

350 and p == self

351# and p._alpha in (None, self._alpha)

352 and self._alpha in (_0_0, p._alpha))

353

354# @property_RO

355# def _isduplicated(self):

356# # Return the number of I{duplicates}?

357# d, v = 0, self

358# while v:

359# if v._dupof is self:

360# d += 1

361# v = v._next

362# if v is self:

363# break

364# return d

365

366 def isenclosedBy(self, *composites_points, **wrap):

367 '''Is this point inside one or more composites or polygons based

368 the U{winding number<https://www.ScienceDirect.com/science/

369 article/pii/S0925772101000128>}?

370

371 @arg composites_points: Composites and/or iterables of points

372 (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, L{LatLonFHP},

373 L{LatLonGH} or any C{LatLon}).

374 @kwarg wrap: If C{True}, wrap or I{normalize} and unroll the

375 C{points} (C{bool}).

376

377 @raise ValueError: Some C{points} invalid.

378

379 @see: U{Algorithm 6<https://www.ScienceDirect.com/science/

380 article/pii/S0925772101000128>}.

381 '''

382 class _Pseudo(object):

383 # Pseudo-_CompositeBase._clips tuple

384

385 @property_RO

386 def _clips(self):

387 for cp in _Cps(_CompositeFHP, composites_points,

388 LatLonFHP.isenclosedBy): # PYCHOK yield

389 for c in cp._clips:

390 yield c

391

392 return self._isinside(_Pseudo(), **wrap)

393

394 def _isinside(self, composite, *excludes, **wrap):

395 # Is this point inside a composite, excluding

396 # certain C{_Clip}s? I{winding number}?

397 x, y, i = self.x, self.y, False

398 for c in composite._clips:

399 if c not in excludes:

400 w = 0

401 for p1, p2 in c._edges2(**wrap):

402 # edge [p1,p2] must straddle y

403 if (p1.y < y) is not (p2.y < y): # or ^

404 r = p2.x > x

405 s = p2.y > p1.y

406 if p1.x < x:

407 b = r and (s is (p1._2A(p2, self) > 0))

408 else:

409 b = r or (s is (p1._2A(p2, self) > 0))

410 if b:

411 w += 1 if s else -1

412 if isodd(w):

413 i = not i

414 return i

415

416 @property_RO

417 def _prev_next2(self):

418 # Adjust 2-tuple (._prev, ._next) iff a I{duplicate} intersection

419 p, n = self, self._next

420 if self._isduplicate:

421 p = self._dupof

422 while p._isduplicate:

423 p = p._dupof

424 while n._isduplicate:

425 n = n._next

426 return p._prev, n

427

428# def _edge2(self):

429# # Return the start and end point of the

430# # edge containing I{intersection} C{v}.

431# n = p = self

432# while p.isintersection:

433# p = p._prev

434# if p is self:

435# break

436# while n.isintersection:

437# n = n._next

438# if n is self:

439# break

440# # assert p == self or not p._2Abs(self, n)

441# return p, n

442

443 def _RPoracle(self, p1, p2, p3):

444 # Relative Position oracle

445 if p1._linked is self: # or p1._linked2(self):

446 T = _RP.IS_Pm

447 elif p3._linked is self: # or p3._linked2(self):

448 T = _RP.IS_Pp

449 elif p1._2A(p2, p3) > 0: # left turn

450 T = _RP.LEFT if self._2A(p1, p2) > 0 and \

451 self._2A(p2, p3) > 0 else \

452 _RP.RIGHT # PYCHOK indent

453 else: # right turn (or straight)

454 T = _RP.RIGHT if self._2A(p1, p2) < 0 and \

455 self._2A(p2, p3) < 0 else \

456 _RP.LEFT # PYCHOK indent

457 return T

458

459

460 class LatLonGH(_LatLonBool):

461 '''A point or intersection in a L{BooleanGH} clip or composite.

462 '''

463 _entry = None # entry or exit iff intersection

464

465 def __init__(self, lat_ll, *lon_h_clipid, **wrap_name):

466 '''New C{LatLonGH} from separate C{lat}, C{lon}, C{h}eight

467 and C{clipid} scalars, or from a previous L{LatLonGH},

468 L{ClipGH4Tuple} or some other C{LatLon} instance.

469

470 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude

471 (L{LatLonGH}, C{LatLon} or L{ClipGH4Tuple}).

472 @arg lon_h_clipid: Longitude (C{scalar}), C{h}eight and

473 C{clipid} iff B{C{lat_ll}} is scalar,

474 ignored otherwise.

475 @kwarg wrap_name: Keyword arguments C{B{wrap}=False} and

476 C{B{name}=NN}. If C{B{wrap} is True}, wrap

477 or I{normalize} the lat- and longitude

478 (C{bool}). Optional B{C{name}} (C{str}).

479 '''

480 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **wrap_name)

481

482 def _check(self):

483 # Check-mark this vertex and its link.

484 self._checked = True

485 k = self._linked

486 if k and not k._checked:

487 k._checked = True

488

489 def _e_x_str(self, t): # PYCHOK no cover

490 return t if self._entry is None else NN(t,

491 (_e_ if self._entry else _x_))

492

493 def isenclosedBy(self, *composites_points, **wrap):

494 '''Is this point inside one or more composites or polygons based

495 on the U{even-odd-rule<https://www.ScienceDirect.com/science/

496 article/pii/S0925772101000128>}?

497

498 @arg composites_points: Composites and/or iterables of points

499 (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, L{LatLonFHP},

500 L{LatLonGH} or any C{LatLon}).

501 @kwarg wrap: If C{True}, wrap or I{normalize} and unroll the

502 C{points} (C{bool}).

503

504 @raise ValueError: Some B{C{points}} invalid.

505 '''

506 class _Pseudo(object):

507 # Pseudo-_CompositeBase._edges3 method

508

509 def _edges3(self, **kwds):

510 for cp in _Cps(_CompositeGH, composites_points,

511 LatLonGH.isenclosedBy): # PYCHOK yield

512 for e in cp._edges3(**kwds):

513 yield e

514

515 return self._isinside(_Pseudo(), **wrap)

516

517 def _isinside(self, composite, *bottom_top, **wrap):

518 # Is this vertex inside the composite? I{even-odd rule}?

519

520 def _x(y, p1, p2):

521 # return C{x} at given C{y} on edge [p1,p2]

522 return (y - p1.y) / (p2.y - p1.y) * (p2.x - p1.x)

523

524 # The I{even-odd} rule counts the number of edges

525 # intersecting a ray emitted from this point to

526 # east-bound infinity. When I{odd} this point lies

527 # inside, if I{even} outside.

528 y, i = self.y, False

529 if not (bottom_top and _outside(y, y, *bottom_top)):

530 x = self.x

531 for p1, p2, _ in composite._edges3(**wrap):

532 if (p1.y < y) is not (p2.y < y): # or ^

533 r = p2.x > x

534 if p1.x < x:

535 b = r and (_x(y, p1, p2) > x)

536 else:

537 b = r or (_x(y, p1, p2) > x)

538 if b:

539 i = not i

540 return i

541

542

543 class _Clip(_Named):

544 '''(INTERNAL) A I{doubly-linked} list representing a I{closed}

545 polygon of L{LatLonFHP} or L{LatLonGH} points, duplicates

546 and intersections with other clips.

547 '''

548 _composite = None

549 _dups = 0

550 _first = None

551 _id = 0

552 _identical = False

553 _noInters = False

554 _last = None

555 _LL = None

556 _len = 0

557 _pushback = False

558

559 def __init__(self, composite, clipid=INT0):

560 '''(INTERNAL) New C{_Clip}.

561 '''

562 # assert isinstance(composite, _CompositeBase)

563 if clipid in composite._clipids:

564 raise ClipError(clipid=clipid, txt=_duplicate_)

565 self._composite = composite

566 self._id = clipid

567 self._LL = composite._LL

568 composite._clips = composite._clips + (self,)

569

570 def __contains__(self, point): # PYCHOK no cover

571 '''Is the B{C{point}} in this clip?

572 '''

573 for v in self:

574 if v is point: # or ==?

575 return True

576 return False

577

578 def __eq__(self, other):

579 '''Is this clip I{equivalent} to an B{C{other}} clip,

580 do both have the same C{len}, the same points, in

581 the same order, possibly rotated?

582 '''

583 return self._equi(_other(self, other), 0)

584

585 def __ge__(self, other):

586 '''See method C{__lt__}.

587 '''

588 return not self.__lt__(other)

589

590 def __gt__(self, other):

591 '''Is this clip C{"above"} an B{C{other}} clip,

592 located or stretched farther North or East?

593 '''

594 return self._bltr4 > _other(self, other)._bltr4

595

596 def __hash__(self): # PYCHOK no over

597 return hash(self._bltr4)

598

599 def __iter__(self):

600 '''Yield the points, duplicates and intersections.

601 '''

602 v = f = self._first

603 while v:

604 yield v

605 v = v._next

606 if v is f:

607 break

608

609 def __le__(self, other):

610 '''See method C{__gt__}.

611 '''

612 return not self.__gt__(other)

613

614 def __len__(self):

615 '''Return the number of points, duplicates and

616 intersections in this clip.

617 '''

618 return self._len

619

620 def __lt__(self, other):

621 '''Is this clip C{"below"} an B{C{other}} clip,

622 located or stretched farther South or West?

623 '''

624 return self._bltr4 < _other(self, other)._bltr4

625

626 def __ne__(self, other): # required for Python 2

627 '''See method C{__eq__}.

628 '''

629 return not self.__eq__(other)

630

631 _all = __iter__

632

633 @property_RO

634 def _all_ON_ON(self):

635 # Check whether all vertices are ON_ON.

636 L_ON_ON = _L.ON_ON

637 return all(v._label is L_ON_ON for v in self)

638

639 def _append(self, y_v, *x_h_clipid):

640 # Append a point given as C{y}, C{x}, C{h}eight and

641 # C{clipid} args or as a C{LatLon[FHP|GH]}.

642 self._last = v = self._LL(y_v, *x_h_clipid) if x_h_clipid else y_v

643 self._len += 1

644 # assert v._clipid == self._id

645

646 v._next = n = self._first

647 if n is None: # set ._first

648 self._first = p = n = v

649 else: # insert before ._first

650 v._prev = p = n._prev

651 p._next = n._prev = v

652 return v

653

654# def _appendedup(self, v, clipid=0):

655# # Like C{._append}, but only append C{v} if not a

656# # duplicate of the one previously append[edup]'ed.

657# y, x, p = v.y, v.x, self._last

658# if p is None or y != p.y or x != p.x or clipid != p._clipid:

659# p = self._append(y, x, v._height, clipid)

660# if v._linked:

661# p._linked = True # to force errors

662# return p

663

664 @Property_RO

665 def _bltr4(self):

666 # Get the bounds as 4-tuple C{(bottom, left, top, right)}.

667 return map2(float, _MODS.points.boundsOf(self, wrap=False))

668

669 def _bltr4eps(self, eps):

670 # Get the ._bltr4 bounds tuple, oversized.

671 if eps > 0: # > EPS

672 yb, xl, yt, xr = self._bltr4

673 yb, yt = _low_high_eps2(yb, yt, eps)

674 xl, xr = _low_high_eps2(xl, xr, eps)

675 t = yb, xl, yt, xr

676 else:

677 t = self._bltr4

678 return t

679

680 def _closed(self, raiser): # PYCHOK unused

681 # End a clip, un-close it and check C{len}.

682 p, f = self._last, self._first

683 if f and f._prev is p and p is not f and \

684 p._next is f and p == f: # PYCHOK no cover

685 # un-close the clip

686 f._prev = p = p._prev

687 p._next = f

688 self._len -= 1

689# elif f and raiser:

690# raise self._OpenClipError(p, f)

691 if len(self) < 3:

692 raise self._Error(_too_(_few_))

693

694 def _dup(self, q):

695 # Duplicate a point (or intersection) as intersection.

696 v = self._insert(q.y, q.x, q)

697 v._alpha = q._alpha or _0_0 # _0_0 replaces None

698 v._dupof = q._dupof or q

699 # assert v._prev is q

700 # assert q._next is v

701 return v

702

703 def _edges2(self, wrap=False, **unused):

704 # Yield each I{original} edge as a 2-tuple

705 # (p1, p2), a pair of C{LatLon[FHP|GH])}s.

706 p1 = p = f = self._first

707 while p:

708 p2 = p = p._next

709 if p.ispoint:

710 if wrap and p is not f:

711 p2 = _unrollon(p1, p)

712 yield p1, p2

713 p1 = p2

714 if p is f:

715 break

716

717 def _equi(self, clip, eps):

718 # Is this clip I{equivalent} to B{C{clip}} within

719 # the given I{non-negative} tolerance B{C{eps}}?

720 r, f = len(self), self._first

721 if f and r == len(clip) and self._bltr4eps(eps) \

722 == clip._bltr4eps(eps):

723 _equi = _LatLonBool._equi

724 for v in clip:

725 if _equi(f, v, eps):

726 s, n = f, v

727 for _ in range(r):

728 s, n = s._next, n._next

729 if not _equi(s, n, eps):

730 break # next v

731 else: # equivalent

732 return True

733 return False

734

735 def _Error(self, txt): # PYCHOK no cover

736 # Build a C{ClipError} instance

737 kwds = dict(len=len(self), txt=txt)

738 if self._dups:

739 kwds.update(dups=self._dups)

740 cp = self._composite

741 if self._id:

742 try:

743 i = cp._clips.index(self)

744 if i != self._id:

745 kwds[_clip_] = i

746 except ValueError:

747 pass

748 kwds[_clipid_] = self._id

749 return ClipError(cp._kind, cp.name, **kwds)

750

751 def _index(self, clips, eps):

752 # see _CompositeBase._equi

753 for i, c in enumerate(clips):

754 if c._equi(self, eps):

755 return i

756 raise ValueError(NN) # like clips.index(self)

757

758 def _insert(self, y, x, start, *end_alpha):

759 # insertVertex between points C{start} and

760 # C{end}, ordered by C{alpha} iff given.

761 v = self._LL(y, x, start._height, start._clipid)

762 n = start._next

763 if end_alpha:

764 end, alpha = end_alpha

765 v._alpha = alpha

766 v._height = favg(v._height, end._height, f=alpha)

767 # assert start is not end

768 while n is not end and n._alpha < alpha:

769 n = n._next

770 v._next = n

771 v._prev = p = n._prev

772 p._next = n._prev = v

773 self._len += 1

774# _Clip._bltr4._update(self)

775# _Clip._ishole._update(self)

776 return v

777

778 def _intersection(self, unused, q, *p1_p2_alpha):

779 # insert an intersection or make a point both

780 if p1_p2_alpha: # intersection on edge

781 v = self._insert(q.y, q.x, *p1_p2_alpha)

782 else: # intersection at point

783 v = q

784 # assert not v._linked

785 # assert v._alpha is None

786 return v

787

788 def _intersections(self):

789 # Yield all intersections, some may be points too.

790 for v in self:

791 if v.isintersection:

792 yield v

793

794 @Property_RO

795 def _ishole(self): # PYCHOK no cover

796 # Is this clip a hole inside its composite?

797 v = self._first

798 return v._isinside(self._composite, self) if v else False

799

800 @property_RO

801 def _nodups(self):

802 # Yield all non-duplicates.

803 for v in self:

804 if not v._dupof:

805 yield v

806

807 def _noXings(self, Union):

808 # Are all intersections non-CROSSINGs, -BOUNCINGs?

809 Ls = _L.BOUNCINGs if Union else _L.CROSSINGs

810 return all(v._label not in Ls for v in self._intersections())

811

812 def _OpenClipError(self, s, e): # PYCHOK no cover

813 # Return a C{CloseError} instance

814 t = NN(s, _ELLIPSIS_(_COMMASPACE_, e))

815 return self._Error(_SPACE_(_open_, t))

816

817 def _point2(self, insert):

818 # getNonIntersectionPoint and -Vertex

819 if not (insert and self._noInters):

820 for p in self._points(may_be=False): # not p._isduplicated?

821 return p, None

822 for n in self._intersections():

823 p, _ = n._prev_next2

824 k = p._linked

825 if k:

826 if n._linked not in k._prev_next2:

827 # create a pseudo-point

828 k = _0_5 * (p + n)

829 if insert:

830 k = self._insert(k.y, k.x, n._prev)

831 r = k # to remove later

832 else: # no ._prev, ._next

833 k._clipid = n._clipid

834 r = None

835 return k, r

836 return None, None

837

838 def _points(self, may_be=True):

839 # Yield all points I{in original order}, which may be intersections too.

840 for v in self:

841 if v.ispoint and (may_be or not v.isintersection):

842 yield v

843

844 def _remove2(self, v):

845 # Remove vertex C{v}.

846 # assert not v._isduplicated

847 if len(self) > 1:

848 p = v._prev

849 p._next = n = v._next

850 n._prev = p

851 if self._first is v:

852 self._first = n

853 if self._last is v:

854 self._last = p

855 self._len -= 1

856 else:

857 n = self._last = \

858 p = self._first = None

859 self._len = 0

860 return p, n

861

862 def _update_all(self): # PYCHOK no cover

863 # Zap the I{cached} properties.

864 _Clip._bltr4._update( self)

865 _Clip._ishole._update(self)

866 return self # for _special_identicals

867

868 def _Xings(self):

869 # Yield all I{un-checked} CROSSING intersections.

870 CROSSING = _L.CROSSING

871 for v in self._intersections():

872 if v._label is CROSSING and not v._checked:

873 yield v

874

875

876 class _CompositeBase(_Named):

877 '''(INTERNAL) Base class for L{BooleanFHP} and L{BooleanGH}

878 (C{_CompositeFHP} and C{_CompositeGH}).

879 '''

880 _clips = () # tuple of C{_Clips}

881 _eps = EPS # null edges

882 _kind = _corners_

883 _LL = _LatLonBool # shut up PyChecker

884 _raiser = False

885 _xtend = False

886

887 def __init__(self, lls, name=NN, kind=NN, eps=EPS):

888 '''(INTERNAL) See L{BooleanFHP} and L{BooleanGH}.

889 '''

890 n = name or _xattr(lls, name=NN)

891 if n:

892 self.name = n

893 if kind:

894 self._kind = kind

895 if self._eps < eps:

896 self._eps = eps

897

898 c = _Clip(self)

899 lp = None

900 for ll in lls:

901 ll = self._LL(ll)

902 if lp is None:

903 c._id = ll._clipid # keep clipid

904 lp = c._append(ll)

905 elif ll._clipid != lp._clipid: # new clip

906 c._closed(self.raiser)

907 c = _Clip(self, ll._clipid)

908 lp = c._append(ll)

909 elif abs(ll - lp) > eps: # PYCHOK lp

910 lp = c._append(ll)

911 else:

912 c._dups += 1

913 c._closed(self.raiser)

914

915 def __contains__(self, point): # PYCHOK no cover

916 '''Is the B{C{point}} in one of the clips?

917 '''

918 for c in self._clips:

919 if point in c:

920 return True

921 return False

922

923 def __eq__(self, other):

924 '''Is this I{composite} equivalent to an B{C{other}}, i.e.

925 do both contain I{equivalent} clips in the same or in a

926 different order? Two clips are considered I{equivalent}

927 if both have the same points etc. in the same order,

928 possibly rotated.

929 '''

930 return self._equi(_other(self, other), 0)

931

932 def __iter__(self):

933 '''Yield all points, duplicates and intersections.

934 '''

935 for c in self._clips:

936 for v in c:

937 yield v

938

939 def __ne__(self, other): # required for Python 2

940 '''See method C{__eq__}.

941 '''

942 return not self.__eq__(other)

943

944 def __len__(self):

945 '''Return the I{total} number of points.

946 '''

947 return sum(map(len, self._clips)) if self._clips else 0

948

949 def __repr__(self):

950 '''String C{repr} of this composite.

951 '''

952 c = len(self._clips)

953 c = Fmt.SQUARE(c) if c > 1 else NN

954 n = Fmt.SQUARE(len(self))

955 t = Fmt.PAREN(self) # XXX not unstr

956 return NN(self.__class__.__name__, c, n, t)

957

958 def __str__(self):

959 '''String C{str} of this composite.

960 '''

961 return _COMMASPACE_.join(map(str, self))

962

963 @property_RO

964 def _bottom_top_eps2(self):

965 # Get the bottom and top C{y} bounds, oversized.

966 return _min_max_eps2(min(v.y for v in self),

967 max(v.y for v in self))

968

969 def _class(self, corners, kwds, **dflts):

970 # Return a new instance

971 _g = kwds.get

972 kwds = dict((n, _g(n, v)) for n, v in dflts.items())

973 return self.__class__(corners or (), **kwds)

974

975 @property_RO

976 def _clipids(self): # PYCHOK no cover

977 for c in self._clips:

978 yield c._id

979

980 def clipids(self):

981 '''Return a tuple with all C{clipid}s, I{ordered}.

982 '''

983 return tuple(self._clipids)

984

985# def _clipidups(self, other):

986# # Number common C{clipid}s between this and an C{other} composite

987# return len(set(self._clipids).intersection(set(other._clipids)))

988

989 def _edges3(self, **raiser_wrap):

990 # Yield each I{original} edge as a 3-tuple

991 # C{(LatLon[FHP|GH], LatLon[FHP|GH], _Clip)}.

992 for c in self._clips:

993 for p1, p2 in c._edges2(**raiser_wrap):

994 yield p1, p2, c

995

996 def _encloses(self, lat, lon, **wrap):

997 # see function .points.isenclosedBy

998 return self._LL(lat, lon).isenclosedBy(self, **wrap)

999

1000 @property

1001 def eps(self):

1002 '''Get the null edges tolerance (C{degrees}, usually).

1003 '''

1004 return self._eps

1005

1006 @eps.setter # PYCHOK setter!

1007 def eps(self, eps):

1008 '''Set the null edges tolerance (C{degrees}, usually).

1009 '''

1010 self._eps = eps

1011

1012 def _10eps(self, **eps):

1013 # Get eps for _LatLonBool._2Abs

1014 e = _xkwds_get(eps, eps=self._eps)

1015 if e != EPS:

1016 e *= _10EPS / EPS

1017 else:

1018 e = _10EPS

1019 return e

1020

1021 def _equi(self, other, eps):

1022 # Is this composite I{equivalent} to an B{C{other}} within

1023 # the given, I{non-negative} tolerance B{C{eps}}?

1024 cs, co = self._clips, other._clips

1025 if cs and len(cs) == len(co):

1026 if eps > 0:

1027 _index = _Clip._index

1028 else:

1029 def _index(c, cs, unused):

1030 return cs.index(c)

1031 try:

1032 cs = list(sorted(cs))

1033 for c in sorted(co):

1034 cs.pop(_index(c, cs, eps))

1035 except ValueError: # from ._index

1036 pass

1037 return False if cs else True

1038 else: # both null?

1039 return False if cs or co else True

1040

1041 def _intersections(self):

1042 # Yield all intersections.

1043 for c in self._clips:

1044 for v in c._intersections():

1045 yield v

1046

1047 def isequalTo(self, other, eps=None):

1048 '''Is this boolean/composite equal to an B{C{other}} within

1049 a given, I{non-negative} tolerance?

1050

1051 @arg other: The other boolean/composite (C{Boolean[FHP|GB]}).

1052 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).

1053

1054 @return: C{True} if equivalent, C{False} otherwise (C{bool}).

1055

1056 @raise TypeError: Invalid B{C{other}}.

1057

1058 @see: Method C{__eq__}.

1059 '''

1060 if isinstance(other, _CompositeBase):

1061 return self._equi(other, _eps0(eps))

1062 raise _IsnotError(_boolean_, _composite_, other=other)

1063

1064 def _kwds(self, op, **more):

1065 # Get all keyword arguments as C{dict}.

1066 kwds = dict(raiser=self.raiser, eps=self.eps,

1067 name=self.name or op.__name__)

1068 kwds.update(more)

1069 return kwds

1070

1071 @property_RO

1072 def _left_right_eps2(self):

1073 # Get the left and right C{x} bounds, oversized.

1074 return _min_max_eps2(min(v.x for v in self),

1075 max(v.x for v in self))

1076

1077 def _points(self, may_be=True): # PYCHOK no cover

1078 # Yield all I{original} points, which may be intersections too.

1079 for c in self._clips:

1080 for v in c._points(may_be=may_be):

1081 yield v

1082

1083 @property

1084 def raiser(self):

1085 '''Get the option to throw L{ClipError} exceptions (C{bool}).

1086 '''

1087 return self._raiser

1088

1089 @raiser.setter # PYCHOK setter!

1090 def raiser(self, throw):

1091 '''Set the option to throw L{ClipError} exceptions (C{bool}).

1092 '''

1093 self._raiser = bool(throw)

1094

1095 def _results(self, _presults, Clas, closed=False, inull=False, **eps):

1096 # Yield the dedup'd results, as L{ClipFHP4Tuple}s

1097 C = self._LL if Clas is None else Clas

1098 e = self._10eps(**eps)

1099 for clipid, ns in enumerate(_presults):

1100 f = p = v = None

1101 for n in ns:

1102 if f is None:

1103 yield n._toClas(C, clipid)

1104 f = p = n

1105 elif v is None:

1106 v = n # got f, p, v

1107 elif inull or p._2Abs(v, n, eps=e):

1108 yield v._toClas(C, clipid)

1109 p, v = v, n

1110 else: # null, colinear, ... skipped

1111 v = n

1112 if v and (inull or p._2Abs(v, f, eps=e)):

1113 yield v._toClas(C, clipid)

1114 p = v

1115 if f and p != f and closed: # close clip

1116 yield f._toClas(C, clipid)

1117

1118 def _sum(self, other, op):

1119 # Combine this and an C{other} composite

1120 LL = self._LL

1121 sp = self.copy(name=self.name or op.__name__)

1122 sp._clips, sid = (), INT0 # new clips

1123 for cp in (self, other):

1124 for c in cp._clips:

1125 _ap = _Clip(sp, sid)._append

1126 for v in c._nodups:

1127 _ap(LL(v.y, v.x, v.height, sid))

1128 sid += 1

1129 return sp

1130

1131 def _sum1(self, _a_p, *args, **kwds): # in .karney, .points

1132 # Sum the area or perimeter of all clips

1133 return _MODS.fsums.fsum1((_a_p(c, *args, **kwds) for c in self._clips), floats=True)

1134

1135 def _sum2(self, LL, _a_p, *args, **kwds): # in .sphericalNvector, -Trigonometry

1136 # Sum the area or perimeter of all clips

1137

1138 def _lls(clip): # convert clip to LLs

1139 _LL = LL

1140 for v in clip:

1141 yield _LL(v.lat, v.lon) # datum=Sphere

1142

1143 return _MODS.fsums.fsum1((_a_p(_lls(c), *args, **kwds) for c in self._clips), floats=True)

1144

1145 def toLatLon(self, LatLon=None, closed=False, **LatLon_kwds):

1146 '''Yield all (non-duplicate) points and intersections

1147 as an instance of B{C{LatLon}}.

1148

1149 @kwarg LatLon: Class to use (C{LatLon}) or if C{None},

1150 L{LatLonFHP} or L{LatLonGH}.

1151 @kwarg closed: If C{True}, close each clip (C{bool}).

1152 @kwarg LatLon_kwds: Optional, additional B{C{LatLon}}

1153 keyword arguments, ignore if

1154 C{B{LatLon} is None}.

1155

1156 @raise TypeError: Invalid B{C{LatLon}}.

1157

1158 @note: For intersections, C{height} is an instance

1159 of L{HeightX}, otherwise of L{Height}.

1160 '''

1161 if LatLon is None:

1162 LL, kwds = self._LL, {}

1163 elif issubclassof(LatLon, _LatLonBool, LatLonBase):

1164 LL, kwds = LatLon, LatLon_kwds

1165 else:

1166 raise _TypeError(LatLon=LatLon)

1167

1168 for c in self._clips:

1169 lf, cid = None, c._id

1170 for v in c._nodups:

1171 ll = LL(v.y, v.x, **kwds)

1172 ll._height = v.height

1173 if ll._clipid != cid:

1174 ll._clipid = cid

1175 yield ll

1176 if lf is None:

1177 lf = ll

1178 if closed and lf:

1179 yield lf

1180

1181

1182 class _CompositeFHP(_CompositeBase):

1183 '''(INTERNAL) A list of clips representing a I{composite}

1184 of L{LatLonFHP} points, duplicates and intersections

1185 with an other I{composite}.

1186 '''

1187 _LL = LatLonFHP

1188 _Union = False

1189

1190 def __init__(self, lls, raiser=False, **name_kind_eps):

1191 # New L{_CompositeFHP}.

1192 if raiser:

1193 self._raiser = True

1194 _CompositeBase.__init__(self, lls, **name_kind_eps)

1195

1196 def _classify(self):

1197 # 2) Classify intersection chains.

1198 L = _L

1199 for v in self._intersections():

1200 n, b = v, v._label

1201 if b in L.RIGHT_LEFT_ON: # next chain

1202 while True:

1203 n._label = None # n.__dict__.pop('_label')

1204 n = n._next

1205 if n is v or n._label is not L.ON_ON: # n._label and ...

1206 break

1207 a = L.LEFT_ON if n._label is L.ON_LEFT else L.RIGHT_ON

1208 v._label = n._label = L.BOUNCING_D if a is b else L.CROSSING_D

1209

1210 # 3) Copy labels

1211 for v in self._intersections():

1212 v._linked._label = v._label

1213

1214 def _clip(self, corners, Union=False, Clas=None,

1215 **closed_inull_raiser_eps):

1216 # Clip this composite with another one, C{corners},

1217 # using Foster-Hormann-Popa's algorithm.

1218 P = self

1219 Q = self._class(corners, closed_inull_raiser_eps,

1220 eps=P._eps, raiser=False)

1221 if Union:

1222 P._Union = Q._Union = True

1223

1224 bt = Q._bottom_top_eps2

1225 lr = Q._left_right_eps2

1226 # compute and insert intersections

1227 for p1, p2, Pc in P._edges3(**closed_inull_raiser_eps):

1228 if not (_outside(p1.x, p2.x, *lr) or

1229 _outside(p1.y, p2.y, *bt)):

1230 e = _EdgeFHP(p1, p2)

1231 if e._dp2 > EPS2: # non-null edge

1232 for q1, q2, Qc in Q._edges3(**closed_inull_raiser_eps):

1233 for T, p, q in e._intersect3(q1, q2):

1234 p = Pc._intersection(T, *p)

1235 q = Qc._intersection(T, *q)

1236 # assert not p._linked

1237 # assert not q._linked

1238 p._link(q)

1239

1240 # label and classify intersections

1241 P._labelize()

1242 P._classify()

1243

1244 # check for special cases

1245 P._special_cases(Q)

1246 Q._special_cases(P)

1247 # handle identicals

1248 P._special_identicals(Q)

1249

1250 # set Entry/Exit flags

1251 P._set_entry_exits(Q)

1252 Q._set_entry_exits(P)

1253

1254 # handle splits and crossings

1255 P._splits_xings(Q)

1256

1257 # yield the results

1258 return P._results(P._presults(Q), Clas, **closed_inull_raiser_eps)

1259

1260 @property_RO

1261 def _identicals(self):

1262 # Yield all clips marked C{._identical}.

1263 for c in self._clips:

1264 if c._identical:

1265 yield c

1266

1267 def _labelize(self):

1268 # 1) Intersections classification

1269 for p in self._intersections():

1270 q = p._linked

1271 # determine local configuration at this intersection

1272 # and positions of Q- and Q+ relative to (P-, I, P+)

1273 p1, p3 = p._prev_next2

1274 q1, q3 = q._prev_next2

1275 t = (q1._RPoracle(p1, p, p3),

1276 q3._RPoracle(p1, p, p3))

1277 # check intersecting and overlapping cases

1278 p._label = _RP2L.get(t, None)

1279

1280 def _presults(self, other):

1281 # Yield the result clips, each as a generator

1282 # of the L{_LatLonFHP}s in that clip

1283 for cp in (self, other):

1284 for c in cp._clips:

1285 if c._pushback:

1286 yield c._all()

1287 for c in self._clips:

1288 for X in c._Xings():

1289 yield self._resultX(X)

1290

1291 def _resultX(self, X):

1292 # Yield the results from CROSSING C{X}.

1293 L, U, v = _L, self._Union, X

1294 while v:

1295 v._checked = True

1296 r = v # in P or Q

1297 s = L.Toggle[v._en_ex]

1298 e = (s is L.EXIT) ^ U

1299 while True:

1300 v = v._next if e else v._prev

1301 yield v

1302 v._checked = True

1303 if v._en_ex is s or v is X:

1304 break

1305 if v is r: # full circle

1306 raise ClipError(full_circle=v, clipid=v._clipid)

1307 if v is not X:

1308 v = v._linked

1309 if v is X:

1310 break

1311

1312 def _set_entry_exits(self, other): # MCCABE 14

1313 # 4) Set entry/exit flags

1314 L, U = _L, self._Union

1315 for c in self._clips:

1316 n, k = c._point2(True)

1317 if n:

1318 f = n

1319 s = L.EXIT if n._isinside(other) else L.ENTRY

1320 t = L.EXIT # first_chain_vertex = True

1321 while True:

1322 if n.isintersection:

1323 b = n._label

1324 if b is L.CROSSING:

1325 n._en_ex = s

1326 s = L.Toggle[s]

1327 elif b is L.BOUNCING and ((s is L.EXIT) ^ U):

1328 n._2split = c # see ._splits_xings

1329 elif b is L.CROSSING_D:

1330 n._en_ex = s

1331 if (s is t) ^ U:

1332 n._label = L.CROSSING

1333 t = L.Toggle[t]

1334 if t is L.EXIT: # first_chain_vertex == True

1335 s = L.Toggle[s]

1336 elif b is L.BOUNCING_D:

1337 n._en_ex = s

1338 if (s is t) ^ U:

1339 n._2xing = True # see ._splits_xings

1340 s = L.Toggle[s]

1341 t = L.Toggle[t]

1342 n = n._next # _, n = n._prev_next2

1343 if n is f:

1344 break # PYCHOK attr?

1345 if k:

1346 c._remove2(k)

1347

1348 def _special_cases(self, other):

1349 # 3.5) Check special cases

1350 U = self._Union

1351 for c in self._clips:

1352 if c._noXings(U):

1353 c._noInters = True

1354 if c._all_ON_ON:

1355 c._identical = True

1356 else:

1357 p, _ = c._point2(False)

1358 if p and (p._isinside(other) ^ U):

1359 c._pushback = True

1360

1361 def _special_identicals(self, other):

1362 # 3.5) Handle identicals

1363 _u = _Clip._update_all

1364 cds = dict((c._id, _u(c)) for c in other._identicals)

1365 # assert len(cds) == len(other._identicals)

1366 if cds: # PYCHOK no cover

1367 for c in self._identicals:

1368 c._update_all()

1369 for v in c._intersections():

1370 d = cds.get(v._linked._clipid, None)

1371 if d and d._ishole is c._ishole:

1372 c._pushback = True

1373 break # next c

1374

1375 @property_RO

1376 def _2splits(self):

1377 # Yield all intersections marked C{._2split}

1378 for p in self._intersections():

1379 if p._2split:

1380 # assert isinstance(p._2split, _Clip)

1381 yield p

1382

1383 def _splits_xings(self, other): # MCCABE 15

1384 # 5) Handle split pairs and 6) crossing candidates

1385

1386 def _2A_dup2(p, P): # PYCHOK unused

1387 p1, p2 = p._prev_next2

1388 ap = p1._2A(p, p2)

1389 Pc = p._2split

1390 # assert Pc in P._clips

1391 # assert p in Pc

1392 return ap, Pc._dup(p)

1393

1394 def _links2(ps, qs): # PYCHOK P unused?

1395 # Yield each link as a 2-tuple(p, q)

1396 id_qs = set(map(id, qs))

1397 if id_qs:

1398 for p in ps:

1399 q = p._linked

1400 if q and id(q) in id_qs:

1401 yield p, q

1402

1403 L = _L

1404 E = L.ENTRY if self._Union else L.EXIT

1405 X = L.Toggle[E]

1406 for p, q in _links2(self._2splits, other._2splits):

1407 ap, pp = _2A_dup2(p, self)

1408 aq, qq = _2A_dup2(q, other)

1409 if (ap * aq) > 0: # PYCHOK no cover

1410 p._link(qq) # overwrites ...

1411 q._link(pp) # ... p-q link

1412 else:

1413 pp._link(qq)

1414 p._en_ex = q._en_ex = E

1415 pp._en_ex = qq._en_ex = X

1416 p._label = pp._label = \

1417 q._label = qq._label = L.CROSSING

1418

1419 for p, q in _links2(self._2xings, other._2xings):

1420 p._label = q._label = L.CROSSING

1421

1422 @property_RO

1423 def _2xings(self):

1424 # Yield all intersections marked C{._2xing}

1425 for p in self._intersections():

1426 if p._2xing:

1427 yield p

1428

1429

1430 class _CompositeGH(_CompositeBase):

1431 '''(INTERNAL) A list of clips representing a I{composite}

1432 of L{LatLonGH} points, duplicates and intersections

1433 with an other I{composite}.

1434 '''

1435 _LL = LatLonGH

1436 _xtend = False

1437

1438 def __init__(self, lls, raiser=False, xtend=False, **name_kind_eps):

1439 # New L{_CompositeGH}.

1440 if xtend:

1441 self._xtend = True

1442 elif raiser:

1443 self._raiser = True

1444 _CompositeBase.__init__(self, lls, **name_kind_eps)

1445

1446 def _clip(self, corners, s_entry, c_entry, Clas=None,

1447 **closed_inull_raiser_xtend_eps):

1448 # Clip this polygon with another one, C{corners}.

1449

1450 # Core of Greiner/Hormann's algorithm, enhanced U{Correia's

1451 # <https://GitHub.com/helderco/univ-polyclip>} implementation***

1452 # and extended to optionally handle so-called "degenerate cases"

1453 S = self

1454 C = self._class(corners, closed_inull_raiser_xtend_eps,

1455 raiser=False, xtend=False)

1456 bt = C._bottom_top_eps2

1457 lr = C._left_right_eps2

1458 # 1. find intersections

1459 for s1, s2, Sc in S._edges3(**closed_inull_raiser_xtend_eps):

1460 if not (_outside(s1.x, s2.x, *lr) or

1461 _outside(s1.y, s2.y, *bt)):

1462 e = _EdgeGH(s1, s2, **closed_inull_raiser_xtend_eps)

1463 if e._hypot2 > EPS2: # non-null edge

1464 for c1, c2, Cc in C._edges3(**closed_inull_raiser_xtend_eps):

1465 for y, x, sa, ca in e._intersect4(c1, c2):

1466 s = Sc._insert(y, x, s1, s2, sa)

1467 c = Cc._insert(y, x, c1, c2, ca)

1468 s._link(c)

1469

1470 # 2. identify entry/exit intersections

1471 if S._first:

1472 s_entry ^= S._first._isinside(C, *bt)

1473 for v in S._intersections():

1474 v._entry = s_entry = not s_entry

1475

1476 if C._first:

1477 c_entry ^= C._first._isinside(S)

1478 for v in C._intersections():

1479 v._entry = c_entry = not c_entry

1480

1481 # 3. yield the result(s)

1482 return S._results(S._presults(), Clas, **closed_inull_raiser_xtend_eps)

1483

1484 @property_RO

1485 def _first(self):

1486 # Get the very first vertex of the first clip

1487 for v in self:

1488 return v

1489 return None # PYCHOK no cover

1490

1491 def _kwds(self, op, **more):

1492 # Get the kwds C{dict}.

1493 return _CompositeBase._kwds(self, op, xtend=self.xtend, **more)

1494

1495 def _presults(self):

1496 # Yield the unchecked intersection(s).

1497 for c in self._clips:

1498 for v in c._intersections():

1499 if not v._checked:

1500 yield self._resultU(v)

1501

1502 def _resultU(self, v):

1503 # Yield the result from an un-checked intersection.

1504 while v and not v._checked:

1505 v._check()

1506 yield v

1507 r = v

1508 e = v._entry

1509 while True:

1510 v = v._next if e else v._prev

1511 yield v

1512 if v._linked:

1513 break

1514 if v is r:

1515 raise ClipError(full_circle=v, clipid=v._clipid)

1516 v = v._linked # switch

1517

1518 @property

1519 def xtend(self):

1520 '''Get the option to handle I{degenerate cases} (C{bool}).

1521 '''

1522 return self._xtend

1523

1524 @xtend.setter # PYCHOK setter!

1525 def xtend(self, xtend):

1526 '''Set the option to handle I{degenerate cases} (C{bool}).

1527 '''

1528 self._xtend = bool(xtend)

1529

1530

1531 class _EdgeFHP(object):

1532 # An edge between two L{LatLonFHP} points.

1533

1534 X_INTERSECT = _Enum('Xi', 1) # C++ enum

1535 X_OVERLAP = _Enum('Xo', 5)

1536 P_INTERSECT = _Enum('Pi', 3)

1537 P_OVERLAP = _Enum('Po', 7)

1538 Ps = (P_INTERSECT, P_OVERLAP, X_OVERLAP)

1539 Q_INTERSECT = _Enum('Qi', 2)

1540 Q_OVERLAP = _Enum('Qo', 6)

1541 Qs = (Q_INTERSECT, Q_OVERLAP, X_OVERLAP)

1542 V_INTERSECT = _Enum('Vi', 4)

1543 V_OVERLAP = _Enum('Vo', 8)

1544 Vs = (V_INTERSECT, V_OVERLAP)

1545

1546 def __init__(self, p1, p2, **unused):

1547 # New edge between points C{p1} and C{p2}, each a L{LatLonFHP}.

1548 self._p1_p2 = p1, p2

1549 self._dp = dp = p2 - p1

1550 self._dp2 = dp * dp # dot product, hypot2

1551

1552 self._lr, \

1553 self._bt = _left_right_bottom_top_eps2(p1, p2)

1554

1555 def _intersect3(self, q1, q2):

1556 # Return intersection Type or C{None}

1557 if not (_outside(q1.x, q2.x, *self._lr) or

1558 _outside(q1.y, q2.y, *self._bt)):

1559 dq = q2 - q1

1560 dq2 = dq * dq # dot product, hypot2

1561 if dq2 > EPS2: # like ._clip

1562 T, E = None, _EdgeFHP # self.__class__

1563 p1, p2 = self._p1_p2

1564 ap1 = p1._2A(q1, q2)

1565 ap2_1 = p2._2A(q1, q2) - ap1

1566 if fabs(ap2_1) > _0_EPS: # non-parallel edges

1567 aq1 = q1._2A(p1, p2)

1568 aq2_1 = q2._2A(p1, p2) - aq1

1569 if fabs(aq2_1) > _0_EPS:

1570 # compute and classify alpha and beta

1571 a, a_0, a_0_1, _ = _alpha4(-ap1 / ap2_1)

1572 b, b_0, b_0_1, _ = _alpha4(-aq1 / aq2_1)

1573 # distinguish intersection types

1574 T = E.X_INTERSECT if a_0_1 and b_0_1 else (

1575 E.P_INTERSECT if a_0_1 and b_0 else (

1576 E.Q_INTERSECT if a_0 and b_0_1 else (

1577 E.V_INTERSECT if a_0 and b_0 else None)))

1578

1579 elif fabs(ap1) < _0_EPS: # parallel or colinear edges

1580 dp = self._dp

1581 d1 = q1 - p1

1582 # compute and classify alpha and beta

1583 a, a_0, a_0_1, _a_0_1 = _alpha4((d1 * dp) / self._dp2)

1584 b, b_0, b_0_1, _b_0_1 = _alpha4((d1 * dq) / (-dq2))

1585 # distinguish overlap type

1586 T = E.X_OVERLAP if a_0_1 and b_0_1 else (

1587 E.P_OVERLAP if a_0_1 and _b_0_1 else (

1588 E.Q_OVERLAP if _a_0_1 and b_0_1 else (

1589 E.V_OVERLAP if a_0 and b_0 else None)))

1590

1591 if T:

1592 if T is E.X_INTERSECT:

1593 v = p1 + a * self._dp

1594 yield T, (v, p1, p2, a), (v, q1, q2, b)

1595 elif T in E.Vs:

1596 yield T, (p1,), (q1,)

1597 else:

1598 if T in E.Qs:

1599 yield T, (p1,), (p1, q1, q2, b)

1600 if T in E.Ps:

1601 yield T, (q1, p1, p2, a), (q1,)

1602

1603

1604 class _EdgeGH(object):

1605 # An edge between two L{LatLonGH} points.

1606

1607 _raiser = False

1608 _xtend = False

1609

1610 def __init__(self, s1, s2, raiser=False, xtend=False, **unused):

1611 # New edge between points C{s1} and C{s2}, each a L{LatLonGH}.

1612 self._s1, self._s2 = s1, s2

1613 self._x_sx_y_sy = (s1.x, s2.x - s1.x,

1614 s1.y, s2.y - s1.y)

1615 self._lr, \

1616 self._bt = _left_right_bottom_top_eps2(s1, s2)

1617

1618 if xtend:

1619 self._xtend = True

1620 elif raiser:

1621 self._raiser = True

1622

1623 def _alpha2(self, x, y, dx, dy):

1624 # Return C{(alpha)}, see .points.nearestOn5

1625 a = (y * dy + x * dx) / self._hypot2

1626 d = (y * dx - x * dy) / self._hypot0

1627 return a, fabs(d)

1628

1629 def _Error(self, n, *args, **kwds): # PYCHOK no cover

1630 t = unstr(_EdgeGH.__name__, self._s1, self._s2)

1631 t = _DOT_(t, _EdgeGH._intersect4.__name__)

1632 t = unstr(t, *args, **kwds)

1633 return ClipError(_case_, n, txt=t)

1634

1635 @Property_RO

1636 def _hypot0(self):

1637 _, sx, _, sy = self._x_sx_y_sy

1638 return hypot(sx, sy) * _0_EPS

1639

1640 @Property_RO

1641 def _hypot2(self):

1642 _, sx, _, sy = self._x_sx_y_sy

1643 return hypot2(sx, sy)

1644

1645 def _intersect4(self, c1, c2, parallel=True): # MCCABE 14

1646 # Yield the intersections of this and another edge.

1647

1648 # @return: None, 1 or 2 intersections, each a 4-Tuple

1649 # (y, x, s_alpha, c_alpha) with intersection

1650 # coordinates x and y and both alphas.

1651

1652 # @raise ClipError: Intersection unhandled.

1653

1654 # @see: U{Intersection point of two line segments

1655 # <http://PaulBourke.net/geometry/pointlineplane/>}.

1656 c1_x, c1_y = c1.x, c1.y

1657 if not (_outside(c1_x, c2.x, *self._lr) or

1658 _outside(c1_y, c2.y, *self._bt)):

1659 x, sx, \

1660 y, sy = self._x_sx_y_sy

1661

1662 cx = c2.x - c1_x

1663 cy = c2.y - c1_y

1664 d = cy * sx - cx * sy

1665

1666 if fabs(d) > _0_EPS: # non-parallel edges

1667 dx = x - c1_x

1668 dy = y - c1_y

1669 ca = (sx * dy - sy * dx) / d

1670 if _0_EPS < ca < _EPS_1 or (self._xtend and

1671 _EPS_0 < ca < _1_EPS):

1672 sa = (cx * dy - cy * dx) / d

1673 if _0_EPS < sa < _EPS_1 or (self._xtend and

1674 _EPS_0 < sa < _1_EPS):

1675 yield (y + sa * sy), (x + sa * sx), sa, ca

1676

1677 # unhandled, "degenerate" cases 1, 2 or 3

1678 elif self._raiser and not (sa < _EPS_0 or sa > _1_EPS): # PYCHOK no cover

1679 raise self._Error(1, c1, c2, sa=sa) # intersection at s1 or s2

1680

1681 elif self._raiser and not (ca < _EPS_0 or ca > _1_EPS): # PYCHOK no cover

1682 # intersection at c1 or c2 or at c1 or c2 and s1 or s2

1683 sa = (cx * dy - cy * dx) / d

1684 e = 2 if sa < _EPS_0 or sa > _1_EPS else 3

1685 raise self._Error(e, c1, c2, ca=ca)

1686

1687 elif parallel and (sx or sy) and (cx or cy): # PYCHOK no cover

1688 # non-null, parallel or colinear edges

1689 sa1, d1 = self._alpha2(c1_x - x, c1_y - y, sx, sy)

1690 sa2, d2 = self._alpha2(c2.x - x, c2.y - y, sx, sy)

1691 if max(d1, d2) < _0_EPS:

1692 if self._xtend and not _outside(sa1, sa2, _EPS_0, _1_EPS):

1693 if sa1 > sa2: # anti-parallel

1694 sa1, sa2 = sa2, sa1

1695 ca1, ca2 = _1_0, _0_0

1696 else: # parallel

1697 ca1, ca2 = _0_0, _1_0

1698 ca = fabs((sx / cx) if cx else (sy / cy))

1699 # = hypot(sx, sy) / hypot(cx, cy)

1700 if sa1 < 0: # s1 is between c1 and c2

1701 ca *= ca1 + sa1

1702 yield y, x, ca1, _alpha1(ca)

1703 else: # c1 is between s1 and s2

1704 yield (y + sa1 * sy), (x + sa1 * sx), sa1, ca1

1705 if sa2 > 1: # s2 is between c1 and c2

1706 ca *= sa2 - _1_0

1707 yield (y + sy), (x + sx), ca2, _alpha1(ca2 - ca)

1708 else: # c2 is between s1 and s2

1709 yield (y + sa2 * sy), (x + sa2 * sx), sa2, ca2

1710 elif self._raiser and not _outside(sa1, sa2, _0_0, _1_EPS):

1711 raise self._Error(4, c1, c2, d1=d1, d2=d2)

1712

1713

1714 class _BooleanBase(object):

1715 # Shared C{Boolean[FHP|GH]} methods.

1716

1717 def __add__(self, other):

1718 '''Sum: C{this + other} clips.

1719 '''

1720 return self._sum(_other(self, other), self.__add__) # PYCHOK OK

1721

1722 def __and__(self, other):

1723 '''Intersection: C{this & other}.

1724 '''

1725 return self._boolean(other, False, False, self.__and__) # PYCHOK OK

1726

1727 def __iadd__(self, other):

1728 '''In-place sum: C{this += other} clips.

1729 '''

1730 return self._inplace(self.__add__(other))

1731

1732 def __iand__(self, other):

1733 '''In-place intersection: C{this &= other}.

1734 '''

1735 return self._inplace(self.__and__(other))

1736

1737 def __ior__(self, other):

1738 '''In-place union: C{this |= other}.

1739 '''

1740 return self._inplace(self.__or__(other))

1741

1742 def __or__(self, other):

1743 '''Union: C{this | other}.

1744 '''

1745 return self._boolean(other, True, True, self.__or__) # PYCHOK OK

1746

1747 def __radd__(self, other):

1748 '''Reverse sum: C{other + this} clips.

1749 '''

1750 return _other(self, other)._sum(self, self.__radd__)

1751

1752 def __rand__(self, other):

1753 '''Reverse intersection: C{other & this}

1754 '''

1755 return _other(self, other).__and__(self)

1756

1757 def __ror__(self, other):

1758 '''Reverse union: C{other | this}

1759 '''

1760 return _other(self, other).__or__(self)

1761

1762 def _boolean4(self, other, op):

1763 # Set up a new C{Boolean[FHP|GH]}.

1764 C = self.__class__

1765 kwds = C._kwds(self, op)

1766 a = C(self, **kwds)

1767 b = _other(self, other)

1768 return a, b, C, kwds

1769

1770 def _inplace(self, r):

1771 # Replace this with a L{Boolean*} result.

1772 self._clips, r._clips = r._clips, None

1773# if self._raiser != r._raiser:

1774# self._raiser = r._raiser

1775# if self._xtend != r._xtend:

1776# self._xtend = r._xtend

1777# if self._eps != r._eps:

1778# self._eps = r._eps

1779 return self

1780

1781

1782 class BooleanFHP(_CompositeFHP, _BooleanBase):

1783 '''I{Composite} class providing I{boolean} operations between two

1784 I{composites} using U{Forster-Hormann-Popa<https://www.ScienceDirect.com/

1785 science/article/pii/S259014861930007X>}'s C++ implementation, transcoded

1786 to pure Python.

1787

1788 The supported operations between (composite) polygon A and B are:

1789

1790 - C = A & B or A &= B, intersection of A and B

1791

1792 - C = A + B or A += B, sum of A and B clips

1793

1794 - C = A | B or A |= B, union of A and B

1795

1796 - A == B or A != B, equivalent A and B clips

1797

1798 - A.isequalTo(B, eps), equivalent within tolerance

1799

1800 @see: Methods C{__eq__} and C{isequalTo}, function L{clipFHP4}

1801 and class L{BooleanGH}.

1802 '''

1803 _kind = _boolean_

1804

1805 def __init__(self, lls, raiser=False, eps=EPS, name=NN):

1806 '''New L{BooleanFHP} operand for I{boolean} operation.

1807

1808 @arg lls: The polygon points and clips (iterable of L{LatLonFHP}s,

1809 L{ClipFHP4Tuple}s or other C{LatLon}s).

1810 @kwarg raiser: If C{True}, throw L{ClipError} exceptions (C{bool}).

1811 @kwarg esp: Tolerance for eliminating null edges (C{degrees}, same

1812 units as the B{C{lls}} coordinates).

1813 @kwarg name: Optional name (C{str}).

1814 '''

1815 _CompositeFHP.__init__(self, lls, raiser=raiser,

1816 eps=eps, name=name)

1817

1818 def __isub__(self, other):

1819 '''Not implemented.'''

1820 return _NotImplemented(self, other)

1821

1822 def __rsub__(self, other):

1823 '''Not implemented.'''

1824 return _NotImplemented(self, other)

1825

1826 def __sub__(self, other):

1827 '''Not implemented.'''

1828 return _NotImplemented(self, other)

1829

1830 def _boolean(self, other, Union, unused, op):

1831 # One C{BooleanFHP} operation.

1832 p, q, C, kwds = self._boolean4(other, op)

1833 r = p._clip(q, Union=Union, **kwds)

1834 return C(r, **kwds)

1835

1836

1837 class BooleanGH(_CompositeGH, _BooleanBase):

1838 '''I{Composite} class providing I{boolean} operations between two

1839 I{composites} using the U{Greiner-Hormann<http://www.Inf.USI.CH/

1840 hormann/papers/Greiner.1998.ECO.pdf>} algorithm and U{Correia

1841 <https://GitHub.com/helderco/univ-polyclip>}'s implementation,

1842 modified and extended.

1843

1844 The supported operations between (composite) polygon A and B are:

1845

1846 - C = A - B or A -= B, difference A less B

1847

1848 - C = B - A or B -= A, difference B less B

1849

1850 - C = A & B or A &= B, intersection of A and B

1851

1852 - C = A + B or A += B, sum of A and B clips

1853

1854 - C = A | B or A |= B, union of A and B

1855

1856 - A == B or A != B, equivalent A and B clips

1857

1858 - A.isequalTo(B, eps), equivalent within tolerance

1859

1860 @note: To handle I{degenerate cases} like C{point-edge} and

1861 C{point-point} intersections, use class L{BooleanFHP}.

1862

1863 @see: Methods C{__eq__} and C{isequalTo}, function L{clipGH4}

1864 and class L{BooleanFHP}.

1865 '''

1866 _kind = _boolean_

1867

1868 def __init__(self, lls, raiser=True, xtend=False, eps=EPS, name=NN):

1869 '''New L{BooleanFHP} operand for I{boolean} operation.

1870

1871 @arg lls: The polygon points and clips (iterable of L{LatLonGH}s,

1872 L{ClipGH4Tuple}s or other C{LatLon}s).

1873 @kwarg raiser: If C{True}, throw L{ClipError} exceptions (C{bool}).

1874 @kwarg xtend: If C{True}, extend edges of I{degenerate cases}, an

1875 attempt to handle the latter (C{bool}).

1876 @kwarg esp: Tolerance for eliminating null edges (C{degrees}, same

1877 units as the B{C{lls}} coordinates).

1878 @kwarg name: Optional name (C{str}).

1879 '''

1880 _CompositeGH.__init__(self, lls, raiser=raiser, xtend=xtend,

1881 eps=eps, name=name)

1882

1883 def _boolean(self, other, s_entry, c_entry, op):

1884 # One C{BooleanGH} operation.

1885 s, c, C, kwds = self._boolean4(other, op)

1886 r = s._clip(c, s_entry, c_entry, **kwds)

1887 return C(r, **kwds)

1888

1889 def __isub__(self, other):

1890 '''In-place difference: C{this -= other}.

1891 '''

1892 return self._inplace(self.__sub__(other))

1893

1894 def __rsub__(self, other):

1895 ''' Reverse difference: C{other - this}

1896 '''

1897 return _other(self, other).__sub__(self)

1898

1899 def __sub__(self, other):

1900 '''Difference: C{this - other}.

1901 '''

1902 return self._boolean(other, True, False, self.__sub__)

1903

1904

1905 def _alpha1(alpha):

1906 # Return C{alpha} in C{[0..1]} range

1907 if _EPS_0 < alpha < _1_EPS:

1908 return max(_0_0, min(alpha, _1_0))

1909 t = _not_(Fmt.SQUARE(_ELLIPSIS_(0, 1)))

1910 raise ClipError(_alpha_, alpha, txt=t)

1911

1912

1913 def _alpha4(a):

1914 # Return 4-tuple (alpha, -EPS < alpha < EPS,

1915 # 0 < alpha < 1,

1916 # not 0 < alpha < 1)

1917 return (a, False, True, False) if _0_EPS < a < _EPS_1 else (

1918 (a, False, False, True) if _0_EPS < fabs(a) else

1919 (a, True, False, False))

1920

1921

1922 def _Cps(Cp, composites_points, where):

1923 # Yield composites and points as a C{Cp} composite.

1924 try:

1925 kwds = dict(kind=_points_, name=where.__name__)

1926 for cp in composites_points:

1927 yield cp if isBoolean(cp) else Cp(cp, **kwds)

1928 except (AttributeError, ClipError, TypeError, ValueError) as x:

1929 raise _ValueError(points=cp, cause=x)

1930

1931

1932 def _eps0(eps):

1933 # Adjust C{eps} or C{None}.

1934 return eps if eps and eps > EPS else 0

1935

1936

1937 def isBoolean(obj):

1938 '''Check for C{Boolean} composites.

1939

1940 @arg obj: The object (any C{type}).

1941

1942 @return: C{True} if B{C{obj}} is L{BooleanFHP},

1943 L{BooleanGH} oe some other composite,

1944 C{False} otherwise.

1945 '''

1946 return isinstance(obj, _CompositeBase)

1947

1948

1949 def _left_right_bottom_top_eps2(p1, p2):

1950 '''(INTERNAL) Return 2-tuple C{(left, right), (bottom, top)}, oversized.

1951 '''

1952 return (_min_max_eps2(p1.x, p2.x),

1953 _min_max_eps2(p1.y, p2.y))

1954

1955

1956 def _low_high_eps2(lo, hi, eps):

1957 '''(INTERNAL) Return 2-tuple C{(lo, hi)}, oversized.

1958 '''

1959 lo *= (_1_0 + eps) if lo < 0 else (_1_0 - eps)

1960 hi *= (_1_0 - eps) if hi < 0 else (_1_0 + eps)

1961 return (lo or -eps), (hi or eps)

1962

1963

1964 def _min_max_eps2(*xs):

1965 '''(INTERNAL) Return 2-tuple C{(min, max)}, oversized.

1966 '''

1967 lo, hi = min(xs), max(xs)

1968 lo *= _1_EPS if lo < 0 else _EPS_1

1969 hi *= _EPS_1 if hi < 0 else _1_EPS

1970 return (lo or _EPS_0), (hi or _0_EPS)

1971

1972

1973 def _other(this, other):

1974 '''(INTERNAL) Check for compatible C{type}s.

1975 '''

1976 C = this.__class__

1977 if isinstance(other, C):

1978 return other

1979 raise _IsnotError(C.__name__, other=other)

1980

1981

1982 def _outside(x1, x2, lo, hi):

1983 '''(INTERNAL) Is C{(x1, x2)} outside C{(lo, hi)}?

1984 '''

1985 return max(x1, x2) < lo or min(x1, x2) > hi

1986

1987

1988__all__ += _ALL_DOCS(_BooleanBase, _Clip,

1989 _CompositeBase, _CompositeFHP, _CompositeGH,

1990 _LatLonBool)

1991

1992# **) MIT License

1993#

1994# Copyright (C) 2018-2023 -- mrJean1 at Gmail -- All Rights Reserved.

1995#

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

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

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

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

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

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

2002#

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

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

2005#

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

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

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

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

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

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

2012# OTHER DEALINGS IN THE SOFTWARE.

2013

2014# ***) GNU GPL 3

2015#

2016# Copyright (C) 2011-2012 Helder Correia <Helder.MC@Gmail.com>

2017#

2018# This program is free software: you can redistribute it and/or

2019# modify it under the terms of the GNU General Public License as

2020# published by the Free Software Foundation, either version 3 of

2021# the License, or any later version.

2022#

2023# This program is distributed in the hope that it will be useful,

2024# but WITHOUT ANY WARRANTY; without even the implied warranty of

2025# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

2026# GNU General Public License for more details.

2027#

2028# You should have received a copy of the GNU General Public License

2029# along with this program. If not, see <http://www.GNU.org/licenses/>.

2030#

2031# You should have received the README file along with this program.

2032# If not, see <https://GitHub.com/helderco/univ-polyclip>.