Coverage for pygeodesy/booleans.py: 94%

959 statements  

« prev     ^ index     » next       coverage.py v7.2.2, created at 2023-03-31 10:52 -0400

1 

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

3 

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

5 

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

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

8C{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 

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

19 

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

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

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

23 _xkwds_get 

24from pygeodesy.fmath import fabs, favg, hypot, hypot2 

25# from pygeodesy.fsums import fsum1 # from _MODS 

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

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

28 _height_, _lat_,_LatLon_, _lon_, _name_, \ 

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

30 _B_, _d_, _R_ # PYCHOK used! 

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

32# from pygeodesy.latlonBase import LatLonBase # from _MODS 

33from pygeodesy.named import Fmt, _Named, _NotImplemented, pairs 

34# from pygeodesy.points import boundsOf # from _MODS 

35from pygeodesy.props import Property_RO, property_RO 

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

37from pygeodesy.units import Height, HeightX 

38 

39# from math import fabs # from .fmath 

40 

41__all__ = _ALL_LAZY.booleans 

42__version__ = '23.03.31' 

43 

44_0_EPS = EPS # near-zero, positive 

45_EPS_0 = -EPS # near-zero, negative 

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

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

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

49 

50_alpha_ = 'alpha' 

51_boolean_ = 'boolean' 

52_case_ = 'case' 

53_corners_ = 'corners' 

54_duplicate_ = 'duplicate' 

55_open_ = 'open' 

56 

57 

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

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

60 

61 

62class _L(object): # Intersection labels 

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

64 CROSSING_D = _Enum(_X_ + _d_, 8) 

65 CROSSINGs = (CROSSING, CROSSING_D) 

66 BOUNCING = _Enum(_B_, 2) 

67 BOUNCING_D = _Enum(_B_ + _d_, 9) 

68 BOUNCINGs = (BOUNCING, BOUNCING_D) + CROSSINGs 

69 LEFT_ON = _Enum('Lo', 3) 

70 ON_ON = _Enum('oo', 5) 

71 ON_LEFT = _Enum('oL', 6) 

72 ON_RIGHT = _Enum('oR', 7) 

73 RIGHT_ON = _Enum('Ro', 4) 

74 RIGHT_LEFT_ON = (RIGHT_ON, LEFT_ON) 

75 # Entry/Exit flags 

76 ENTRY = _Enum(_e_, 1) 

77 EXIT = _Enum(_x_, 0) 

78 Toggle = {ENTRY: EXIT, 

79 EXIT: ENTRY, 

80 None: None} 

81 

82_L = _L() # PYCHOK singleton 

83 

84 

85class _RP(object): # RelativePositions 

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

87 IS_Pp = _Enum('Pp', 3) 

88 LEFT = _Enum('L', 0) 

89 RIGHT = _Enum(_R_, 1) 

90 

91_RP = _RP() # PYCHOK singleton 

92 

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

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

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

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

97 # overlapping cases 

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

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

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

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

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

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

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

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

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

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

108 

109 

110def _alpha1(alpha): 

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

112 if _EPS_0 < alpha < _1_EPS: 

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

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

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

116 

117 

118def _alpha4(a): 

119 # Return 4-tuple (alpha, abs(alpha) near 0, 0 < alpha < 1, not 0 < alpha < 1) 

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

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

122 (a, True, False, False)) 

123 

124 

125def _eps0(eps): 

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

127 return eps if eps and eps > EPS else 0 

128 

129 

130def _left_right_bottom_top_eps2(p1, p2): 

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

132 ''' 

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

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

135 

136 

137def _low_high_eps2(lo, hi, eps): 

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

139 ''' 

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

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

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

143 

144 

145def _min_max_eps2(*xs): 

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

147 ''' 

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

149 lo *= _1_EPS if lo < 0 else _EPS_1 

150 hi *= _EPS_1 if hi < 0 else _1_EPS 

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

152 

153 

154def _other(this, other): 

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

156 ''' 

157 C = this.__class__ 

158 if isinstance(other, C): 

159 return other 

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

161 

162 

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

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

165 ''' 

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

167 

168 

169class _LatLonBool(_Named): 

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

171 ''' 

172 _alpha = None # point AND intersection else length 

173 _checked = False # checked in phase 3 iff intersection 

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

175 _dupof = None # original of a duplicate 

176# _e_x_str = NN # shut up PyChecker 

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

178 _linked = None # link to neighbor iff intersection 

179 _next = None # link to the next vertex 

180 _prev = None # link to the previous vertex 

181 

182 def __init__(self, lat_ll, lon=None, height=0, clipid=INT0, name=NN): 

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

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

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

186 

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

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

189 or some other C{LatLon}). 

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

191 scalar, ignored otherwise. 

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

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

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

195 ''' 

196 if lon is None: 

197 self.y, self.x = lat_ll.lat, lat_ll.lon 

198 h = getattr(lat_ll, _height_, height) 

199 c = getattr(lat_ll, _clipid_, clipid) 

200 else: 

201 self.y, self.x = lat_ll, lon 

202 h, c = height, clipid 

203 # don't duplicate defaults 

204 if self._height != h: 

205 self._height = h 

206 if self._clipid != c: 

207 self._clipid = c 

208 if name: 

209 self.name = name 

210 

211 def __abs__(self): 

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

213 

214 def __eq__(self, other): 

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

216 other.x == self.x and 

217 other.y == self.y) 

218 

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

220 return not self.__eq__(other) 

221 

222 def __repr__(self): 

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

224 ''' 

225 if self._prev or self._next: 

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

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

228 else: 

229 t = str(self) 

230 return t 

231 

232 def __str__(self): 

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

234 ''' 

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

236 if self._height: 

237 X = _X_ if self.isintersection else NN 

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

239 if self._clipid: 

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

241 if self._alpha is not None: 

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

243# if self._dupof: # recursion risk 

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

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

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

247 if self._linked: 

248 k = _DOT_ if self._checked else _BANG_ 

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

250 return NN(self.name, t) 

251 

252 def __sub__(self, other): 

253 _other(self, other) 

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

255 self.x - other.x) 

256 

257 def _2A(self, p2, p3): 

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

259 x, y = self.x, self.y 

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

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

262 

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

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

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

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

267 return 0 if a < eps else a 

268 

269 @property_RO 

270 def clipid(self): 

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

272 ''' 

