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, issubclassof, map2, _xscalar

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, _xkwds_pop2

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_, _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 _name__, _Named, _NotImplemented, \

35 Fmt, pairs, unstr

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

37# from pygeodesy.points import boundsOf # _MODS

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

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

40 from pygeodesy.units import Height, HeightX

41 from pygeodesy.utily import fabs, _unrollon, _Wrap

42

43# from math import fabs # from .utily

44

45__all__ = _ALL_LAZY.booleans

46__version__ = '24.06.06'

47

48_0_EPS = EPS # near-zero, positive

49_EPS_0 = -EPS # near-zero, negative

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

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

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

53

54_alpha_ = 'alpha'

55_boolean_ = 'boolean'

56_case_ = 'case'

57_corners_ = 'corners'

58_duplicate_ = 'duplicate'

59_open_ = 'open'

60

61

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

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

64

65

66 class _L(object): # Intersection labels

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

68 CROSSING_D = _Enum(_X_ + _d_, 8)

69 CROSSINGs = (CROSSING, CROSSING_D)

70 BOUNCING = _Enum(_B_, 2)

71 BOUNCING_D = _Enum(_B_ + _d_, 9)

72 BOUNCINGs = (BOUNCING, BOUNCING_D) + CROSSINGs

73 LEFT_ON = _Enum('Lo', 3)

74 ON_ON = _Enum('oo', 5)

75 ON_LEFT = _Enum('oL', 6)

76 ON_RIGHT = _Enum('oR', 7)

77 RIGHT_ON = _Enum('Ro', 4)

78 RIGHT_LEFT_ON = (RIGHT_ON, LEFT_ON)

79 # Entry/Exit flags

80 ENTRY = _Enum(_e_, 1)

81 EXIT = _Enum(_x_, 0)

82 Toggle = {ENTRY: EXIT,

83 EXIT: ENTRY,

84 None: None}

85

86_L = _L() # PYCHOK singleton

87

88

89 class _RP(object): # RelativePositions

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

91 IS_Pp = _Enum('Pp', 3)

92 LEFT = _Enum('L', 0)

93 RIGHT = _Enum(_R_, 1)

94

95_RP = _RP() # PYCHOK singleton

96

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

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

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

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

101 # overlapping cases

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

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

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

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

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

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

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

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

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

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

112

113

114 class _LatLonBool(_Named):

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

116 '''

117 _alpha = None # point AND intersection else length

118 _checked = False # checked in phase 3 iff intersection

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

120 _dupof = None # original of a duplicate

121# _e_x_str = NN # shut up PyChecker

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

123 _linked = None # link to neighbor iff intersection

124 _next = None # link to the next vertex

125 _prev = None # link to the previous vertex

126

127 def __init__(self, lat_ll, lon=None, height=0, clipid=INT0, wrap=False, **name):

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

129 scalars or from a previous C{LatLon[FHP|GH]}, C{Clip[FHP|GH]4Tuple} or some

130 other C{LatLon} instance.

131

132 @arg lat_ll: Latitude (C{scalar}) or a lat-/longitude (C{LatLon[FHP|GH]},

133 C{Clip[FHP|GH]4Tuple} or some other C{LatLon}).

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

135 otherwise.

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

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

138 @kwarg wrap: If C{True}, wrap or I{normalize} B{C{lat}} and B{C{lon}} (C{bool}).

139 @kwarg name: Optional C{B{name}=NN} (C{str}).

140 '''

141 h, name = _xkwds_pop2(name, h=height) if name else (height, name)

142

143 if lon is None:

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

145 h = _xattr(lat_ll, height=h)

146 c = _xattr(lat_ll, clipid=clipid)

147 else:

148 y, x, c = lat_ll, lon, clipid

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

150 # don't duplicate defaults

151 if self._height != h:

152 self._height = h

153 if self._clipid != c:

154 self._clipid = c

155 if name:

156 self.name = name

157

158 def __abs__(self):

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

160

161 def __eq__(self, other):

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

163 other.x == self.x and

164 other.y == self.y)

165

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

167 return not self.__eq__(other)

168

169 def __repr__(self):

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

171 '''

172 if self._prev or self._next:

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

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

175 else:

176 t = str(self)

177 return t

178

179 def __str__(self):

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

181 '''

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

183 if self._height:

184 X = _X_ if self.isintersection else NN

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

186 if self._clipid:

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

188 if self._alpha is not None:

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

190# if self._dupof: # recursion risk

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

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

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

194 if self._linked:

195 k = _DOT_ if self._checked else _BANG_

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

197 return NN(self.name, t)

198

199 def __sub__(self, other):

200 _other(self, other)

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

202 self.x - other.x)

203

204 def _2A(self, p2, p3):

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

206 x, y = self.x, self.y

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

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

209

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

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

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

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

214 return 0 if a < eps else a

215

216 @property_RO

217 def clipid(self):

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

219 '''

220 return self._clipid

221

222 def _equi(self, llb, eps):

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

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

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

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

227

228 @property_RO

229 def height(self):

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

231 '''

232 h = self._height

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

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

235

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

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

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

239

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

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

242

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

244

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

246 '''

247 try:

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

249 except (AttributeError, TypeError, ValueError):

250 raise _IsnotError(_LatLon_, other=other)

251

252 @property_RO

253 def isintersection(self):

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

255 '''

