Coverage for pygeodesy/booleans.py: 94%
959 statements
« prev ^ index » next coverage.py v7.2.2, created at 2023-03-31 10:52 -0400
« prev ^ index » next coverage.py v7.2.2, created at 2023-03-31 10:52 -0400
2# -*- coding: utf-8 -*-
4u'''I{Boolean} operations on I{composite} polygons and I{clip}s.
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}.
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.
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
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
39# from math import fabs # from .fmath
41__all__ = _ALL_LAZY.booleans
42__version__ = '23.03.31'
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
50_alpha_ = 'alpha'
51_boolean_ = 'boolean'
52_case_ = 'case'
53_corners_ = 'corners'
54_duplicate_ = 'duplicate'
55_open_ = 'open'
58def _Enum(txt, enum): # PYCHOK unused
59 return txt # NN(txt, _TILDE_, enum)
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}
82_L = _L() # PYCHOK singleton
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)
91_RP = _RP() # PYCHOK singleton
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}
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)
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))
125def _eps0(eps):
126 # Adjust C{eps} or C{None}.
127 return eps if eps and eps > EPS else 0
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))
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)
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)
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)
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
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
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.
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
211 def __abs__(self):
212 return max(fabs(self.x), fabs(self.y))
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)
219 def __ne__(self, other): # required for Python 2
220 return not self.__eq__(other)
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
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)
252 def __sub__(self, other):
253 _other(self, other)
254 return self.__class__(self.y - other.y, # classof
255 self.x - other.x)
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)
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
269 @property_RO
270 def clipid(self):
271 '''Get the I{clipid} (C{int} or C{0}).
272 '''
273 return self._clipid
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)
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)
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}?
293 @arg other: The other point (C{LatLon}).
294 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).
296 @return: C{True} if equivalent, C{False} otherwise (C{bool}).
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)
305 @property_RO
306 def isintersection(self):
307 '''Is this an intersection?
308 '''
309 return bool(self._linked)
311 @property_RO
312 def ispoint(self):
313 '''Is this an original (boolean) point?
314 '''
315 return self._alpha is None
317 @property_RO
318 def lat(self):
319 '''Get the latitude (C{scalar}).
320 '''
321 return self.y
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
329 @property_RO
330 def lon(self):
331 '''Get the longitude (C{scalar}).
332 '''
333 return self.x
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)
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
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.
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)
363 def __add__(self, other):
364 _other(self, other)
365 return self.__class__(self.y + other.y, self.x + other.x)
367 def __mod__(self, other): # cross product
368 _other(self, other)
369 return self.x * other.y - self.y * other.x
371 def __mul__(self, other): # dot product
372 _other(self, other)
373 return self.x * other.x + self.y * other.y
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)
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
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))
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
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
431 def isinside(self, *composites):
432 '''Is this point inside B{{composites}} based on C{winding number}?
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}).
439 @see: U{Algorithm 6<https://www.ScienceDirect.com/science/
440 article/pii/S0925772101000128>}.
441 '''
442 self._isinside(_CompositeEdges(self.__class__, composites))
444 @property_RO
445 def isintersection(self):
446 '''Is this an intersection? May be C{ispoint} too!
447 '''
448 return bool(self._linked)
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
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
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
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
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
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.
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)
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
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_))
531 def _isinside(self, composite, *bottom_top):
532 # Is this vertex inside the composite? I{Odd-even rule}.
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)
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
556 def isinside(self, *composites):
557 '''Is this point inside B{C{composites}} based on C{odd-even rule}?
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))
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
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,)
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
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)
609 def __ge__(self, other):
610 '''See method C{__lt__}.
611 '''
612 return not self.__lt__(other)
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
620 def __hash__(self): # PYCHOK no over
621 return hash(self._bltr4)
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
633 def __le__(self, other):
634 '''See method C{__gt__}.
635 '''
636 return not self.__gt__(other)
638 def __len__(self):
639 '''Return the number of points, duplicates and
640 intersections in this clip.
641 '''
642 return self._len
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
650 def __ne__(self, other): # required for Python 2
651 '''See method C{__eq__}.
652 '''
653 return not self.__eq__(other)
655 _all = __iter__
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)
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
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
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
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))
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
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_))
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
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
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
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)
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)
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
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
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
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
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
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())
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))
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
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
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
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
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
898class _ClipEdges(_Clip): # PYCHOK no cover
899 # Wrapper yielding edges, eliminating
900 # null edges and adding closing edge.
902 def __init__(self, cps, LL): # PYCHOK signature
903 self._cps = cps # _CompositeEdges
904 self._LL = LL
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
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
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
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)
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
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)
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
989 def __ne__(self, other): # required for Python 2
990 '''See method C{__eq__}.
991 '''
992 return not self.__eq__(other)
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
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)
1008 def __str__(self):
1009 '''String C{str} of this composite.
1010 '''
1011 return _COMMASPACE_.join(map(str, self))
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))
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)
1025 @property_RO
1026 def _clipids(self): # PYCHOK no cover
1027 for c in self._clips:
1028 yield c._id
1030 def clipids(self):
1031 '''Return a tuple with all C{clipid}s, I{ordered}.
1032 '''
1033 return tuple(self._clipids)
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)))
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
1046 def _encloses(self, lat, lon):
1047 # see function .points.isenclosedBy
1048 return self._LL(lat, lon)._isinside(self)
1050 @property
1051 def eps(self):
1052 '''Get the null edges tolerance (C{degrees}, usually).
1053 '''
1054 return self._eps
1056 @eps.setter # PYCHOK setter!
1057 def eps(self, eps):
1058 '''Set the null edges tolerance (C{degrees}, usually).
1059 '''
1060 self._eps = eps
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
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
1091 def _intersections(self):
1092 # Yield all intersections.
1093 for c in self._clips:
1094 for v in c._intersections():
1095 yield v
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?
1101 @arg other: The other boolean/composite (C{Boolean[FHP|GB]}).
1102 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).
1104 @return: C{True} if equivalent, C{False} otherwise (C{bool}).
1106 @raise TypeError: Invalid B{C{other}}.
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)
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
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))
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
1133 @property
1134 def raiser(self):
1135 '''Get the option to throw L{ClipError} exceptions (C{bool}).
1136 '''
1137 return self._raiser
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)
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)
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
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)
1186 def _sum2(self, LL, _a_p, *args, **kwds): # in .sphericalNvector, -Trigonometry
1187 # Sum the area or perimeter of all clips
1189 def _lls(clip): # convert clip to LLs
1190 for v in clip:
1191 yield LL(v.lat, v.lon) # datum=Sphere
1193 return _MODS.fsums.fsum1((_a_p(_lls(c), *args, **kwds) for c in self._clips),
1194 floats=True)
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}}.
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}.
1207 @raise TypeError: Invalid B{C{LatLon}}.
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)
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
1234class _CompositeEdges(_CompositeBase): # PYCHOK no cover
1235 # Polygon wrapper yielding clips and edges,
1236 # eliminating duplicates and closing open clips.
1238 def __init__(self, LL, composites): # PYCHOK signature
1239 self._cps = composites
1240 self._LL = LL
1242 @property_RO
1243 def _clips(self):
1244 # Use one C{_Clip}.
1245 return (_ClipEdges(self._cps, self._LL),)
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
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)
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
1276 # 3) Copy labels
1277 for v in self._intersections():
1278 v._linked._label = v._label
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
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)
1305 # label and classify intersections
1306 P._labelize()
1307 P._classify()
1309 # check for special cases
1310 P._special_cases(Q)
1311 Q._special_cases(P)
1312 # handle identicals
1313 P._special_identicals(Q)
1315 # set Entry/Exit flags
1316 P._set_entry_exits(Q)
1317 Q._set_entry_exits(P)
1319 # handle splits and crossings
1320 P._splits_xings(Q)
1322 # yield the results
1323 return P._results(P._presults(Q), Clas, **closed_inull_raiser_eps)
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
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)
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)
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
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)
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
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
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
1448 def _splits_xings(self, other): # MCCABE 15
1449 # 5) Handle split pairs and 6) crossing candidates
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)
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
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
1484 for p, q in _links2(self._2xings, other._2xings):
1485 p._label = q._label = L.CROSSING
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
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
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)
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}.
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)
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
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
1546 # 3. yield the result(s)
1547 return S._results(S._presults(), Clas, **closed_inull_raiser_xtend_eps)
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
1556 def _kwds(self, op, **more):
1557 # Get the kwds C{dict}.
1558 return _CompositeBase._kwds(self, op, xtend=self.xtend, **more)
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)
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
1583 @property
1584 def xtend(self):
1585 '''Get the option to handle I{degenerate cases} (C{bool}).
1586 '''
1587 return self._xtend
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)
1596class _EdgeFHP(object):
1597 # An edge between two L{LatLonFHP} points.
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)
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
1617 self._lr, \
1618 self._bt = _left_right_bottom_top_eps2(p1, p2)
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)))
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)))
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,)
1669class _EdgeGH(object):
1670 # An edge between two L{LatLonGH} points.
1672 _raiser = False
1673 _xtend = False
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)
1683 if xtend:
1684 self._xtend = True
1685 elif raiser:
1686 self._raiser = True
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)
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)
1698 @Property_RO
1699 def _hypot0(self):
1700 _, sx, _, sy = self._x_sx_y_sy
1701 return hypot(sx, sy) * _0_EPS
1703 @Property_RO
1704 def _hypot2(self):
1705 _, sx, _, sy = self._x_sx_y_sy
1706 return hypot2(sx, sy)
1708 def _intersect4(self, c1, c2, parallel=True): # MCCABE 14
1709 # Yield the intersections of this and another edge.
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.
1715 # @raise ClipError: Intersection unhandled.
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
1725 cx = c2.x - c1_x
1726 cy = c2.y - c1_y
1727 d = cy * sx - cx * sy
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
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
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)
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)
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
1821class _BooleanBase(object):
1822 # Shared C{Boolean[FHP|GH]} methods.
1824 def __add__(self, other):
1825 '''Sum: C{this + other} clips.
1826 '''
1827 return self._sum(_other(self, other), self.__add__) # PYCHOK OK
1829 def __and__(self, other):
1830 '''Intersection: C{this & other}.
1831 '''
1832 return self._boolean(other, False, False, self.__and__) # PYCHOK OK
1834 def __iadd__(self, other):
1835 '''In-place sum: C{this += other} clips.
1836 '''
1837 return self._inplace(self.__add__(other))
1839 def __iand__(self, other):
1840 '''In-place intersection: C{this &= other}.
1841 '''
1842 return self._inplace(self.__and__(other))
1844 def __ior__(self, other):
1845 '''In-place union: C{this |= other}.
1846 '''
1847 return self._inplace(self.__or__(other))
1849 def __or__(self, other):
1850 '''Union: C{this | other}.
1851 '''
1852 return self._boolean(other, True, True, self.__or__) # PYCHOK OK
1854 def __radd__(self, other):
1855 '''Reverse sum: C{other + this} clips.
1856 '''
1857 return _other(self, other)._sum(self, self.__radd__)
1859 def __rand__(self, other):
1860 '''Reverse intersection: C{other & this}
1861 '''
1862 return _other(self, other).__and__(self)
1864 def __ror__(self, other):
1865 '''Reverse union: C{other | this}
1866 '''
1867 return _other(self, other).__or__(self)
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
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
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.
1895 The supported operations between (composite) polygon A and B are:
1897 - C = A & B or A &= B, intersection of A and B
1899 - C = A + B or A += B, sum of A and B clips
1901 - C = A | B or A |= B, union of A and B
1903 - A == B or A != B, equivalent A and B clips
1905 - A.isequalTo(B, eps), equivalent within tolerance
1907 @see: Methods C{__eq__} and C{isequalTo}, function L{clipFHP4}
1908 and class L{BooleanGH}.
1909 '''
1910 _kind = _boolean_
1912 def __init__(self, lls, raiser=False, eps=EPS, name=NN):
1913 '''New L{BooleanFHP} operand for I{boolean} operation.
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)
1925 def __isub__(self, other):
1926 '''Not implemented.'''
1927 return _NotImplemented(self, other)
1929 def __rsub__(self, other):
1930 '''Not implemented.'''
1931 return _NotImplemented(self, other)
1933 def __sub__(self, other):
1934 '''Not implemented.'''
1935 return _NotImplemented(self, other)
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)
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.
1951 The supported operations between (composite) polygon A and B are:
1953 - C = A - B or A -= B, difference A less B
1955 - C = B - A or B -= A, difference B less B
1957 - C = A & B or A &= B, intersection of A and B
1959 - C = A + B or A += B, sum of A and B clips
1961 - C = A | B or A |= B, union of A and B
1963 - A == B or A != B, equivalent A and B clips
1965 - A.isequalTo(B, eps), equivalent within tolerance
1967 @note: To handle I{degenerate cases} like C{point-edge} and
1968 C{point-point} intersections, use class L{BooleanFHP}.
1970 @see: Methods C{__eq__} and C{isequalTo}, function L{clipGH4}
1971 and class L{BooleanFHP}.
1972 '''
1973 _kind = _boolean_
1975 def __init__(self, lls, raiser=True, xtend=False, eps=EPS, name=NN):
1976 '''New L{BooleanFHP} operand for I{boolean} operation.
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)
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)
1996 def __isub__(self, other):
1997 '''In-place difference: C{this -= other}.
1998 '''
1999 return self._inplace(self.__sub__(other))
2001 def __rsub__(self, other):
2002 ''' Reverse difference: C{other - this}
2003 '''
2004 return _other(self, other).__sub__(self)
2006 def __sub__(self, other):
2007 '''Difference: C{this - other}.
2008 '''
2009 return self._boolean(other, True, False, self.__sub__)
2012def isBoolean(obj):
2013 '''Check for C{Boolean} composites.
2015 @arg obj: The object (any C{type}).
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)
2024__all__ += _ALL_DOCS(_BooleanBase, _Clip,
2025 _CompositeBase, _CompositeFHP, _CompositeGH,
2026 _LatLonBool)
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.
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>.