273 return self._clipid 

274 

275 def _equi(self, llb, eps): 

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

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

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

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

280 

281 @property_RO 

282 def height(self): 

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

284 ''' 

285 h = self._height 

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

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

288 

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

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

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

292 

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

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

295 

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

297 

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

299 ''' 

300 try: 

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

302 except (AttributeError, TypeError, ValueError): 

303 raise _IsnotError(_LatLon_, other=other) 

304 

305 @property_RO 

306 def isintersection(self): 

307 '''Is this an intersection? 

308 ''' 

309 return bool(self._linked) 

310 

311 @property_RO 

312 def ispoint(self): 

313 '''Is this an original (boolean) point? 

314 ''' 

315 return self._alpha is None 

316 

317 @property_RO 

318 def lat(self): 

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

320 ''' 

321 return self.y 

322 

323 def _link(self, other): 

324 # Make this and an other point are neighbors. 

325 # assert _other(self, other) 

326 self._linked = other 

327 other._linked = self 

328 

329 @property_RO 

330 def lon(self): 

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

332 ''' 

333 return self.x 

334 

335 def _toClas(self, Clas, clipid): 

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

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

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

339 

340 

341class LatLonFHP(_LatLonBool): 

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

343 ''' 

344 _en_ex = None 

345 _label = None 

346 _2split = None # or C{._Clip} 

347 _2xing = False 

348 

349 def __init__(self, lat_ll, *lon_h_clipid, **name): 

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

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

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

353 

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

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

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

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

358 ignored otherwise. 

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

360 ''' 

361 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **name) 

362 

363 def __add__(self, other): 

364 _other(self, other) 

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

366 

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

368 _other(self, other) 

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

370 

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

372 _other(self, other) 

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

374 

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

376 if not isscalar(other): 

377 raise _IsnotError(_scalar_, other=other) 

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

379 

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

381 if self._label: 

382 t = NN(self._label, t) 

383 if self._en_ex: 

384 t = NN(t, self._en_ex) 

385 return t 

386 

387 @property_RO 

388 def _isduplicate(self): 

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

390 p = self._dupof 

391 return bool(p and self._linked 

392 and p is not self 

393 and p == self 

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

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

396 

397# @property_RO 

398# def _isduplicated(self): 

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

400# d, v = 0, self 

401# while v: 

402# if v._dupof is self: 

403# d += 1 

404# v = v._next 

405# if v is self: 

406# break 

407# return d 

408 

409 def _isinside(self, composite, *excludes): 

410 # Is this point inside a composite, 

411 # excluding certain C{_Clip}s. 

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

413 for c in composite._clips: 

414 if c not in excludes: 

415 w = 0 

416 for p1, p2 in c._edges2(): 

417 # edge [p1,p2] must straddle y 

418 if (p1.y < y) is not (p2.y < y): 

419 r = p2.x > x 

420 s = p2.y > p1.y 

421 if p1.x < x: 

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

423 else: 

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

425 if b: 

426 w += 1 if s else -1 

427 if isodd(w): 

428 i = not i 

429 return i 

430 

431 def isinside(self, *composites): 

432 '''Is this point inside B{{composites}} based on C{winding number}? 

433 

434 @arg composites: One or more iterables or I{composites} of clips 

435 or points (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, 

436 L{LatLonFHP}, L{LatLonGH}, L{LatLon_} or any 

437 other C{LatLon}). 

438 

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

440 article/pii/S0925772101000128>}. 

441 ''' 

442 self._isinside(_CompositeEdges(self.__class__, composites)) 

443 

444 @property_RO 

445 def isintersection(self): 

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

447 ''' 

448 return bool(self._linked) 

449 

450 @property_RO 

451 def ispoint(self): 

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

453 ''' 

454 return self._alpha is None 

455 

456 @property_RO 

457 def _prev_next2(self): 

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

459 p, n = self, self._next 

460 if self._isduplicate: 

461 p = self._dupof 

462 while p._isduplicate: 

463 p = p._dupof 

464 while n._isduplicate: 

465 n = n._next 

466 return p._prev, n 

467 

468# def _edge2(self): 

469# # Return the start and end point of the 

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

471# n = p = self 

472# while p.isintersection: 

473# p = p._prev 

474# if p is self: 

475# break 

476# while n.isintersection: 

477# n = n._next 

478# if n is self: 

479# break 

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

481# return p, n 

482 

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

484 # Relative Position oracle 

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

486 T = _RP.IS_Pm 

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

488 T = _RP.IS_Pp 

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

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

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

492 _RP.RIGHT # PYCHOK indent 

493 else: # right turn (or straight) 

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

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

496 _RP.LEFT # PYCHOK indent 

497 return T 

498 

499 

500class LatLonGH(_LatLonBool): 

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

502 ''' 

503 _entry = None # entry or exit iff intersection 

504 _extend = False 

505 

506 def __init__(self, lat_ll, *lon_h_clipid, **name): 

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

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

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

510 

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

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

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

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

515 ignored otherwise. 

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

517 ''' 

518 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **name) 

519 

520 def _check(self): 

521 # Check-mark this vertex and its link. 

522 self._checked = True 

523 k = self._linked 

524 if k and not k._checked: 

525 k._checked = True 

526 

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

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

529 (_e_ if self._entry else _x_)) 

530 

531 def _isinside(self, composite, *bottom_top): 

532 # Is this vertex inside the composite? I{Odd-even rule}. 

533 

534 def _x(y, p1, p2): 

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

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

537 

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

539 # intersecting a ray emitted East-bound from this 

540 # point to infinity. When I{odd} this point lies 

541 # inside, if I{even} outside. 

542 i, y = False, self.y 

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