256 return bool(self._linked)

257

258 @property_RO

259 def ispoint(self):

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

261 '''

262 return self._alpha is None

263

264 @property_RO

265 def lat(self):

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

267 '''

268 return self.y

269

270 @property_RO

271 def latlon(self):

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

273 '''

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

275

276 def _link(self, other):

277 # Make this and an other point neighbors.

278 # assert _other(self, other)

279 self._linked = other

280 other._linked = self

281

282 @property_RO

283 def lon(self):

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

285 '''

286 return self.x

287

288 def _toClas(self, Clas, clipid):

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

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

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

292

293

294 class LatLonFHP(_LatLonBool):

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

296 '''

297 _en_ex = None

298 _label = None

299 _2split = None # or C{._Clip}

300 _2xing = False

301

302 def __init__(self, lat_ll, lon=None, height=0, clipid=INT0, **wrap_name):

303 '''New C{LatLonFHP} from separate C{lat}, C{lon}, C{h}eight and C{clipid}

304 scalars, or from a previous L{LatLonFHP}, L{ClipFHP4Tuple} or some other

305 C{LatLon} instance.

306

307 @arg lat_ll: Latitude (C{scalar}) or a lat-/longitude (L{LatLonFHP},

308 L{ClipFHP4Tuple} or some other C{LatLon}).

309

310 @see: L{Here<_LatLonBool.__init__>} for further details.

311 '''

312 _LatLonBool.__init__(self, lat_ll, lon, height, clipid, **wrap_name)

313

314 def __add__(self, other):

315 _other(self, other)

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

317

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

319 _other(self, other)

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

321

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

323 _other(self, other)

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

325

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

327 _xscalar(other=other)

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

329

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

331 if self._label:

332 t = NN(self._label, t)

333 if self._en_ex:

334 t = NN(t, self._en_ex)

335 return t

336

337 @property_RO

338 def _isduplicate(self):

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

340 p = self._dupof

341 return bool(p and self._linked

342 and p is not self

343 and p == self

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

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

346

347# @property_RO

348# def _isduplicated(self):

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

350# d, v = 0, self

351# while v:

352# if v._dupof is self:

353# d += 1

354# v = v._next

355# if v is self:

356# break

357# return d

358

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

360 '''Is this point inside one or more composites or polygons based on

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

362 pii/S0925772101000128>}?

363

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

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

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

367 @kwarg wrap: Optional keyword argument C{B{wrap}=False}, if C{True},

368 wrap or I{normalize} and unroll all C{points} (C{bool}).

369

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

371

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

373 article/pii/S0925772101000128>}.

374 '''

375 class _Pseudo(object):

376 # Pseudo-_CompositeBase._clips tuple

377

378 @property_RO

379 def _clips(self):

380 for cp in _Cps(_CompositeFHP, composites_points,

381 LatLonFHP.isenclosedBy): # PYCHOK yield

382 for c in cp._clips:

383 yield c

384

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

386

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

388 # Is this point inside a composite, excluding

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

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

391 for c in composite._clips:

392 if c not in excludes:

393 w = 0

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

395 # edge [p1,p2] must straddle y

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

397 r = p2.x > x

398 s = p2.y > p1.y

399 if p1.x < x:

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

401 else:

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

403 if b:

404 w += 1 if s else -1

405 if isodd(w):

406 i = not i

407 return i

408

409 @property_RO

410 def _prev_next2(self):

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

412 p, n = self, self._next

413 if self._isduplicate:

414 p = self._dupof

415 while p._isduplicate:

416 p = p._dupof

417 while n._isduplicate:

418 n = n._next

419 return p._prev, n

420

421# def _edge2(self):

422# # Return the start and end point of the

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

424# n = p = self

425# while p.isintersection:

426# p = p._prev

427# if p is self:

428# break

429# while n.isintersection:

430# n = n._next

431# if n is self:

432# break

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

434# return p, n

435

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

437 # Relative Position oracle

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

439 T = _RP.IS_Pm

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

441 T = _RP.IS_Pp

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

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

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

445 _RP.RIGHT # PYCHOK indent

446 else: # right turn (or straight)

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

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

449 _RP.LEFT # PYCHOK indent

450 return T

451

452

453 class LatLonGH(_LatLonBool):

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

455 '''

456 _entry = None # entry or exit iff intersection

457

458 def __init__(self, lat_ll, lon=None, height=0, clipid=INT0, **wrap_name):

459 '''New C{LatLonGH} from separate C{lat}, C{lon}, C{h}eight and C{clipid}

460 scalars, or from a previous L{LatLonGH}, L{ClipGH4Tuple} or some other

461 C{LatLon} instance.

462

463 @arg lat_ll: Latitude (C{scalar}) or a lat-/longitude (L{LatLonGH},

464 L{ClipGH4Tuple} or some other C{LatLon}).

465

466 @see: L{Here<_LatLonBool.__init__>} for further details.

467 '''

468 _LatLonBool.__init__(self, lat_ll, lon, height, clipid, **wrap_name)

469

470 def _check(self):

471 # Check-mark this vertex and its link.

472 self._checked = True

473 k = self._linked

474 if k and not k._checked:

475 k._checked = True