544 x = self.x 

545 for p1, p2, _ in composite._edges3(): 

546 if (p1.y < y) is not (p2.y < y): 

547 r = p2.x > x 

548 if p1.x < x: 

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

550 else: 

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

552 if b: 

553 i = not i 

554 return i 

555 

556 def isinside(self, *composites): 

557 '''Is this point inside B{C{composites}} based on C{odd-even rule}? 

558 

559 @arg composites: One or more iterables or I{composites} of clips 

560 or points (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, 

561 L{LatLonFHP}, L{LatLonGH}, L{LatLon_} or any 

562 other C{LatLon}). 

563 ''' 

564 self._isinside(_CompositeEdges(self.__class__, composites)) 

565 

566 

567class _Clip(_Named): 

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

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

570 and intersections with other clips. 

571 ''' 

572 _composite = None 

573 _dups = 0 

574 _first = None 

575 _id = 0 

576 _identical = False 

577 _noInters = False 

578 _last = None 

579 _LL = None 

580 _len = 0 

581 _pushback = False 

582 

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

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

585 ''' 

586 # assert isinstance(composite, _CompositeBase) 

587 if clipid in composite._clipids: 

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

589 self._composite = composite 

590 self._id = clipid 

591 self._LL = composite._LL 

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

593 

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

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

596 ''' 

597 for v in self: 

598 if v is point: # or ==? 

599 return True 

600 return False 

601 

602 def __eq__(self, other): 

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

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

605 the same order, possibly rotated? 

606 ''' 

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

608 

609 def __ge__(self, other): 

610 '''See method C{__lt__}. 

611 ''' 

612 return not self.__lt__(other) 

613 

614 def __gt__(self, other): 

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

616 located or stretched farther North or East? 

617 ''' 

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

619 

620 def __hash__(self): # PYCHOK no over 

621 return hash(self._bltr4) 

622 

623 def __iter__(self): 

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

625 ''' 

626 v = f = self._first 

627 while v: 

628 yield v 

629 v = v._next 

630 if v is f: 

631 break 

632 

633 def __le__(self, other): 

634 '''See method C{__gt__}. 

635 ''' 

636 return not self.__gt__(other) 

637 

638 def __len__(self): 

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

640 intersections in this clip. 

641 ''' 

642 return self._len 

643 

644 def __lt__(self, other): 

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

646 located or stretched farther South or West? 

647 ''' 

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

649 

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

651 '''See method C{__eq__}. 

652 ''' 

653 return not self.__eq__(other) 

654 

655 _all = __iter__ 

656 

657 @property_RO 

658 def _all_ON_ON(self): 

659 # Check whether all vertices are ON_ON. 

660 L_ON_ON = _L.ON_ON 

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

662 

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

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

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

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

667 self._len += 1 

668 # assert v._clipid == self._id 

669 

670 v._next = n = self._first 

671 if n is None: # set ._first 

672 self._first = p = n = v 

673 else: # insert before ._first 

674 v._prev = p = n._prev 

675 p._next = n._prev = v 

676 return v 

677 

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

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

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

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

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

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

684# if v._linked: 

685# p._linked = True # to force errors 

686# return p 

687 

688 @Property_RO 

689 def _bltr4(self): 

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

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

692 

693 def _bltr4eps(self, eps): 

694 # Get the bounds ._bltr4 tuple, oversized. 

695 if eps > 0: # > EPS 

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

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

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

699 t = yb, xl, yt, xr 

700 else: 

701 t = self._bltr4 

702 return t 

703 

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

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

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

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

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

709 # un-close the clip 

710 f._prev = p = p._prev 

711 p._next = f 

712 self._len -= 1 

713# elif f and raiser: 

714# raise self._OpenClipError(p, f) 

715 if len(self) < 3: 

716 raise self._Error(_too_(_few_)) 

717 

718 def _dup(self, q): 

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

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

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

722 v._dupof = q._dupof or q 

723 # assert v._prev is q 

724 # assert q._next is v 

725 return v 

726 

727 def _edges2(self, **unused): 

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

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

730 p1 = p2 = f = self._first 

731 while p2: 

732 p2 = p2._next 

733 if p2.ispoint: 

734 yield p1, p2 

735 p1 = p2 

736 if p2 is f: 

737 break 

738 

739 def _equi(self, clip, eps): 

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

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

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

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

744 == clip._bltr4eps(eps): 

745 _equi = _LatLonBool._equi 

746 for v in clip: 

747 if _equi(f, v, eps): 

748 s, n = f, v 

749 for _ in range(r): 

750 s, n = s._next, n._next 

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

752 break # next v 

753 else: # equivalent 

754 return True 

755 return False 

756 

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

758 # Build a C{ClipError} instance 

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

760 if self._dups: 

761 kwds.update(dups=self._dups) 

762 cp = self._composite 

763 if self._id: 

764 try: 

765 i = cp._clips.index(self) 

766 if i != self._id: 

767 kwds[_clip_] = i 

768 except ValueError: 

769 pass 

770 kwds[_clipid_] = self._id 

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

772 

773 def _index(self, clips, eps): 

774 # see _CompositeBase._equi 

775 for i, c in enumerate(clips): 

776 if c._equi(self, eps): 

777 return i 

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

779 

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

781 # insertVertex between points C{start} and 

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

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

784 n = start._next 

785 if end_alpha: 

786 end, alpha = end_alpha 

787 v._alpha = alpha 

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

789 # assert start is not end 

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

791 n = n._next 

792 v._next = n 

793 v._prev = p = n._prev 

794 p._next = n._prev = v 

795 self._len += 1 

796# _Clip._bltr4._update(self) 

797# _Clip._ishole._update(self) 

798 return v 

799 

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

801 # insert an intersection or make a point both 

802 if p1_p2_alpha: # intersection on edge 

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

804 else: # intersection at point 

805 v = q 

806 # assert not v._linked 

807 # assert v._alpha is None 

808 return v 

809 

810 def _intersections(self): 

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

812 for v in self: 

813 if v.isintersection: 

814 yield v 

815 

816 @Property_RO 

817 def _ishole(self): # PYCHOK no cover 

818 # Is this clip a hole inside its composite? 

819 v = self._first 

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

821 

822 @property_RO 

823 def _nodups(self): 

824 # Yield all non-duplicates. 

825 for v in self: 

826 if not v._dupof: 

827 yield v 

828 

829 def _noXings(self, Union): 

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

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

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

833 

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

835 # Return a C{CloseError} instance 

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

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

838 

839 def _point2(self, insert): 

840 # getNonIntersectionPoint and -Vertex 

841 if not (insert and self._noInters): 

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

843 return p, None 

844 for n in self._intersections(): 

845 p, _ = n._prev_next2 

846 k = p._linked 

847 if k: 

848 if n._linked not in k._prev_next2: 

849 # create a pseudo-point 

850 k = _0_5 * (p + n) 

851 if insert: 

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

853 r = k # to remove later 

854 else: # no ._prev, ._next 

855 k._clipid = n._clipid 

856 r = None 

857 return k, r 

858 return None, None 

859 

860 def _points(self, may_be=True): 

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

862 for v in self: 

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

864 yield v 

865 

866 def _remove2(self, v): 

867 # Remove vertex C{v}. 

868 # assert not v._isduplicated 

869 if len(self) > 1: 

870 p = v._prev 

871 p._next = n = v._next 

872 n._prev = p 

873 if self._first is v: 

874 self._first = n 

875 if self._last is v: 

876 self._last = p 

877 self._len -= 1 

878 else: 

879 n = self._last = \ 

880 p = self._first = None 

881 self._len = 0 

882 return p, n 

883 

884 def _update_all(self): # PYCHOK no cover 

885 # Zap the I{cached} properties. 

886 _Clip._bltr4._update( self) 

887 _Clip._ishole._update(self) 

888 return self # for _special_identicals 

889 

890 def _Xings(self): 

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

892 CROSSING = _L.CROSSING 

893 for v in self._intersections(): 

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

895 yield v 

896 

897 

898class _ClipEdges(_Clip): # PYCHOK no cover 

899 # Wrapper yielding edges, eliminating 

900 # null edges and adding closing edge. 

901 

902 def __init__(self, cps, LL): # PYCHOK signature 

903 self._cps = cps # _CompositeEdges 

904 self._LL = LL 

905 

906 def _edges2(self, *unused): # PYCHOK signature 

907 # Yield each edge as a C{LatLon[FHP|GH]} point pair. 

908 for cp in self._cps: 

909 self._composite = cp 

910 p2 = s = None 

911 for ll in cp: 

912 p1, p2 = p2, self._LL(ll) 

913 if s is None: 

914 s = p1 = p2 

915 elif p1._clipid != p2._clipid: 

916 if p1 != s: 

917 yield p1, s 

918 s = p1 = p2 

919 elif p1 != p2: 

920 yield p1, p2 

921 self._id = p2._clipid 

922 if p1 != s: 

923 yield p1, s 

924 

925 

926class _CompositeBase(_Named): 

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

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

929 ''' 

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

931 _eps = EPS # null edges 

932 _kind = _corners_ 

933 _LL = _LatLonBool # shut up PyChecker 

934 _raiser = False 

935 _xtend = False 

936 

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

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

939 ''' 

940 n = name or getattr(lls, _name_, NN) 

941 if n: 

942 self.name = n 

943 if kind: 

944 self._kind = kind 

945 if self._eps < eps: 

946 self._eps = eps 

947 

948 c = _Clip(self) 

949 lp = None 

950 for ll in lls: 

951 ll = self._LL(ll) 

952 if lp is None: 

953 c._id = ll._clipid # keep clipid 

954 lp = c._append(ll) 

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

956 c._closed(self.raiser) 

957 c = _Clip(self, ll._clipid) 

958 lp = c._append(ll) 

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

960 lp = c._append(ll) 

961 else: 

962 c._dups += 1 

963 c._closed(self.raiser) 

964 

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

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

967 ''' 

968 for c in self._clips: 

969 if point in c: 

970 return True 

971 return False 

972 

973 def __eq__(self, other): 

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

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

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

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

978 possibly rotated. 

979 ''' 

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

981 

982 def __iter__(self): 

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

984 ''' 

985 for c in self._clips: 

986 for v in c: 

987 yield v 

988 

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

990 '''See method C{__eq__}. 

991 ''' 

992 return not self.__eq__(other) 

993 

994 def __len__(self): 

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

996 ''' 

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

998 

999 def __repr__(self): 

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

1001 ''' 

1002 c = len(self._clips) 

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

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

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

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

1007 

1008 def __str__(self): 

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

1010 ''' 

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

1012 

1013 @property_RO 

1014 def _bottom_top_eps2(self): 

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

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

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

1018 

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

1020 # Return a new instance 

1021 _g = kwds.get 

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

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

1024 

1025 @property_RO 

1026 def _clipids(self): # PYCHOK no cover 

1027 for c in self._clips: 

1028 yield c._id 

1029 

1030 def clipids(self): 

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

1032 ''' 

1033 return tuple(self._clipids) 

1034 

1035# def _clipidups(self, other): 

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

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

1038 

1039 def _edges3(self, **raiser): 

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

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

1042 for c in self._clips: 

1043 for p1, p2 in c._edges2(**raiser): 

1044 yield p1, p2, c 

1045 

1046 def _encloses(self, lat, lon): 

1047 # see function .points.isenclosedBy 

1048 return self._LL(lat, lon)._isinside(self) 

1049 

1050 @property 

1051 def eps(self): 

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

1053 ''' 

1054 return self._eps 

1055 

1056 @eps.setter # PYCHOK setter! 

1057 def eps(self, eps): 

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