476

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

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

479 (_e_ if self._entry else _x_))

480

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

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

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

484 article/pii/S0925772101000128>}?

485

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

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

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

489 @kwarg wrap: Optional keyword argument C{B{wrap}=False}, if C{True},

490 wrap or I{normalize} and unroll all C{points} (C{bool}).

491

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

493 '''

494 class _Pseudo(object):

495 # Pseudo-_CompositeBase._edges3 method

496

497 def _edges3(self, **kwds):

498 for cp in _Cps(_CompositeGH, composites_points,

499 LatLonGH.isenclosedBy): # PYCHOK yield

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

501 yield e

502

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

504

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

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

507

508 def _x(y, p1, p2):

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

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

511

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

513 # intersecting a ray emitted from this point to

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

515 # inside, if I{even} outside.

516 y, i = self.y, False

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

518 x = self.x

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

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

521 r = p2.x > x

522 if p1.x < x:

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

524 else:

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

526 if b:

527 i = not i

528 return i

529

530

531 class _Clip(_Named):

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

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

534 and intersections with other clips.

535 '''

536 _composite = None

537 _dups = 0

538 _first = None

539 _id = 0

540 _identical = False

541 _noInters = False

542 _last = None

543 _LL = None

544 _len = 0

545 _pushback = False

546

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

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

549 '''

550 # assert isinstance(composite, _CompositeBase)

551 if clipid in composite._clipids:

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

553 self._composite = composite

554 self._id = clipid

555 self._LL = composite._LL

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

557

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

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

560 '''

561 for v in self:

562 if v is point: # or ==?

563 return True

564 return False

565

566 def __eq__(self, other):

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

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

569 the same order, possibly rotated?

570 '''

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

572

573 def __ge__(self, other):

574 '''See method C{__lt__}.

575 '''

576 return not self.__lt__(other)

577

578 def __gt__(self, other):

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

580 located or stretched farther North or East?

581 '''

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

583

584 def __hash__(self): # PYCHOK no over

585 return hash(self._bltr4)

586

587 def __iter__(self):

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

589 '''

590 v = f = self._first

591 while v:

592 yield v

593 v = v._next

594 if v is f:

595 break

596

597 def __le__(self, other):

598 '''See method C{__gt__}.

599 '''

600 return not self.__gt__(other)

601

602 def __len__(self):

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

604 intersections in this clip.

605 '''

606 return self._len

607

608 def __lt__(self, other):

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

610 located or stretched farther South or West?

611 '''

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

613

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

615 '''See method C{__eq__}.

616 '''

617 return not self.__eq__(other)

618

619 _all = __iter__

620

621 @property_RO

622 def _all_ON_ON(self):

623 # Check whether all vertices are ON_ON.

624 L_ON_ON = _L.ON_ON

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

626

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

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

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

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

631 self._len += 1

632 # assert v._clipid == self._id

633

634 v._next = n = self._first

635 if n is None: # set ._first

636 self._first = p = n = v

637 else: # insert before ._first

638 v._prev = p = n._prev

639 p._next = n._prev = v

640 return v

641

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

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

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

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

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

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

648# if v._linked:

649# p._linked = True # to force errors

650# return p

651

652 @Property_RO

653 def _bltr4(self):

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

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

656

657 def _bltr4eps(self, eps):

658 # Get the ._bltr4 bounds tuple, slightly oversized.

659 if eps > 0: # > EPS

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

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

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

663 t = yb, xl, yt, xr

664 else:

665 t = self._bltr4

666 return t

667

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

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

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

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

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

673 # un-close the clip

674 f._prev = p = p._prev

675 p._next = f

676 self._len -= 1

677# elif f and raiser:

678# raise self._OpenClipError(p, f)

679 if len(self) < 3:

680 raise self._Error(_too_(_few_))

681

682 def _dup(self, q):

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

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

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

686 v._dupof = q._dupof or q

687 # assert v._prev is q

688 # assert q._next is v

689 return v

690

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

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

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

694 p1 = p = f = self._first

695 while p:

696 p2 = p = p._next

697 if p.ispoint:

698 if wrap and p is not f:

699 p2 = _unrollon(p1, p)

700 yield p1, p2

701 p1 = p2

702 if p is f:

703 break

704

705 def _equi(self, clip, eps):

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

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

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

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

710 == clip._bltr4eps(eps):

711 _equi = _LatLonBool._equi

712 for v in clip:

713 if _equi(f, v, eps):

714 s, n = f, v

715 for _ in range(r):

716 s, n = s._next, n._next

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

718 break # next v

719 else: # equivalent

720 return True

721 return False

722

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

724 # Build a C{ClipError} instance

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

726 if self._dups:

727 kwds.update(dups=self._dups)

728 cp = self._composite

729 if self._id:

730 try:

731 i = cp._clips.index(self)

732 if i != self._id:

733 kwds[_clip_] = i

734 except ValueError:

735 pass

736 kwds[_clipid_] = self._id

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

738

739 def _index(self, clips, eps):

740 # see _CompositeBase._equi

741 for i, c in enumerate(clips):

742 if c._equi(self, eps):

743 return i

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

745

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

747 # insertVertex between points C{start} and

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

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

750 n = start._next

751 if end_alpha:

752 end, alpha = end_alpha

753 v._alpha = alpha

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

755 # assert start is not end

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

757 n = n._next

758 v._next = n

759 v._prev = p = n._prev

760 p._next = n._prev = v

761 self._len += 1

762# _Clip._bltr4._update(self)

763# _Clip._ishole._update(self)

764 return v

765

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

767 # insert an intersection or make a point both

768 if p1_p2_alpha: # intersection on edge

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

770 else: # intersection at point

771 v = q

772 # assert not v._linked

773 # assert v._alpha is None

774 return v

775

776 def _intersections(self):

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

778 for v in self:

779 if v.isintersection:

780 yield v

781

782 @Property_RO

783 def _ishole(self): # PYCHOK no cover

784 # Is this clip a hole inside its composite?

785 v = self._first

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

787

788 @property_RO

789 def _nodups(self):

790 # Yield all non-duplicates.

791 for v in self:

792 if not v._dupof:

793 yield v

794

795 def _noXings(self, Union):

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

797 Xings = _L.BOUNCINGs if Union else _L.CROSSINGs

798 return all(v._label not in Xings for v in self._intersections())

799

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

801 # Return a C{CloseError} instance

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

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

804

805 def _point2(self, insert):

806 # getNonIntersectionPoint and -Vertex

807 if not (insert and self._noInters):

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

809 return p, None

810 for n in self._intersections():

811 p, _ = n._prev_next2

812 k = p._linked

813 if k:

814 if n._linked not in k._prev_next2:

815 # create a pseudo-point

816 k = _0_5 * (p + n)

817 if insert:

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

819 r = k # to remove later

820 else: # no ._prev, ._next

821 k._clipid = n._clipid

822 r = None

823 return k, r

824 return None, None

825

826 def _points(self, may_be=True):

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

828 for v in self:

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

830 yield v

831

832 def _remove2(self, v):

833 # Remove vertex C{v}.

834 # assert not v._isduplicated

835 if len(self) > 1:

836 p = v._prev

837 p._next = n = v._next

838 n._prev = p

839 if self._first is v:

840 self._first = n

841 if self._last is v:

842 self._last = p

843 self._len -= 1

844 else:

845 n = self._last = \

846 p = self._first = None

847 self._len = 0

848 return p, n

849

850 def _update_all(self): # PYCHOK no cover

851 # Zap the I{cached} properties.

852 _Clip._bltr4._update( self)

853 _Clip._ishole._update(self)

854 return self # for _special_identicals

855

856 def _Xings(self):

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

858 CROSSING = _L.CROSSING

859 for v in self._intersections():

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

861 yield v

862

863

864 class _CompositeBase(_Named):

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

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

867 '''

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