1059 ''' 

1060 self._eps = eps 

1061 

1062 def _10eps(self, **eps): 

1063 # Get eps for _LatLonBool._2Abs 

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

1065 if e != EPS: 

1066 e *= _10EPS / EPS 

1067 else: 

1068 e = _10EPS 

1069 return e 

1070 

1071 def _equi(self, other, eps): 

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

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

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

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

1076 if eps > 0: 

1077 _index = _Clip._index 

1078 else: 

1079 def _index(c, cs, unused): 

1080 return cs.index(c) 

1081 try: 

1082 cs = list(sorted(cs)) 

1083 for c in sorted(co): 

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

1085 except ValueError: # from ._index 

1086 pass 

1087 return False if cs else True 

1088 else: # both null? 

1089 return False if cs or co else True 

1090 

1091 def _intersections(self): 

1092 # Yield all intersections. 

1093 for c in self._clips: 

1094 for v in c._intersections(): 

1095 yield v 

1096 

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

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

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

1100 

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

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

1103 

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

1105 

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

1107 

1108 @see: Method C{__eq__}. 

1109 ''' 

1110 if isinstance(other, _CompositeBase): 

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

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

1113 

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

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

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

1117 name=self.name or op.__name__) 

1118 kwds.update(more) 

1119 return kwds 

1120 

1121 @property_RO 

1122 def _left_right_eps2(self): 

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

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

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

1126 

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

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

1129 for c in self._clips: 

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

1131 yield v 

1132 

1133 @property 

1134 def raiser(self): 

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

1136 ''' 

1137 return self._raiser 

1138 

1139 @raiser.setter # PYCHOK setter! 

1140 def raiser(self, throw): 

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

1142 ''' 

1143 self._raiser = bool(throw) 

1144 

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

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

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

1148 e = self._10eps(**eps) 

1149 for clipid, ns in enumerate(_presults): 

1150 f = p = v = None 

1151 for n in ns: 

1152 if f is None: 

1153 yield n._toClas(C, clipid) 

1154 f = p = n 

1155 elif v is None: 

1156 v = n # got f, p, v 

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

1158 yield v._toClas(C, clipid) 

1159 p, v = v, n 

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

1161 v = n 

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

1163 yield v._toClas(C, clipid) 

1164 p = v 

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

1166 yield f._toClas(C, clipid) 

1167 

1168 def _sum(self, other, op): 

1169 # Combine this and an C{other} composite 

1170 LL = self._LL 

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

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

1173 for cp in (self, other): 

1174 for c in cp._clips: 

1175 _ap = _Clip(sp, sid)._append 

1176 for v in c._nodups: 

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

1178 sid += 1 

1179 return sp 

1180 

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

1182 # Sum the area or perimeter of all clips 

1183 return _MODS.fsums.fsum1((_a_p(c, *args, **kwds) for c in self._clips), 

1184 floats=True) 

1185 

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

1187 # Sum the area or perimeter of all clips 

1188 

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

1190 for v in clip: 

1191 yield LL(v.lat, v.lon) # datum=Sphere 

1192 

1193 return _MODS.fsums.fsum1((_a_p(_lls(c), *args, **kwds) for c in self._clips), 

1194 floats=True) 

1195 

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

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

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

1199 

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

1201 L{LatLonFHP} or L{LatLonGH}. 

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

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

1204 keyword arguments, ignore if 

1205 C{B{LatLon} is None}. 

1206 

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

1208 

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

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

1211 ''' 

1212 if LatLon is None: 

1213 LL, kwds = self._LL, {} 

1214 elif issubclassof(LatLon, _LatLonBool, 

1215 _MODS.latlonBase.LatLonBase): 

1216 LL, kwds = LatLon, LatLon_kwds 

1217 else: 

1218 raise _TypeError(LatLon=LatLon) 

1219 

1220 for c in self._clips: 

1221 lf, cid = None, c._id 

1222 for v in c._nodups: 

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

1224 ll._height = v.height 

1225 if ll._clipid != cid: 

1226 ll._clipid = cid 

1227 yield ll 

1228 if lf is None: 

1229 lf = ll 

1230 if closed and lf: 

1231 yield lf 

1232 

1233 

1234class _CompositeEdges(_CompositeBase): # PYCHOK no cover 

1235 # Polygon wrapper yielding clips and edges, 

1236 # eliminating duplicates and closing open clips. 

1237 

1238 def __init__(self, LL, composites): # PYCHOK signature 

1239 self._cps = composites 

1240 self._LL = LL 

1241 

1242 @property_RO 

1243 def _clips(self): 

1244 # Use one C{_Clip}. 

1245 return (_ClipEdges(self._cps, self._LL),) 

1246 

1247 

1248class _CompositeFHP(_CompositeBase): 

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

1250 of L{LatLonFHP} points, duplicates and intersections 

1251 with an other I{composite}. 

1252 ''' 

1253 _LL = LatLonFHP 

1254 _Union = False 

1255 

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

1257 # New L{_CompositeFHP}. 

1258 if raiser: 

1259 self._raiser = True 

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

1261 

1262 def _classify(self): 

1263 # 2) Classify intersection chains. 

1264 L = _L 

1265 for v in self._intersections(): 

1266 n, b = v, v._label 

1267 if b in L.RIGHT_LEFT_ON: # next chain 

1268 while True: 

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

1270 n = n._next 

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

1272 break 

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

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

1275 

1276 # 3) Copy labels 

1277 for v in self._intersections(): 

1278 v._linked._label = v._label 

1279 

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

1281 **closed_inull_raiser_eps): 

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

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

1284 P = self 

1285 Q = self._class(corners, closed_inull_raiser_eps, 

1286 eps=P._eps, raiser=False) 

1287 P._Union = Q._Union = Union 

1288 

1289 bt = Q._bottom_top_eps2 

1290 lr = Q._left_right_eps2 

1291 # compute and insert intersections 

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

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

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

1295 e = _EdgeFHP(p1, p2) 

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

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

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

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

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

1301 # assert not p._linked 

1302 # assert not q._linked 

1303 p._link(q) 

1304 

1305 # label and classify intersections 

1306 P._labelize() 

1307 P._classify() 

1308 

1309 # check for special cases 

1310 P._special_cases(Q) 

1311 Q._special_cases(P) 

1312 # handle identicals 

1313 P._special_identicals(Q) 

1314 

1315 # set Entry/Exit flags 

1316 P._set_entry_exits(Q) 

1317 Q._set_entry_exits(P) 

1318 

1319 # handle splits and crossings 

1320 P._splits_xings(Q) 

1321 

1322 # yield the results 

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

1324 

1325 @property_RO 

1326 def _identicals(self): 

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

1328 for c in self._clips: 

1329 if c._identical: 

1330 yield c 

1331 

1332 def _labelize(self): 

1333 # 1) Intersections classification 

1334 for p in self._intersections(): 

1335 q = p._linked 

1336 # determine local configuration at this intersection 

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

1338 p1, p3 = p._prev_next2 

1339 q1, q3 = q._prev_next2 

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

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

1342 # check intersecting and overlapping cases 

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

1344 

1345 def _presults(self, other): 

1346 # Yield the result clips, each as a generator 

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

1348 for cp in (self, other): 

1349 for c in cp._clips: 

1350 if c._pushback: 

1351 yield c._all() 

1352 for c in self._clips: 

1353 for X in c._Xings(): 

1354 yield self._resultX(X) 

1355 

1356 def _resultX(self, X): 

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

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

1359 while v: 

1360 v._checked = True 

1361 r = v # in P or Q 

1362 s = L.Toggle[v._en_ex] 

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

1364 while True: 

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

1366 yield v 

1367 v._checked = True 

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

1369 break 

1370 if v is r: # full circle 

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

1372 if v is not X: 

1373 v = v._linked 

1374 if v is X: 

1375 break 

1376 

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

1378 # 4) Set entry/exit flags 

1379 L, U = _L, self._Union 

1380 for c in self._clips: 

1381 n, k = c._point2(True) 

1382 if n: 

1383 f = n 

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

1385 t = L.EXIT # first_chain_vertex = True 

1386 while True: 

1387 if n.isintersection: 

1388 b = n._label 

1389 if b is L.CROSSING: 

1390 n._en_ex = s 

1391 s = L.Toggle[s] 

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

1393 n._2split = c # see ._splits_xings 

1394 elif b is L.CROSSING_D: 

1395 n._en_ex = s 

1396 if (s is t) ^ U: 

1397 n._label = L.CROSSING 

1398 t = L.Toggle[t] 

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

1400 s = L.Toggle[s] 

1401 elif b is L.BOUNCING_D: 

1402 n._en_ex = s 

1403 if (s is t) ^ U: 

1404 n._2xing = True # see ._splits_xings 

1405 s = L.Toggle[s] 

1406 t = L.Toggle[t] 

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

1408 if n is f: 

1409 break # PYCHOK attr? 

1410 if k: 

1411 c._remove2(k) 

1412 

1413 def _special_cases(self, other): 

1414 # 3.5) Check special cases 

1415 U = self._Union 

1416 for c in self._clips: 

1417 if c._noXings(U): 

1418 c._noInters = True 

1419 if c._all_ON_ON: 

1420 c._identical = True 

1421 else: 

1422 p, _ = c._point2(False) 

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

1424 c._pushback = True 

1425 

1426 def _special_identicals(self, other): 

1427 # 3.5) Handle identicals 

1428 _u = _Clip._update_all 

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

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

1431 if cds: # PYCHOK no cover 

1432 for c in self._identicals: 

1433 c._update_all() 

1434 for v in c._intersections(): 

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

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

1437 c._pushback = True 

1438 break # next c 

1439 

1440 @property_RO 

1441 def _2splits(self): 

1442 # Yield all intersections marked C{._2split} 

1443 for p in self._intersections(): 

1444 if p._2split: 

1445 # assert isinstance(p._2split, _Clip) 

1446 yield p 

1447 

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

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

1450 

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

1452 p1, p2 = p._prev_next2 

1453 ap = p1._2A(p, p2) 

1454 Pc = p._2split 

1455 # assert Pc in P._clips 

1456 # assert p in Pc 

1457 return ap, Pc._dup(p) 

1458 

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

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

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

1462 if id_qs: 

1463 for p in ps: 

1464 q = p._linked 

1465 if q and id(q) in id_qs: 

1466 yield p, q 

1467 

1468 L = _L 

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

1470 X = L.Toggle[E] 

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

1472 ap, pp = _2A_dup2(p, self) 

1473 aq, qq = _2A_dup2(q, other) 

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

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

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

1477 else: 

1478 pp._link(qq) 

1479 p._en_ex = q._en_ex = E 

1480 pp._en_ex = qq._en_ex = X 

1481 p._label = pp._label = \ 

1482 q._label = qq._label = L.CROSSING 

1483 

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

1485 p._label = q._label = L.CROSSING 

1486 

1487 @property_RO 

1488 def _2xings(self): 

1489 # Yield all intersections marked C{._2xing} 

1490 for p in self._intersections(): 

1491 if p._2xing: 

1492 yield p 

1493 

1494 

1495class _CompositeGH(_CompositeBase): 

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

1497 of L{LatLonGH} points, duplicates and intersections 

1498 with an other I{composite}. 