869 _eps = EPS # null edges

870 _kind = _corners_

871 _LL = _LatLonBool # shut up PyChecker

872 _raiser = False

873 _xtend = False

874

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

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

877 '''

878 n = _name__(name, _or_nameof=lls)

879 if n:

880 self.name = n

881 if kind:

882 self._kind = kind

883 if self._eps < eps:

884 self._eps = eps

885

886 c = _Clip(self)

887 lp = None

888 for ll in lls:

889 ll = self._LL(ll)

890 if lp is None:

891 c._id = ll._clipid # keep clipid

892 lp = c._append(ll)

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

894 c._closed(self.raiser)

895 c = _Clip(self, ll._clipid)

896 lp = c._append(ll)

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

898 lp = c._append(ll)

899 else:

900 c._dups += 1

901 c._closed(self.raiser)

902

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

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

905 '''

906 for c in self._clips:

907 if point in c:

908 return True

909 return False

910

911 def __eq__(self, other):

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

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

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

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

916 possibly rotated.

917 '''

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

919

920 def __iter__(self):

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

922 '''

923 for c in self._clips:

924 for v in c:

925 yield v

926

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

928 '''See method C{__eq__}.

929 '''

930 return not self.__eq__(other)

931

932 def __len__(self):

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

934 '''

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

936

937 def __repr__(self):

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

939 '''

940 c = len(self._clips)

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

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

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

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

945

946 def __str__(self):

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

948 '''

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

950

951 @property_RO

952 def _bottom_top_eps2(self):

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

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

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

956

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

958 # Return a new instance

959 _g = kwds.get

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

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

962

963 @property_RO

964 def _clipids(self): # PYCHOK no cover

965 for c in self._clips:

966 yield c._id

967

968 def clipids(self):

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

970 '''

971 return tuple(self._clipids)

972

973# def _clipidups(self, other):

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

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

976

977 def _edges3(self, **raiser_wrap):

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

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

980 for c in self._clips:

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

982 yield p1, p2, c

983

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

985 # see function .points.isenclosedBy

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

987

988 @property

989 def eps(self):

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

991 '''

992 return self._eps

993

994 @eps.setter # PYCHOK setter!

995 def eps(self, eps):

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

997 '''

998 self._eps = eps

999

1000 def _10eps(self, **eps_):

1001 # Get eps for _LatLonBool._2Abs

1002 e = _xkwds_get(eps_, eps=self._eps)

1003 if e != EPS:

1004 e *= _10EPS / EPS

1005 else:

1006 e = _10EPS

1007 return e

1008

1009 def _equi(self, other, eps):

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

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

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

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