1499 ''' 

1500 _LL = LatLonGH 

1501 _xtend = False 

1502 

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

1504 # New L{_CompositeGH}. 

1505 if xtend: 

1506 self._xtend = True 

1507 elif raiser: 

1508 self._raiser = True 

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

1510 

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

1512 **closed_inull_raiser_xtend_eps): 

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

1514 

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

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

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

1518 S = self 

1519 C = self._class(corners, closed_inull_raiser_xtend_eps, 

1520 raiser=False, xtend=False) 

1521 bt = C._bottom_top_eps2 

1522 lr = C._left_right_eps2 

1523 # 1. find intersections 

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

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

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

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

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

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

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

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

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

1533 s._link(c) 

1534 

1535 # 2. identify entry/exit intersections 

1536 if S._first: 

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

1538 for v in S._intersections(): 

1539 v._entry = s_entry = not s_entry 

1540 

1541 if C._first: 

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

1543 for v in C._intersections(): 

1544 v._entry = c_entry = not c_entry 

1545 

1546 # 3. yield the result(s) 

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

1548 

1549 @property_RO 

1550 def _first(self): 

1551 # Get the very first vertex of the first clip 

1552 for v in self: 

1553 return v 

1554 return None # PYCHOK no cover 

1555 

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

1557 # Get the kwds C{dict}. 

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

1559 

1560 def _presults(self): 

1561 # Yield the unchecked intersection(s). 

1562 for c in self._clips: 

1563 for v in c._intersections(): 

1564 if not v._checked: 

1565 yield self._resultU(v) 

1566 

1567 def _resultU(self, v): 

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

1569 while v and not v._checked: 

1570 v._check() 

1571 yield v 

1572 r = v 

1573 e = v._entry 

1574 while True: 

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

1576 yield v 

1577 if v._linked: 

1578 break 

1579 if v is r: 

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

1581 v = v._linked # switch 

1582 

1583 @property 

1584 def xtend(self): 

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

1586 ''' 

1587 return self._xtend 

1588 

1589 @xtend.setter # PYCHOK setter! 

1590 def xtend(self, xtend): 

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

1592 ''' 

1593 self._xtend = bool(xtend) 

1594 

1595 

1596class _EdgeFHP(object): 

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

1598 

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

1600 X_OVERLAP = _Enum('Xo', 5) 

1601 P_INTERSECT = _Enum('Pi', 3) 

1602 P_OVERLAP = _Enum('Po', 7) 

1603 Ps = (P_INTERSECT, P_OVERLAP, X_OVERLAP) 

1604 Q_INTERSECT = _Enum('Qi', 2) 

1605 Q_OVERLAP = _Enum('Qo', 6) 

1606 Qs = (Q_INTERSECT, Q_OVERLAP, X_OVERLAP) 

1607 V_INTERSECT = _Enum('Vi', 4) 

1608 V_OVERLAP = _Enum('Vo', 8) 

1609 Vs = (V_INTERSECT, V_OVERLAP) 

1610 

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

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

1613 self._p1_p2 = p1, p2 

1614 self._dp = dp = p2 - p1 

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

1616 

1617 self._lr, \ 

1618 self._bt = _left_right_bottom_top_eps2(p1, p2) 

1619 

1620 def _intersect3(self, q1, q2): 

1621 # Return intersection Type or C{None} 

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

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

1624 dq = q2 - q1 

1625 dq2 = dq * dq # dot product, hypot2 

1626 if dq2 > EPS2: # like ._clip 

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

1628 p1, p2 = self._p1_p2 

1629 ap1 = p1._2A(q1, q2) 

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

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

1632 aq1 = q1._2A(p1, p2) 

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

1634 if fabs(aq2_1) > _0_EPS: 

1635 # compute and classify alpha and beta 

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

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

1638 # distinguish intersection types 

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

1640 E.P_INTERSECT if a_0_1 and b_0 else ( 

1641 E.Q_INTERSECT if a_0 and b_0_1 else ( 

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

1643 

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

1645 dp = self._dp 

1646 d1 = q1 - p1 

1647 # compute and classify alpha and beta 

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

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

1650 # distinguish overlap type 

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

1652 E.P_OVERLAP if a_0_1 and _b_0_1 else ( 

1653 E.Q_OVERLAP if _a_0_1 and b_0_1 else ( 

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

1655 

1656 if T: 

1657 if T is E.X_INTERSECT: 

1658 v = p1 + a * self._dp 

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

1660 elif T in E.Vs: 

1661 yield T, (p1,), (q1,) 

1662 else: 

1663 if T in E.Qs: 

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

1665 if T in E.Ps: 

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

1667 

1668 

1669class _EdgeGH(object): 

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

1671 

1672 _raiser = False 

1673 _xtend = False 

1674 

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

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

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

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

1679 s1.y, s2.y - s1.y) 

1680 self._lr, \ 

1681 self._bt = _left_right_bottom_top_eps2(s1, s2) 

1682 

1683 if xtend: 

1684 self._xtend = True 

1685 elif raiser: 

1686 self._raiser = True 

1687 

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

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

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

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

1692 return a, fabs(d) 

1693 

1694 def _error(self, n, c1, c2): # PYCHOK no cover 

1695 t = _SPACE_(self._intersect4.__name__, _EdgeGH(c1, c2)) 

1696 raise ClipError(_case_, n, txt=t) 

1697 

1698 @Property_RO 

1699 def _hypot0(self): 

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

1701 return hypot(sx, sy) * _0_EPS 

1702 

1703 @Property_RO 

1704 def _hypot2(self): 

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

1706 return hypot2(sx, sy) 

1707 

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

1709 # Yield the intersections of this and another edge. 

1710 

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

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

1713 # coordinates x and y and both alphas. 

1714 

1715 # @raise ClipError: Intersection unhandled. 

1716 

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

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

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

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

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

1722 x, sx, \ 

1723 y, sy = self._x_sx_y_sy 

1724 

1725 cx = c2.x - c1_x 

1726 cy = c2.y - c1_y 

1727 d = cy * sx - cx * sy 

1728 

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

1730 dx = x - c1_x 

1731 dy = y - c1_y 

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

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

1734 _EPS_0 < ca < _1_EPS): 

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

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

1737 _EPS_0 < sa < _1_EPS): 

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

1739 

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

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

1742 self._error(1, c1, c2) # intersection at s1 or s2 

1743 

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

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

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

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

1748 self._error(e, c1, c2) 

1749 

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

1751 # non-null, parallel or colinear edges 

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

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

1754 if max(d1, d2) < _0_EPS: 

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

1756 if sa1 > sa2: # anti-parallel 

1757 sa1, sa2 = sa2, sa1 

1758 ca1, ca2 = _1_0, _0_0 

1759 else: # parallel 

1760 ca1, ca2 = _0_0, _1_0 

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

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

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

1764 ca *= ca1 + sa1 

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

1766 else: # c1 is between s1 and s2 

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

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

1769 ca *= sa2 - _1_0 

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

1771 else: # c2 is between s1 and s2 

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

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

1774 self._error(4, c1, c2) 

1775 

1776# def _intersect4(self, c1, c2, **unused): 

1777# # Intersect this and another edge. 

1778# 

1779# # @return: 4-Tuple (x, y, s_alpha, c_alpha) with the 

1780# # intersection point x, y and both alphas. 

1781# 

1782# # @raise ClipError: Intersection unhandled. 

1783# 

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

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

1786# 

1787# if not (_outside(c1.x, c2.x, *self._lr) or 

1788# _outside(c1.y, c2.y, *self._bt)): 

1789# x, sx, \ 

1790# y, sy = self._x_sx_y_sy 

1791# 

1792# cx = c2.x - c1.x 

1793# cy = c2.y - c1.y 

1794# d = cy * sx - cx * sy 

1795# 

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

1797# dx = x - c1.x 

1798# dy = y - c1.y 

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

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

1801# if _0_EPS < ca < _EPS_1: 

1802# if _0_EPS < sa < _EPS_1: 

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

1804# 

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

1806# elif self.raiser and not (sa < _EPS_0 or sa > _1_EPS): 

1807# self._error(1, c1, c2) # insection at s1 or s2 

1808# 

1809# elif self.raiser and not (ca < _EPS_0 or ca > _1_EPS): 

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

1811# self._error(2 if sa < _EPS_0 or sa > _1_EPS else 3, c1, c2) 

1812# 

1813# elif self.raiser and (sx or sy) and (cx or cy): 

1814# # null, parallel or colinear edges 

1815# h = hypot(sx, sy) * _0_EPS 

1816# if min(_perpendicular(c1.x - x, c1.y - y, sx, sy), 

1817# _perpendicular(c2.x - x, c2.y - y, sx, sy)) < h: 

1818# self._error(4, c1, c2) # colinear, overlapping 

1819 

1820 

1821class _BooleanBase(object): 

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

1823 

1824 def __add__(self, other): 

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

1826 ''' 

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