1014 if eps > 0:

1015 _index = _Clip._index

1016 else:

1017 def _index(c, cs, unused):

1018 return cs.index(c)

1019 try:

1020 cs = list(sorted(cs))

1021 for c in sorted(co):

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

1023 except ValueError: # from ._index

1024 pass

1025 return False if cs else True

1026 else: # both null?

1027 return False if cs or co else True

1028

1029 def _intersections(self):

1030 # Yield all intersections.

1031 for c in self._clips:

1032 for v in c._intersections():

1033 yield v

1034

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

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

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

1038

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

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

1041

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

1043

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

1045

1046 @see: Method C{__eq__}.

1047 '''

1048 if isinstance(other, _CompositeBase):

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

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

1051

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

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

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

1055 name=self.name or op.__name__)

1056 kwds.update(more)

1057 return kwds

1058

1059 @property_RO

1060 def _left_right_eps2(self):

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

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

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

1064

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

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

1067 for c in self._clips:

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

1069 yield v

1070

1071 @property

1072 def raiser(self):

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

1074 '''

1075 return self._raiser

1076

1077 @raiser.setter # PYCHOK setter!

1078 def raiser(self, throw):

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

1080 '''

1081 self._raiser = bool(throw)

1082

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

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

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

1086 e = self._10eps(**eps)

1087 for clipid, ns in enumerate(_presults):

1088 f = p = v = None

1089 for n in ns:

1090 if f is None:

1091 yield n._toClas(C, clipid)

1092 f = p = n

1093 elif v is None:

1094 v = n # got f, p, v

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

1096 yield v._toClas(C, clipid)

1097 p, v = v, n

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

1099 v = n

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

1101 yield v._toClas(C, clipid)

1102 p = v

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

1104 yield f._toClas(C, clipid)

1105

1106 def _sum(self, other, op):

1107 # Combine this and an C{other} composite

1108 LL = self._LL

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

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

1111 for cp in (self, other):

1112 for c in cp._clips:

1113 _ap = _Clip(sp, sid)._append

1114 for v in c._nodups:

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

1116 sid += 1

1117 return sp

1118

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

1120 # Sum the area or perimeter of all clips

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

1122

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

1124 # Sum the area or perimeter of all clips

1125

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

1127 _LL = LL

1128 for v in clip:

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

1130

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

1132

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

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

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

1136

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

1138 L{LatLonFHP} or L{LatLonGH}.

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

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

1141 keyword arguments, ignore if

1142 C{B{LatLon} is None}.

1143

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

1145

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

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

1148 '''

1149 if LatLon is None:

1150 LL, kwds = self._LL, {}

1151 elif issubclassof(LatLon, _LatLonBool, LatLonBase):

1152 LL, kwds = LatLon, LatLon_kwds

1153 else:

1154 raise _TypeError(LatLon=LatLon)

1155

1156 for c in self._clips:

1157 lf, cid = None, c._id

1158 for v in c._nodups:

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

1160 ll._height = v.height

1161 if ll._clipid != cid:

1162 ll._clipid = cid

1163 yield ll

1164 if lf is None:

1165 lf = ll

1166 if closed and lf:

1167 yield lf

1168

1169

1170 class _CompositeFHP(_CompositeBase):

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

1172 of L{LatLonFHP} points, duplicates and intersections

1173 with an other I{composite}.