1828 

1829 def __and__(self, other): 

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

1831 ''' 

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

1833 

1834 def __iadd__(self, other): 

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

1836 ''' 

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

1838 

1839 def __iand__(self, other): 

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

1841 ''' 

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

1843 

1844 def __ior__(self, other): 

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

1846 ''' 

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

1848 

1849 def __or__(self, other): 

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

1851 ''' 

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

1853 

1854 def __radd__(self, other): 

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

1856 ''' 

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

1858 

1859 def __rand__(self, other): 

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

1861 ''' 

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

1863 

1864 def __ror__(self, other): 

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

1866 ''' 

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

1868 

1869 def _boolean4(self, other, op): 

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

1871 C = self.__class__ 

1872 kwds = C._kwds(self, op) 

1873 a = C(self, **kwds) 

1874 b = _other(self, other) 

1875 return a, b, C, kwds 

1876 

1877 def _inplace(self, r): 

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

1879 self._clips, r._clips = r._clips, None 

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

1881# self._raiser = r._raiser 

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

1883# self._xtend = r._xtend 

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

1885# self._eps = r._eps 

1886 return self 

1887 

1888 

1889class BooleanFHP(_CompositeFHP, _BooleanBase): 

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

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

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

1893 to pure Python. 

1894 

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

1896 

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

1898 

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

1900 

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

1902 

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

1904 

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

1906 

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

1908 and class L{BooleanGH}. 

1909 ''' 

1910 _kind = _boolean_ 

1911 

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

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

1914 

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

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

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

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

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

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

1921 ''' 

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

1923 eps=eps, name=name) 

1924 

1925 def __isub__(self, other): 

1926 '''Not implemented.''' 

1927 return _NotImplemented(self, other) 

1928 

1929 def __rsub__(self, other): 

1930 '''Not implemented.''' 

1931 return _NotImplemented(self, other) 

1932 

1933 def __sub__(self, other): 

1934 '''Not implemented.''' 

1935 return _NotImplemented(self, other) 

1936 

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

1938 # One C{BooleanFHP} operation. 

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

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

1941 return C(r, **kwds) 

1942 

1943 

1944class BooleanGH(_CompositeGH, _BooleanBase): 

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

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

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

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

1949 modified and extended. 

1950 

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

1952 

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

1954 

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

1956 

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

1958 

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

1960 

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

1962 

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

1964 

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

1966 

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

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

1969 

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

1971 and class L{BooleanFHP}. 

1972 ''' 

1973 _kind = _boolean_ 

1974 

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

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

1977 

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

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

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

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

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

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

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

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

1986 ''' 

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

1988 eps=eps, name=name) 

1989 

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

1991 # One C{BooleanGH} operation. 

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

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

1994 return C(r, **kwds) 

1995 

1996 def __isub__(self, other): 

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

1998 ''' 

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

2000 

2001 def __rsub__(self, other): 

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

2003 ''' 

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

2005 

2006 def __sub__(self, other): 

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

2008 ''' 

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

2010 

2011 

2012def isBoolean(obj): 

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

2014 

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

2016 

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

2018 L{BooleanGH} oe some other composite, 

2019 C{False} otherwise. 

2020 ''' 

2021 return isinstance(obj, _CompositeBase) 

2022 

2023 

2024__all__ += _ALL_DOCS(_BooleanBase, _Clip, 

2025 _CompositeBase, _CompositeFHP, _CompositeGH, 

2026 _LatLonBool) 

2027 

2028# **) MIT License 

2029# 

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

2031# 

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

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

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

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

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

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

2038# 

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

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

2041# 

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

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

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

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

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

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

2048# OTHER DEALINGS IN THE SOFTWARE. 

2049 

2050# ***) GNU GPL 3 

2051# 

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

2053# 

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

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

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

2057# the License, or any later version. 

2058# 

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

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

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

2062# GNU General Public License for more details. 

2063# 

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

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

2066# 

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

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