1174 '''

1175 _LL = LatLonFHP

1176 _Union = False

1177

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

1179 # New L{_CompositeFHP}.

1180 if raiser:

1181 self._raiser = True

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

1183

1184 def _classify(self):

1185 # 2) Classify intersection chains.

1186 L = _L

1187 for v in self._intersections():

1188 n, b = v, v._label

1189 if b in L.RIGHT_LEFT_ON: # next chain

1190 while True:

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

1192 n = n._next

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

1194 break

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

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

1197

1198 # 3) Copy labels

1199 for v in self._intersections():

1200 v._linked._label = v._label

1201

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

1203 **closed_inull_raiser_eps):

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

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

1206 P = self

1207 Q = self._class(corners, closed_inull_raiser_eps,

1208 eps=P._eps, raiser=False)

1209 if Union:

1210 P._Union = Q._Union = True

1211

1212 bt = Q._bottom_top_eps2

1213 lr = Q._left_right_eps2

1214 # compute and insert intersections

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

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

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

1218 e = _EdgeFHP(p1, p2)

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

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

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

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

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

1224 # assert not p._linked

1225 # assert not q._linked

1226 p._link(q)

1227

1228 # label and classify intersections

1229 P._labelize()

1230 P._classify()

1231

1232 # check for special cases

1233 P._special_cases(Q)

1234 Q._special_cases(P)

1235 # handle identicals

1236 P._special_identicals(Q)

1237

1238 # set Entry/Exit flags

1239 P._set_entry_exits(Q)

1240 Q._set_entry_exits(P)

1241

1242 # handle splits and crossings

1243 P._splits_xings(Q)

1244

1245 # yield the results

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

1247

1248 @property_RO

1249 def _identicals(self):

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

1251 for c in self._clips:

1252 if c._identical:

1253 yield c

1254

1255 def _labelize(self):

1256 # 1) Intersections classification

1257 for p in self._intersections():

1258 q = p._linked

1259 # determine local configuration at this intersection

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

1261 p1, p3 = p._prev_next2

1262 q1, q3 = q._prev_next2

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

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

1265 # check intersecting and overlapping cases

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

1267

1268 def _presults(self, other):

1269 # Yield the result clips, each as a generator

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

1271 for cp in (self, other):

1272 for c in cp._clips:

1273 if c._pushback:

1274 yield c._all()

1275 for c in self._clips:

1276 for X in c._Xings():

1277 yield self._resultX(X)

1278

1279 def _resultX(self, X):

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

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

1282 while v:

1283 v._checked = True

1284 r = v # in P or Q

1285 s = L.Toggle[v._en_ex]

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

1287 while True:

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

1289 yield v

1290 v._checked = True

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

1292 break

1293 if v is r: # full circle

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

1295 if v is not X:

1296 v = v._linked

1297 if v is X:

1298 break

1299

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

1301 # 4) Set entry/exit flags

1302 L, U = _L, self._Union

1303 for c in self._clips:

1304 n, k = c._point2(True)

1305 if n:

1306 f = n

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

1308 t = L.EXIT # first_chain_vertex = True

1309 while True:

1310 if n.isintersection:

1311 b = n._label

1312 if b is L.CROSSING:

1313 n._en_ex = s

1314 s = L.Toggle[s]

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

1316 n._2split = c # see ._splits_xings

1317 elif b is L.CROSSING_D:

1318 n._en_ex = s

1319 if (s is t) ^ U:

1320 n._label = L.CROSSING

1321 t = L.Toggle[t]

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

1323 s = L.Toggle[s]

1324 elif b is L.BOUNCING_D:

1325 n._en_ex = s

1326 if (s is t) ^ U:

1327 n._2xing = True # see ._splits_xings

1328 s = L.Toggle[s]

1329 t = L.Toggle[t]

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

1331 if n is f:

1332 break # PYCHOK attr?

1333 if k:

1334 c._remove2(k)

1335

1336 def _special_cases(self, other):

1337 # 3.5) Check special cases

1338 U = self._Union

1339 for c in self._clips:

1340 if c._noXings(U):

1341 c._noInters = True

1342 if c._all_ON_ON:

1343 c._identical = True

1344 else:

1345 p, _ = c._point2(False)

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

1347 c._pushback = True

1348

1349 def _special_identicals(self, other):

1350 # 3.5) Handle identicals

1351 _u = _Clip._update_all

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

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

1354 if cds: # PYCHOK no cover

1355 for c in self._identicals:

1356 c._update_all()

1357 for v in c._intersections():

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

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

1360 c._pushback = True

1361 break # next c

1362

1363 @property_RO

1364 def _2splits(self):

1365 # Yield all intersections marked C{._2split}

1366 for p in self._intersections():

1367 if p._2split:

1368 # assert isinstance(p._2split, _Clip)

1369 yield p

1370

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

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

1373

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

1375 p1, p2 = p._prev_next2

1376 ap = p1._2A(p, p2)

1377 Pc = p._2split

1378 # assert Pc in P._clips

1379 # assert p in Pc

1380 return ap, Pc._dup(p)

1381

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

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

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

1385 if id_qs:

1386 for p in ps:

1387 q = p._linked

1388 if q and id(q) in id_qs:

1389 yield p, q

1390

1391 L = _L

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

1393 X = L.Toggle[E]

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

1395 ap, pp = _2A_dup2(p, self)

1396 aq, qq = _2A_dup2(q, other)

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

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

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

1400 else:

1401 pp._link(qq)

1402 p._en_ex = q._en_ex = E

1403 pp._en_ex = qq._en_ex = X

1404 p._label = pp._label = \

1405 q._label = qq._label = L.CROSSING

1406

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

1408 p._label = q._label = L.CROSSING

1409

1410 @property_RO

1411 def _2xings(self):

1412 # Yield all intersections marked C{._2xing}

1413 for p in self._intersections():

1414 if p._2xing:

1415 yield p

1416

1417

1418 class _CompositeGH(_CompositeBase):

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

1420 of L{LatLonGH} points, duplicates and intersections

1421 with an other I{composite}.

1422 '''

1423 _LL = LatLonGH

1424 _xtend = False

1425

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

1427 # New L{_CompositeGH}.

1428 if xtend:

1429 self._xtend = True

1430 elif raiser:

1431 self._raiser = True

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

1433

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

1435 **closed_inull_raiser_xtend_eps):

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

1437

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

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

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

1441 S = self

1442 C = self._class(corners, closed_inull_raiser_xtend_eps,

1443 raiser=False, xtend=False)

1444 bt = C._bottom_top_eps2

1445 lr = C._left_right_eps2

1446 # 1. find intersections

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

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

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

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

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

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

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

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

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

1456 s._link(c)

1457

1458 # 2. identify entry/exit intersections

1459 if S._first:

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

1461 for v in S._intersections():

1462 v._entry = s_entry = not s_entry

1463

1464 if C._first:

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

1466 for v in C._intersections():

1467 v._entry = c_entry = not c_entry

1468

1469 # 3. yield the result(s)

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

1471

1472 @property_RO

1473 def _first(self):

1474 # Get the very first vertex of the first clip

1475 for v in self:

1476 return v

1477 return None # PYCHOK no cover

1478

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

1480 # Get the kwds C{dict}.

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

1482

1483 def _presults(self):

1484 # Yield the unchecked intersection(s).

1485 for c in self._clips:

1486 for v in c._intersections():

1487 if not v._checked:

1488 yield self._resultU(v)

1489

1490 def _resultU(self, v):

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

1492 while v and not v._checked:

1493 v._check()

1494 yield v

1495 r = v

1496 e = v._entry

1497 while True:

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

1499 yield v

1500 if v._linked:

1501 break

1502 if v is r:

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

1504 v = v._linked # switch

1505

1506 @property

1507 def xtend(self):

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

1509 '''

1510 return self._xtend

1511

1512 @xtend.setter # PYCHOK setter!

1513 def xtend(self, xtend):

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

1515 '''

1516 self._xtend = bool(xtend)

1517

1518

1519 class _EdgeFHP(object):

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

1521

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

1523 X_OVERLAP = _Enum('Xo', 5)

1524 P_INTERSECT = _Enum('Pi', 3)

1525 P_OVERLAP = _Enum('Po', 7)

1526 Ps = (P_INTERSECT, P_OVERLAP, X_OVERLAP)

1527 Q_INTERSECT = _Enum('Qi', 2)

1528 Q_OVERLAP = _Enum('Qo', 6)

1529 Qs = (Q_INTERSECT, Q_OVERLAP, X_OVERLAP)

1530 V_INTERSECT = _Enum('Vi', 4)

1531 V_OVERLAP = _Enum('Vo', 8)

1532 Vs = (V_INTERSECT, V_OVERLAP)

1533

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

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

1536 self._p1_p2 = p1, p2

1537 self._dp = dp = p2 - p1

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

1539

1540 self._lr, \

1541 self._bt = _left_right_bottom_top_eps2(p1, p2)

1542

1543 def _intersect3(self, q1, q2):

1544 # Yield intersection(s) Type or C{None}

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

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

1547 dq = q2 - q1

1548 dq2 = dq * dq # dot product, hypot2

1549 if dq2 > EPS2: # like ._clip

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

1551 p1, p2 = self._p1_p2

1552 ap1 = p1._2A(q1, q2)

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

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

1555 aq1 = q1._2A(p1, p2)

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

1557 if fabs(aq2_1) > _0_EPS:

1558 # compute and classify alpha and beta

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

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

1561 # distinguish intersection types

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

1563 E.P_INTERSECT if a_0_1 and b_0 else (

1564 E.Q_INTERSECT if a_0 and b_0_1 else (

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

1566

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

1568 dp = self._dp

1569 d1 = q1 - p1

1570 # compute and classify alpha and beta

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

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

1573 # distinguish overlap type

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

1575 E.P_OVERLAP if a_0_1 and _b_0_1 else (

1576 E.Q_OVERLAP if _a_0_1 and b_0_1 else (

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

1578

1579 if T:

1580 if T is E.X_INTERSECT:

1581 v = p1 + a * self._dp

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

1583 elif T in E.Vs:

1584 yield T, (p1,), (q1,)

1585 else:

1586 if T in E.Qs:

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

1588 if T in E.Ps:

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

1590

1591

1592 class _EdgeGH(object):

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

1594

1595 _raiser = False

1596 _xtend = False

1597

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

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

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

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

1602 s1.y, s2.y - s1.y)

1603 self._lr, \

1604 self._bt = _left_right_bottom_top_eps2(s1, s2)

1605

1606 if xtend:

1607 self._xtend = True

1608 elif raiser:

1609 self._raiser = True

1610

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

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

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

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

1615 return a, fabs(d)

1616

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

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

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

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

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

1622

1623 @Property_RO

1624 def _hypot0(self):

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

1626 return hypot(sx, sy) * _0_EPS

1627

1628 @Property_RO

1629 def _hypot2(self):

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

1631 return hypot2(sx, sy)

1632

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

1634 # Yield the intersection(s) of this and another edge.

1635

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

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

1638 # coordinates x and y and both alphas.

1639

1640 # @raise ClipError: Intersection unhandled.

1641

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

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

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

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

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

1647 x, sx, \

1648 y, sy = self._x_sx_y_sy

1649

1650 cx = c2.x - c1_x

1651 cy = c2.y - c1_y

1652 d = cy * sx - cx * sy

1653

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

1655 dx = x - c1_x

1656 dy = y - c1_y

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

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

1659 _EPS_0 < ca < _1_EPS):

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

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

1662 _EPS_0 < sa < _1_EPS):

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

1664

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

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

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

1668

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

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

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

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

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

1674

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

1676 # non-null, parallel or colinear edges

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

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

1679 if max(d1, d2) < _0_EPS:

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

1681 if sa1 > sa2: # anti-parallel

1682 sa1, sa2 = sa2, sa1

1683 ca1, ca2 = _1_0, _0_0

1684 else: # parallel

1685 ca1, ca2 = _0_0, _1_0

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

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

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

1689 ca *= ca1 + sa1

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

1691 else: # c1 is between s1 and s2

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

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

1694 ca *= sa2 - _1_0

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

1696 else: # c2 is between s1 and s2

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

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

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

1700

1701

1702 class _BooleanBase(object):

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

1704

1705 def __add__(self, other):

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

1707 '''

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

1709

1710 def __and__(self, other):

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

1712 '''

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

1714

1715 def __iadd__(self, other):

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

1717 '''

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

1719

1720 def __iand__(self, other):

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

1722 '''

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

1724

1725 def __ior__(self, other):

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

1727 '''

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

1729

1730 def __or__(self, other):

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

1732 '''

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

1734

1735 def __radd__(self, other):

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

1737 '''

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

1739

1740 def __rand__(self, other):

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

1742 '''

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

1744

1745 def __ror__(self, other):

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

1747 '''

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

1749

1750 def _boolean4(self, other, op):

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

1752 C = self.__class__

1753 kwds = C._kwds(self, op)

1754 a = C(self, **kwds)

1755 b = _other(self, other)

1756 return a, b, C, kwds

1757

1758 def _inplace(self, r):

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

1760 self._clips, r._clips = r._clips, None

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

1762# self._raiser = r._raiser

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

1764# self._xtend = r._xtend

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

1766# self._eps = r._eps

1767 return self

1768

1769

1770 class BooleanFHP(_CompositeFHP, _BooleanBase):

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

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

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

1774 to pure Python.

1775

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

1777

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

1779

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

1781

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

1783

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

1785

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

1787

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

1789 and class L{BooleanGH}.

1790 '''

1791 _kind = _boolean_

1792

1793 def __init__(self, lls, raiser=False, eps=EPS, **name):

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

1795

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

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

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

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

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

1801 @kwarg name: Optional C{B{name}=NN} (C{str}).

1802 '''

1803 _CompositeFHP.__init__(self, lls, raiser=raiser, eps=eps, **name)

1804

1805 def __isub__(self, other):

1806 '''Not implemented.'''

1807 return _NotImplemented(self, other)

1808

1809 def __rsub__(self, other):

1810 '''Not implemented.'''

1811 return _NotImplemented(self, other)

1812

1813 def __sub__(self, other):

1814 '''Not implemented.'''

1815 return _NotImplemented(self, other)

1816

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

1818 # One C{BooleanFHP} operation.

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

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

1821 return C(r, **kwds)

1822

1823

1824 class BooleanGH(_CompositeGH, _BooleanBase):

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

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

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

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

1829 modified and extended.

1830

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

1832

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

1834

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

1836

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

1838

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

1840

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

1842

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

1844

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

1846

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

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

1849

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

1851 and class L{BooleanFHP}.

1852 '''

1853 _kind = _boolean_

1854

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

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

1857

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

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

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

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

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

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

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

1865 @kwarg name: Optional C{B{name}=NN} (C{str}).

1866 '''

1867 _CompositeGH.__init__(self, lls, raiser=raiser, xtend=xtend, eps=eps, **name)

1868

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

1870 # One C{BooleanGH} operation.

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

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

1873 return C(r, **kwds)

1874

1875 def __isub__(self, other):

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

1877 '''

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

1879

1880 def __rsub__(self, other):

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

1882 '''

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

1884

1885 def __sub__(self, other):

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

1887 '''

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

1889

1890

1891 def _alpha1(alpha):

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

1893 if _EPS_0 < alpha < _1_EPS:

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

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

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

1897

1898

1899 def _alpha4(a):

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

1901 # 0 < alpha < 1,

1902 # not 0 < alpha < 1)

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

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

1905 (a, True, False, False))

1906

1907

1908 def _Cps(Cp, composites_points, where):

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

1910 try:

1911 kwds = dict(kind=_points_, name__=where)

1912 for cp in composites_points:

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

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

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

1916

1917

1918 def _eps0(eps):

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

1920 return eps if eps and eps > EPS else 0

1921

1922

1923 def isBoolean(obj):

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

1925

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

1927

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

1929 or some other composite, C{False} otherwise.

1930 '''

1931 return isinstance(obj, _CompositeBase)

1932

1933

1934 def _left_right_bottom_top_eps2(p1, p2):

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

1936 '''

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

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

1939

1940

1941 def _low_high_eps2(lo, hi, eps):

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

1943 '''

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

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

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

1947

1948

1949 def _min_max_eps2(*xs):

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

1951 '''

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

1953 lo *= _1_EPS if lo < 0 else _EPS_1

1954 hi *= _EPS_1 if hi < 0 else _1_EPS

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

1956

1957

1958 def _other(this, other):

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

1960 '''

1961 C = this.__class__

1962 if isinstance(other, C):

1963 return other

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

1965

1966

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

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

1969 '''

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

1971

1972

1973__all__ += _ALL_DOCS(_BooleanBase, _Clip,

1974 _CompositeBase, _CompositeFHP, _CompositeGH,

1975 _LatLonBool)

1976

1977# **) MIT License

1978#

1979# Copyright (C) 2018-2024 -- mrJean1 at Gmail -- All Rights Reserved.

1980#

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

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

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

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

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

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

1987#

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

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

1990#

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

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

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

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

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

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

1997# OTHER DEALINGS IN THE SOFTWARE.

1998

1999# ***) GNU GPL 3

2000#

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

2002#

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

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

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

2006# the License, or any later version.

2007#

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

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

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

2011# GNU General Public License for more details.

2012#

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

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

2015#

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

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