Coverage for pygeodesy/booleans.py: 94%
981 statements
« prev ^ index » next coverage.py v7.2.2, created at 2024-06-01 11:43 -0400
« prev ^ index » next coverage.py v7.2.2, created at 2024-06-01 11:43 -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, issubclassof, map2, _xscalar
21from pygeodesy.constants import EPS, EPS2, INT0, _0_0, _0_5, _1_0
22from pygeodesy.errors import ClipError, _IsnotError, _TypeError, \
23 _ValueError, _xattr, _xkwds_get
24from pygeodesy.fmath import favg, hypot, hypot2
25# from pygeodesy.fsums import fsum1 # _MODS
26from pygeodesy.interns import NN, _BANG_, _clip_, _clipid_, _COMMASPACE_, \
27 _composite_, _DOT_, _e_, _ELLIPSIS_, _few_, \
28 _height_, _lat_, _LatLon_, _lon_, _not_, \
29 _points_, _SPACE_, _too_, _X_, _x_, \
30 _B_, _d_, _R_ # PYCHOK used!
31from pygeodesy.lazily import _ALL_DOCS, _ALL_LAZY, _ALL_MODS as _MODS
32from pygeodesy.latlonBase import LatLonBase, \
33 LatLon2Tuple, Property_RO, property_RO
34from pygeodesy.named import _name__, _Named, _NotImplemented, \
35 Fmt, pairs, unstr
36# from pygeodesy.namedTuples import LatLon2Tupe # from .latlonBase
37# from pygeodesy.points import boundsOf # _MODS
38# from pygeodesy.props import Property_RO, property_RO # from .latlonBase
39# from pygeodesy.streprs import Fmt, pairs, unstr # from .named
40from pygeodesy.units import Height, HeightX
41from pygeodesy.utily import fabs, _unrollon, _Wrap
43# from math import fabs # from .utily
45__all__ = _ALL_LAZY.booleans
46__version__ = '24.05.29'
48_0_EPS = EPS # near-zero, positive
49_EPS_0 = -EPS # near-zero, negative
50_1_EPS = _1_0 + EPS # near-one, over
51_EPS_1 = _1_0 - EPS # near-one, under
52_10EPS = EPS * 10 # see ._2Abs, ._10eps
54_alpha_ = 'alpha'
55_boolean_ = 'boolean'
56_case_ = 'case'
57_corners_ = 'corners'
58_duplicate_ = 'duplicate'
59_open_ = 'open'
62def _Enum(txt, enum): # PYCHOK unused
63 return txt # NN(txt, _TILDE_, enum)
66class _L(object): # Intersection labels
67 CROSSING = _Enum(_X_, 1) # C++ enum
68 CROSSING_D = _Enum(_X_ + _d_, 8)
69 CROSSINGs = (CROSSING, CROSSING_D)
70 BOUNCING = _Enum(_B_, 2)
71 BOUNCING_D = _Enum(_B_ + _d_, 9)
72 BOUNCINGs = (BOUNCING, BOUNCING_D) + CROSSINGs
73 LEFT_ON = _Enum('Lo', 3)
74 ON_ON = _Enum('oo', 5)
75 ON_LEFT = _Enum('oL', 6)
76 ON_RIGHT = _Enum('oR', 7)
77 RIGHT_ON = _Enum('Ro', 4)
78 RIGHT_LEFT_ON = (RIGHT_ON, LEFT_ON)
79 # Entry/Exit flags
80 ENTRY = _Enum(_e_, 1)
81 EXIT = _Enum(_x_, 0)
82 Toggle = {ENTRY: EXIT,
83 EXIT: ENTRY,
84 None: None}
86_L = _L() # PYCHOK singleton
89class _RP(object): # RelativePositions
90 IS_Pm = _Enum('Pm', 2) # C++ enum
91 IS_Pp = _Enum('Pp', 3)
92 LEFT = _Enum('L', 0)
93 RIGHT = _Enum(_R_, 1)
95_RP = _RP() # PYCHOK singleton
97_RP2L = {(_RP.LEFT, _RP.RIGHT): _L.CROSSING,
98 (_RP.RIGHT, _RP.LEFT): _L.CROSSING,
99 (_RP.LEFT, _RP.LEFT): _L.BOUNCING,
100 (_RP.RIGHT, _RP.RIGHT): _L.BOUNCING,
101 # overlapping cases
102 (_RP.RIGHT, _RP.IS_Pp): _L.LEFT_ON,
103 (_RP.IS_Pp, _RP.RIGHT): _L.LEFT_ON,
104 (_RP.LEFT, _RP.IS_Pp): _L.RIGHT_ON,
105 (_RP.IS_Pp, _RP.LEFT): _L.RIGHT_ON,
106 (_RP.IS_Pm, _RP.IS_Pp): _L.ON_ON,
107 (_RP.IS_Pp, _RP.IS_Pm): _L.ON_ON,
108 (_RP.IS_Pm, _RP.RIGHT): _L.ON_LEFT,
109 (_RP.RIGHT, _RP.IS_Pm): _L.ON_LEFT,
110 (_RP.LEFT, _RP.IS_Pm): _L.ON_RIGHT,
111 (_RP.IS_Pm, _RP.LEFT): _L.ON_RIGHT}
114class _LatLonBool(_Named):
115 '''(INTERNAL) Base class for L{LatLonFHP} and L{LatLonGH}.
116 '''
117 _alpha = None # point AND intersection else length
118 _checked = False # checked in phase 3 iff intersection
119 _clipid = INT0 # (polygonal) clip identifier, number
120 _dupof = None # original of a duplicate
121# _e_x_str = NN # shut up PyChecker
122 _height = Height(0) # interpolated height, usually meter
123 _linked = None # link to neighbor iff intersection
124 _next = None # link to the next vertex
125 _prev = None # link to the previous vertex
127 def __init__(self, lat_ll, lon=None, height=0, clipid=INT0,
128 wrap=False, **name):
129 '''New C{LatLon[FHP|GH]} from separate C{lat}, C{lon}, C{height}
130 and C{clipid} scalars or from a previous C{LatLon[FHP|GH]},
131 a C{Clip[FHP|GH]4Tuple} or some other C{LatLon} instance.
133 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude
134 (C{LatLon[FHP|GH]}, aC{Clip[FHP|GH]4Tuple}
135 or some other C{LatLon}).
136 @kwarg lon: Longitude (C{scalar}), iff B{C{lat_ll}} is
137 scalar, ignored otherwise.
138 @kwarg height: Height (C{scalar}), conventionally C{meter}.
139 @kwarg clipid: Clip identifier (C{int}).
140 @kwarg wrap: If C{True}, wrap or I{normalize} B{C{lat}}
141 and B{C{lon}} (C{bool}).
142 @kwarg name: Optional name (C{str}).
143 '''
144 if lon is None:
145 y, x = lat_ll.lat, lat_ll.lon
146 h = _xattr(lat_ll, height=height)
147 c = _xattr(lat_ll, clipid=clipid)
148 else:
149 y, x = lat_ll, lon
150 h, c = height, clipid
151 self.y, self.x = _Wrap.latlon(y, x) if wrap else (y, x)
152 # don't duplicate defaults
153 if self._height != h:
154 self._height = h
155 if self._clipid != c:
156 self._clipid = c
157 if name:
158 self.name = name
160 def __abs__(self):
161 return max(fabs(self.x), fabs(self.y))
163 def __eq__(self, other):
164 return other is self or bool(_other(self, other) and
165 other.x == self.x and
166 other.y == self.y)
168 def __ne__(self, other): # required for Python 2
169 return not self.__eq__(other)
171 def __repr__(self):
172 '''String C{repr} of this lat-/longitude.
173 '''
174 if self._prev or self._next:
175 t = _ELLIPSIS_(self._prev, self._next)
176 t = _SPACE_(self, Fmt.ANGLE(t))
177 else:
178 t = str(self)
179 return t
181 def __str__(self):
182 '''String C{str} of this lat-/longitude.
183 '''
184 t = (_lat_, self.lat), (_lon_, self.lon)
185 if self._height:
186 X = _X_ if self.isintersection else NN
187 t += (_height_ + X, self._height),
188 if self._clipid:
189 t += (_clipid_, self._clipid),
190 if self._alpha is not None:
191 t += (_alpha_, self._alpha),
192# if self._dupof: # recursion risk
193# t += (_dupof_, self._dupof.name),
194 t = pairs(t, prec=8, fmt=Fmt.g, ints=True)
195 t = Fmt.PAREN(_COMMASPACE_.join(t))
196 if self._linked:
197 k = _DOT_ if self._checked else _BANG_
198 t = NN(t, self._e_x_str(k)) # PYCHOK expected
199 return NN(self.name, t)
201 def __sub__(self, other):
202 _other(self, other)
203 return self.__class__(self.y - other.y, # classof
204 self.x - other.x)
206 def _2A(self, p2, p3):
207 # I{Signed} area of a triangle, I{doubled}.
208 x, y = self.x, self.y
209 return (p2.x - x) * (p3.y - y) - \
210 (p3.x - x) * (p2.y - y)
212 def _2Abs(self, p2, p3, eps=_10EPS):
213 # I{Unsigned} area of a triangle, I{doubled}
214 # or 0 if below the given threshold C{eps}.
215 a = fabs(self._2A(p2, p3))
216 return 0 if a < eps else a
218 @property_RO
219 def clipid(self):
220 '''Get the I{clipid} (C{int} or C{0}).
221 '''
222 return self._clipid
224 def _equi(self, llb, eps):
225 # Is this LLB I{equivalent} to B{C{llb}} within
226 # the given I{non-negative} tolerance B{C{eps}}?
227 return not (fabs(llb.lon - self.x) > eps or
228 fabs(llb.lat - self.y) > eps)
230 @property_RO
231 def height(self):
232 '''Get the I{height} (C{Height} or C{int}).
233 '''
234 h = self._height
235 return HeightX(h) if self.isintersection else (
236 Height(h) if h else _LatLonBool._height)
238 def isequalTo(self, other, eps=None):
239 '''Is this point equal to an B{C{other}} within a given,
240 I{non-negative} tolerance, ignoring C{height}?
242 @arg other: The other point (C{LatLon}).
243 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).
245 @return: C{True} if equivalent, C{False} otherwise (C{bool}).
247 @raise TypeError: Invalid B{C{other}}.
248 '''
249 try:
250 return self._equi(other, _eps0(eps))
251 except (AttributeError, TypeError, ValueError):
252 raise _IsnotError(_LatLon_, other=other)
254 @property_RO
255 def isintersection(self):
256 '''Is this an intersection? May be C{ispoint} too!
257 '''
258 return bool(self._linked)
260 @property_RO
261 def ispoint(self):
262 '''Is this an I{original} point? May be C{isintersection} too!
263 '''
264 return self._alpha is None
266 @property_RO
267 def lat(self):
268 '''Get the latitude (C{scalar}).
269 '''
270 return self.y
272 @property_RO
273 def latlon(self):
274 '''Get the lat- and longitude (L{LatLon2Tuple}).
275 '''
276 return LatLon2Tuple(self.y, self.x)
278 def _link(self, other):
279 # Make this and an other point neighbors.
280 # assert _other(self, other)
281 self._linked = other
282 other._linked = self
284 @property_RO
285 def lon(self):
286 '''Get the longitude (C{scalar}).
287 '''
288 return self.x
290 def _toClas(self, Clas, clipid):
291 # Return this vertex as a C{Clas} instance
292 # (L{Clip[FHP|GH]4Tuple} or L{LatLon[FHP|GH]}).
293 return Clas(self.lat, self.lon, self.height, clipid)
296class LatLonFHP(_LatLonBool):
297 '''A point or intersection in a L{BooleanFHP} clip or composite.
298 '''
299 _en_ex = None
300 _label = None
301 _2split = None # or C{._Clip}
302 _2xing = False
304 def __init__(self, lat_ll, *lon_h_clipid, **wrap_name):
305 '''New C{LatLonFHP} from separate C{lat}, C{lon}, C{h}eight
306 and C{clipid} scalars, or from a previous L{LatLonFHP},
307 a L{ClipFHP4Tuple} or some other C{LatLon} instance.
309 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude
310 (L{LatLonFHP}, C{LatLon} or L{ClipFHP4Tuple}).
311 @arg lon_h_clipid: Longitude (C{scalar}), C{h}eight and
312 C{clipid} iff B{C{lat_ll}} is scalar,
313 ignored otherwise.
314 @kwarg wrap_name: Keyword arguments C{B{wrap}=False} and
315 C{B{name}=NN}. If C{B{wrap} is True}, wrap
316 or I{normalize} the lat- and longitude
317 (C{bool}). Optional B{C{name}} (C{str}).
318 '''
319 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **wrap_name)
321 def __add__(self, other):
322 _other(self, other)
323 return self.__class__(self.y + other.y, self.x + other.x)
325 def __mod__(self, other): # cross product
326 _other(self, other)
327 return self.x * other.y - self.y * other.x
329 def __mul__(self, other): # dot product
330 _other(self, other)
331 return self.x * other.x + self.y * other.y
333 def __rmul__(self, other): # scalar product
334 _xscalar(other=other)
335 return self.__class__(self.y * other, self.x * other)
337 def _e_x_str(self, t): # PYCHOK no cover
338 if self._label:
339 t = NN(self._label, t)
340 if self._en_ex:
341 t = NN(t, self._en_ex)
342 return t
344 @property_RO
345 def _isduplicate(self):
346 # Is this point a I{duplicate} intersection?
347 p = self._dupof
348 return bool(p and self._linked
349 and p is not self
350 and p == self
351# and p._alpha in (None, self._alpha)
352 and self._alpha in (_0_0, p._alpha))
354# @property_RO
355# def _isduplicated(self):
356# # Return the number of I{duplicates}?
357# d, v = 0, self
358# while v:
359# if v._dupof is self:
360# d += 1
361# v = v._next
362# if v is self:
363# break
364# return d
366 def isenclosedBy(self, *composites_points, **wrap):
367 '''Is this point inside one or more composites or polygons based
368 the U{winding number<https://www.ScienceDirect.com/science/
369 article/pii/S0925772101000128>}?
371 @arg composites_points: Composites and/or iterables of points
372 (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, L{LatLonFHP},
373 L{LatLonGH} or any C{LatLon}).
374 @kwarg wrap: If C{True}, wrap or I{normalize} and unroll the
375 C{points} (C{bool}).
377 @raise ValueError: Some C{points} invalid.
379 @see: U{Algorithm 6<https://www.ScienceDirect.com/science/
380 article/pii/S0925772101000128>}.
381 '''
382 class _Pseudo(object):
383 # Pseudo-_CompositeBase._clips tuple
385 @property_RO
386 def _clips(self):
387 for cp in _Cps(_CompositeFHP, composites_points,
388 LatLonFHP.isenclosedBy): # PYCHOK yield
389 for c in cp._clips:
390 yield c
392 return self._isinside(_Pseudo(), **wrap)
394 def _isinside(self, composite, *excludes, **wrap):
395 # Is this point inside a composite, excluding
396 # certain C{_Clip}s? I{winding number}?
397 x, y, i = self.x, self.y, False
398 for c in composite._clips:
399 if c not in excludes:
400 w = 0
401 for p1, p2 in c._edges2(**wrap):
402 # edge [p1,p2] must straddle y
403 if (p1.y < y) is not (p2.y < y): # or ^
404 r = p2.x > x
405 s = p2.y > p1.y
406 if p1.x < x:
407 b = r and (s is (p1._2A(p2, self) > 0))
408 else:
409 b = r or (s is (p1._2A(p2, self) > 0))
410 if b:
411 w += 1 if s else -1
412 if isodd(w):
413 i = not i
414 return i
416 @property_RO
417 def _prev_next2(self):
418 # Adjust 2-tuple (._prev, ._next) iff a I{duplicate} intersection
419 p, n = self, self._next
420 if self._isduplicate:
421 p = self._dupof
422 while p._isduplicate:
423 p = p._dupof
424 while n._isduplicate:
425 n = n._next
426 return p._prev, n
428# def _edge2(self):
429# # Return the start and end point of the
430# # edge containing I{intersection} C{v}.
431# n = p = self
432# while p.isintersection:
433# p = p._prev
434# if p is self:
435# break
436# while n.isintersection:
437# n = n._next
438# if n is self:
439# break
440# # assert p == self or not p._2Abs(self, n)
441# return p, n
443 def _RPoracle(self, p1, p2, p3):
444 # Relative Position oracle
445 if p1._linked is self: # or p1._linked2(self):
446 T = _RP.IS_Pm
447 elif p3._linked is self: # or p3._linked2(self):
448 T = _RP.IS_Pp
449 elif p1._2A(p2, p3) > 0: # left turn
450 T = _RP.LEFT if self._2A(p1, p2) > 0 and \
451 self._2A(p2, p3) > 0 else \
452 _RP.RIGHT # PYCHOK indent
453 else: # right turn (or straight)
454 T = _RP.RIGHT if self._2A(p1, p2) < 0 and \
455 self._2A(p2, p3) < 0 else \
456 _RP.LEFT # PYCHOK indent
457 return T
460class LatLonGH(_LatLonBool):
461 '''A point or intersection in a L{BooleanGH} clip or composite.
462 '''
463 _entry = None # entry or exit iff intersection
465 def __init__(self, lat_ll, *lon_h_clipid, **wrap_name):
466 '''New C{LatLonGH} from separate C{lat}, C{lon}, C{h}eight
467 and C{clipid} scalars, or from a previous L{LatLonGH},
468 L{ClipGH4Tuple} or some other C{LatLon} instance.
470 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude
471 (L{LatLonGH}, C{LatLon} or L{ClipGH4Tuple}).
472 @arg lon_h_clipid: Longitude (C{scalar}), C{h}eight and
473 C{clipid} iff B{C{lat_ll}} is scalar,
474 ignored otherwise.
475 @kwarg wrap_name: Keyword arguments C{B{wrap}=False} and
476 C{B{name}=NN}. If C{B{wrap} is True}, wrap
477 or I{normalize} the lat- and longitude
478 (C{bool}). Optional B{C{name}} (C{str}).
479 '''
480 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **wrap_name)
482 def _check(self):
483 # Check-mark this vertex and its link.
484 self._checked = True
485 k = self._linked
486 if k and not k._checked:
487 k._checked = True
489 def _e_x_str(self, t): # PYCHOK no cover
490 return t if self._entry is None else NN(t,
491 (_e_ if self._entry else _x_))
493 def isenclosedBy(self, *composites_points, **wrap):
494 '''Is this point inside one or more composites or polygons based
495 on the U{even-odd-rule<https://www.ScienceDirect.com/science/
496 article/pii/S0925772101000128>}?
498 @arg composites_points: Composites and/or iterables of points
499 (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, L{LatLonFHP},
500 L{LatLonGH} or any C{LatLon}).
501 @kwarg wrap: If C{True}, wrap or I{normalize} and unroll the
502 C{points} (C{bool}).
504 @raise ValueError: Some B{C{points}} invalid.
505 '''
506 class _Pseudo(object):
507 # Pseudo-_CompositeBase._edges3 method
509 def _edges3(self, **kwds):
510 for cp in _Cps(_CompositeGH, composites_points,
511 LatLonGH.isenclosedBy): # PYCHOK yield
512 for e in cp._edges3(**kwds):
513 yield e
515 return self._isinside(_Pseudo(), **wrap)
517 def _isinside(self, composite, *bottom_top, **wrap):
518 # Is this vertex inside the composite? I{even-odd rule}?
520 def _x(y, p1, p2):
521 # return C{x} at given C{y} on edge [p1,p2]
522 return (y - p1.y) / (p2.y - p1.y) * (p2.x - p1.x)
524 # The I{even-odd} rule counts the number of edges
525 # intersecting a ray emitted from this point to
526 # east-bound infinity. When I{odd} this point lies
527 # inside, if I{even} outside.
528 y, i = self.y, False
529 if not (bottom_top and _outside(y, y, *bottom_top)):
530 x = self.x
531 for p1, p2, _ in composite._edges3(**wrap):
532 if (p1.y < y) is not (p2.y < y): # or ^
533 r = p2.x > x
534 if p1.x < x:
535 b = r and (_x(y, p1, p2) > x)
536 else:
537 b = r or (_x(y, p1, p2) > x)
538 if b:
539 i = not i
540 return i
543class _Clip(_Named):
544 '''(INTERNAL) A I{doubly-linked} list representing a I{closed}
545 polygon of L{LatLonFHP} or L{LatLonGH} points, duplicates
546 and intersections with other clips.
547 '''
548 _composite = None
549 _dups = 0
550 _first = None
551 _id = 0
552 _identical = False
553 _noInters = False
554 _last = None
555 _LL = None
556 _len = 0
557 _pushback = False
559 def __init__(self, composite, clipid=INT0):
560 '''(INTERNAL) New C{_Clip}.
561 '''
562 # assert isinstance(composite, _CompositeBase)
563 if clipid in composite._clipids:
564 raise ClipError(clipid=clipid, txt=_duplicate_)
565 self._composite = composite
566 self._id = clipid
567 self._LL = composite._LL
568 composite._clips = composite._clips + (self,)
570 def __contains__(self, point): # PYCHOK no cover
571 '''Is the B{C{point}} in this clip?
572 '''
573 for v in self:
574 if v is point: # or ==?
575 return True
576 return False
578 def __eq__(self, other):
579 '''Is this clip I{equivalent} to an B{C{other}} clip,
580 do both have the same C{len}, the same points, in
581 the same order, possibly rotated?
582 '''
583 return self._equi(_other(self, other), 0)
585 def __ge__(self, other):
586 '''See method C{__lt__}.
587 '''
588 return not self.__lt__(other)
590 def __gt__(self, other):
591 '''Is this clip C{"above"} an B{C{other}} clip,
592 located or stretched farther North or East?
593 '''
594 return self._bltr4 > _other(self, other)._bltr4
596 def __hash__(self): # PYCHOK no over
597 return hash(self._bltr4)
599 def __iter__(self):
600 '''Yield the points, duplicates and intersections.
601 '''
602 v = f = self._first
603 while v:
604 yield v
605 v = v._next
606 if v is f:
607 break
609 def __le__(self, other):
610 '''See method C{__gt__}.
611 '''
612 return not self.__gt__(other)
614 def __len__(self):
615 '''Return the number of points, duplicates and
616 intersections in this clip.
617 '''
618 return self._len
620 def __lt__(self, other):
621 '''Is this clip C{"below"} an B{C{other}} clip,
622 located or stretched farther South or West?
623 '''
624 return self._bltr4 < _other(self, other)._bltr4
626 def __ne__(self, other): # required for Python 2
627 '''See method C{__eq__}.
628 '''
629 return not self.__eq__(other)
631 _all = __iter__
633 @property_RO
634 def _all_ON_ON(self):
635 # Check whether all vertices are ON_ON.
636 L_ON_ON = _L.ON_ON
637 return all(v._label is L_ON_ON for v in self)
639 def _append(self, y_v, *x_h_clipid):
640 # Append a point given as C{y}, C{x}, C{h}eight and
641 # C{clipid} args or as a C{LatLon[FHP|GH]}.
642 self._last = v = self._LL(y_v, *x_h_clipid) if x_h_clipid else y_v
643 self._len += 1
644 # assert v._clipid == self._id
646 v._next = n = self._first
647 if n is None: # set ._first
648 self._first = p = n = v
649 else: # insert before ._first
650 v._prev = p = n._prev
651 p._next = n._prev = v
652 return v
654# def _appendedup(self, v, clipid=0):
655# # Like C{._append}, but only append C{v} if not a
656# # duplicate of the one previously append[edup]'ed.
657# y, x, p = v.y, v.x, self._last
658# if p is None or y != p.y or x != p.x or clipid != p._clipid:
659# p = self._append(y, x, v._height, clipid)
660# if v._linked:
661# p._linked = True # to force errors
662# return p
664 @Property_RO
665 def _bltr4(self):
666 # Get the bounds as 4-tuple C{(bottom, left, top, right)}.
667 return map2(float, _MODS.points.boundsOf(self, wrap=False))
669 def _bltr4eps(self, eps):
670 # Get the ._bltr4 bounds tuple, oversized.
671 if eps > 0: # > EPS
672 yb, xl, yt, xr = self._bltr4
673 yb, yt = _low_high_eps2(yb, yt, eps)
674 xl, xr = _low_high_eps2(xl, xr, eps)
675 t = yb, xl, yt, xr
676 else:
677 t = self._bltr4
678 return t
680 def _closed(self, raiser): # PYCHOK unused
681 # End a clip, un-close it and check C{len}.
682 p, f = self._last, self._first
683 if f and f._prev is p and p is not f and \
684 p._next is f and p == f: # PYCHOK no cover
685 # un-close the clip
686 f._prev = p = p._prev
687 p._next = f
688 self._len -= 1
689# elif f and raiser:
690# raise self._OpenClipError(p, f)
691 if len(self) < 3:
692 raise self._Error(_too_(_few_))
694 def _dup(self, q):
695 # Duplicate a point (or intersection) as intersection.
696 v = self._insert(q.y, q.x, q)
697 v._alpha = q._alpha or _0_0 # _0_0 replaces None
698 v._dupof = q._dupof or q
699 # assert v._prev is q
700 # assert q._next is v
701 return v
703 def _edges2(self, wrap=False, **unused):
704 # Yield each I{original} edge as a 2-tuple
705 # (p1, p2), a pair of C{LatLon[FHP|GH])}s.
706 p1 = p = f = self._first
707 while p:
708 p2 = p = p._next
709 if p.ispoint:
710 if wrap and p is not f:
711 p2 = _unrollon(p1, p)
712 yield p1, p2
713 p1 = p2
714 if p is f:
715 break
717 def _equi(self, clip, eps):
718 # Is this clip I{equivalent} to B{C{clip}} within
719 # the given I{non-negative} tolerance B{C{eps}}?
720 r, f = len(self), self._first
721 if f and r == len(clip) and self._bltr4eps(eps) \
722 == clip._bltr4eps(eps):
723 _equi = _LatLonBool._equi
724 for v in clip:
725 if _equi(f, v, eps):
726 s, n = f, v
727 for _ in range(r):
728 s, n = s._next, n._next
729 if not _equi(s, n, eps):
730 break # next v
731 else: # equivalent
732 return True
733 return False
735 def _Error(self, txt): # PYCHOK no cover
736 # Build a C{ClipError} instance
737 kwds = dict(len=len(self), txt=txt)
738 if self._dups:
739 kwds.update(dups=self._dups)
740 cp = self._composite
741 if self._id:
742 try:
743 i = cp._clips.index(self)
744 if i != self._id:
745 kwds[_clip_] = i
746 except ValueError:
747 pass
748 kwds[_clipid_] = self._id
749 return ClipError(cp._kind, cp.name, **kwds)
751 def _index(self, clips, eps):
752 # see _CompositeBase._equi
753 for i, c in enumerate(clips):
754 if c._equi(self, eps):
755 return i
756 raise ValueError(NN) # like clips.index(self)
758 def _insert(self, y, x, start, *end_alpha):
759 # insertVertex between points C{start} and
760 # C{end}, ordered by C{alpha} iff given.
761 v = self._LL(y, x, start._height, start._clipid)
762 n = start._next
763 if end_alpha:
764 end, alpha = end_alpha
765 v._alpha = alpha
766 v._height = favg(v._height, end._height, f=alpha)
767 # assert start is not end
768 while n is not end and n._alpha < alpha:
769 n = n._next
770 v._next = n
771 v._prev = p = n._prev
772 p._next = n._prev = v
773 self._len += 1
774# _Clip._bltr4._update(self)
775# _Clip._ishole._update(self)
776 return v
778 def _intersection(self, unused, q, *p1_p2_alpha):
779 # insert an intersection or make a point both
780 if p1_p2_alpha: # intersection on edge
781 v = self._insert(q.y, q.x, *p1_p2_alpha)
782 else: # intersection at point
783 v = q
784 # assert not v._linked
785 # assert v._alpha is None
786 return v
788 def _intersections(self):
789 # Yield all intersections, some may be points too.
790 for v in self:
791 if v.isintersection:
792 yield v
794 @Property_RO
795 def _ishole(self): # PYCHOK no cover
796 # Is this clip a hole inside its composite?
797 v = self._first
798 return v._isinside(self._composite, self) if v else False
800 @property_RO
801 def _nodups(self):
802 # Yield all non-duplicates.
803 for v in self:
804 if not v._dupof:
805 yield v
807 def _noXings(self, Union):
808 # Are all intersections non-CROSSINGs, -BOUNCINGs?
809 Ls = _L.BOUNCINGs if Union else _L.CROSSINGs
810 return all(v._label not in Ls for v in self._intersections())
812 def _OpenClipError(self, s, e): # PYCHOK no cover
813 # Return a C{CloseError} instance
814 t = NN(s, _ELLIPSIS_(_COMMASPACE_, e))
815 return self._Error(_SPACE_(_open_, t))
817 def _point2(self, insert):
818 # getNonIntersectionPoint and -Vertex
819 if not (insert and self._noInters):
820 for p in self._points(may_be=False): # not p._isduplicated?
821 return p, None
822 for n in self._intersections():
823 p, _ = n._prev_next2
824 k = p._linked
825 if k:
826 if n._linked not in k._prev_next2:
827 # create a pseudo-point
828 k = _0_5 * (p + n)
829 if insert:
830 k = self._insert(k.y, k.x, n._prev)
831 r = k # to remove later
832 else: # no ._prev, ._next
833 k._clipid = n._clipid
834 r = None
835 return k, r
836 return None, None
838 def _points(self, may_be=True):
839 # Yield all points I{in original order}, which may be intersections too.
840 for v in self:
841 if v.ispoint and (may_be or not v.isintersection):
842 yield v
844 def _remove2(self, v):
845 # Remove vertex C{v}.
846 # assert not v._isduplicated
847 if len(self) > 1:
848 p = v._prev
849 p._next = n = v._next
850 n._prev = p
851 if self._first is v:
852 self._first = n
853 if self._last is v:
854 self._last = p
855 self._len -= 1
856 else:
857 n = self._last = \
858 p = self._first = None
859 self._len = 0
860 return p, n
862 def _update_all(self): # PYCHOK no cover
863 # Zap the I{cached} properties.
864 _Clip._bltr4._update( self)
865 _Clip._ishole._update(self)
866 return self # for _special_identicals
868 def _Xings(self):
869 # Yield all I{un-checked} CROSSING intersections.
870 CROSSING = _L.CROSSING
871 for v in self._intersections():
872 if v._label is CROSSING and not v._checked:
873 yield v
876class _CompositeBase(_Named):
877 '''(INTERNAL) Base class for L{BooleanFHP} and L{BooleanGH}
878 (C{_CompositeFHP} and C{_CompositeGH}).
879 '''
880 _clips = () # tuple of C{_Clips}
881 _eps = EPS # null edges
882 _kind = _corners_
883 _LL = _LatLonBool # shut up PyChecker
884 _raiser = False
885 _xtend = False
887 def __init__(self, lls, kind=NN, eps=EPS, **name):
888 '''(INTERNAL) See L{BooleanFHP} and L{BooleanGH}.
889 '''
890 n = _name__(name, _or_nameof=lls)
891 if n:
892 self.name = n
893 if kind:
894 self._kind = kind
895 if self._eps < eps:
896 self._eps = eps
898 c = _Clip(self)
899 lp = None
900 for ll in lls:
901 ll = self._LL(ll)
902 if lp is None:
903 c._id = ll._clipid # keep clipid
904 lp = c._append(ll)
905 elif ll._clipid != lp._clipid: # new clip
906 c._closed(self.raiser)
907 c = _Clip(self, ll._clipid)
908 lp = c._append(ll)
909 elif abs(ll - lp) > eps: # PYCHOK lp
910 lp = c._append(ll)
911 else:
912 c._dups += 1
913 c._closed(self.raiser)
915 def __contains__(self, point): # PYCHOK no cover
916 '''Is the B{C{point}} in one of the clips?
917 '''
918 for c in self._clips:
919 if point in c:
920 return True
921 return False
923 def __eq__(self, other):
924 '''Is this I{composite} equivalent to an B{C{other}}, i.e.
925 do both contain I{equivalent} clips in the same or in a
926 different order? Two clips are considered I{equivalent}
927 if both have the same points etc. in the same order,
928 possibly rotated.
929 '''
930 return self._equi(_other(self, other), 0)
932 def __iter__(self):
933 '''Yield all points, duplicates and intersections.
934 '''
935 for c in self._clips:
936 for v in c:
937 yield v
939 def __ne__(self, other): # required for Python 2
940 '''See method C{__eq__}.
941 '''
942 return not self.__eq__(other)
944 def __len__(self):
945 '''Return the I{total} number of points.
946 '''
947 return sum(map(len, self._clips)) if self._clips else 0
949 def __repr__(self):
950 '''String C{repr} of this composite.
951 '''
952 c = len(self._clips)
953 c = Fmt.SQUARE(c) if c > 1 else NN
954 n = Fmt.SQUARE(len(self))
955 t = Fmt.PAREN(self) # XXX not unstr
956 return NN(self.__class__.__name__, c, n, t)
958 def __str__(self):
959 '''String C{str} of this composite.
960 '''
961 return _COMMASPACE_.join(map(str, self))
963 @property_RO
964 def _bottom_top_eps2(self):
965 # Get the bottom and top C{y} bounds, oversized.
966 return _min_max_eps2(min(v.y for v in self),
967 max(v.y for v in self))
969 def _class(self, corners, kwds, **dflts):
970 # Return a new instance
971 _g = kwds.get
972 kwds = dict((n, _g(n, v)) for n, v in dflts.items())
973 return self.__class__(corners or (), **kwds)
975 @property_RO
976 def _clipids(self): # PYCHOK no cover
977 for c in self._clips:
978 yield c._id
980 def clipids(self):
981 '''Return a tuple with all C{clipid}s, I{ordered}.
982 '''
983 return tuple(self._clipids)
985# def _clipidups(self, other):
986# # Number common C{clipid}s between this and an C{other} composite
987# return len(set(self._clipids).intersection(set(other._clipids)))
989 def _edges3(self, **raiser_wrap):
990 # Yield each I{original} edge as a 3-tuple
991 # C{(LatLon[FHP|GH], LatLon[FHP|GH], _Clip)}.
992 for c in self._clips:
993 for p1, p2 in c._edges2(**raiser_wrap):
994 yield p1, p2, c
996 def _encloses(self, lat, lon, **wrap):
997 # see function .points.isenclosedBy
998 return self._LL(lat, lon).isenclosedBy(self, **wrap)
1000 @property
1001 def eps(self):
1002 '''Get the null edges tolerance (C{degrees}, usually).
1003 '''
1004 return self._eps
1006 @eps.setter # PYCHOK setter!
1007 def eps(self, eps):
1008 '''Set the null edges tolerance (C{degrees}, usually).
1009 '''
1010 self._eps = eps
1012 def _10eps(self, **eps_):
1013 # Get eps for _LatLonBool._2Abs
1014 e = _xkwds_get(eps_, eps=self._eps)
1015 if e != EPS:
1016 e *= _10EPS / EPS
1017 else:
1018 e = _10EPS
1019 return e
1021 def _equi(self, other, eps):
1022 # Is this composite I{equivalent} to an B{C{other}} within
1023 # the given, I{non-negative} tolerance B{C{eps}}?
1024 cs, co = self._clips, other._clips
1025 if cs and len(cs) == len(co):
1026 if eps > 0:
1027 _index = _Clip._index
1028 else:
1029 def _index(c, cs, unused):
1030 return cs.index(c)
1031 try:
1032 cs = list(sorted(cs))
1033 for c in sorted(co):
1034 cs.pop(_index(c, cs, eps))
1035 except ValueError: # from ._index
1036 pass
1037 return False if cs else True
1038 else: # both null?
1039 return False if cs or co else True
1041 def _intersections(self):
1042 # Yield all intersections.
1043 for c in self._clips:
1044 for v in c._intersections():
1045 yield v
1047 def isequalTo(self, other, eps=None):
1048 '''Is this boolean/composite equal to an B{C{other}} within
1049 a given, I{non-negative} tolerance?
1051 @arg other: The other boolean/composite (C{Boolean[FHP|GB]}).
1052 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).
1054 @return: C{True} if equivalent, C{False} otherwise (C{bool}).
1056 @raise TypeError: Invalid B{C{other}}.
1058 @see: Method C{__eq__}.
1059 '''
1060 if isinstance(other, _CompositeBase):
1061 return self._equi(other, _eps0(eps))
1062 raise _IsnotError(_boolean_, _composite_, other=other)
1064 def _kwds(self, op, **more):
1065 # Get all keyword arguments as C{dict}.
1066 kwds = dict(raiser=self.raiser, eps=self.eps,
1067 name=self.name or op.__name__)
1068 kwds.update(more)
1069 return kwds
1071 @property_RO
1072 def _left_right_eps2(self):
1073 # Get the left and right C{x} bounds, oversized.
1074 return _min_max_eps2(min(v.x for v in self),
1075 max(v.x for v in self))
1077 def _points(self, may_be=True): # PYCHOK no cover
1078 # Yield all I{original} points, which may be intersections too.
1079 for c in self._clips:
1080 for v in c._points(may_be=may_be):
1081 yield v
1083 @property
1084 def raiser(self):
1085 '''Get the option to throw L{ClipError} exceptions (C{bool}).
1086 '''
1087 return self._raiser
1089 @raiser.setter # PYCHOK setter!
1090 def raiser(self, throw):
1091 '''Set the option to throw L{ClipError} exceptions (C{bool}).
1092 '''
1093 self._raiser = bool(throw)
1095 def _results(self, _presults, Clas, closed=False, inull=False, **eps):
1096 # Yield the dedup'd results, as L{ClipFHP4Tuple}s
1097 C = self._LL if Clas is None else Clas
1098 e = self._10eps(**eps)
1099 for clipid, ns in enumerate(_presults):
1100 f = p = v = None
1101 for n in ns:
1102 if f is None:
1103 yield n._toClas(C, clipid)
1104 f = p = n
1105 elif v is None:
1106 v = n # got f, p, v
1107 elif inull or p._2Abs(v, n, eps=e):
1108 yield v._toClas(C, clipid)
1109 p, v = v, n
1110 else: # null, colinear, ... skipped
1111 v = n
1112 if v and (inull or p._2Abs(v, f, eps=e)):
1113 yield v._toClas(C, clipid)
1114 p = v
1115 if f and p != f and closed: # close clip
1116 yield f._toClas(C, clipid)
1118 def _sum(self, other, op):
1119 # Combine this and an C{other} composite
1120 LL = self._LL
1121 sp = self.copy(name=self.name or op.__name__)
1122 sp._clips, sid = (), INT0 # new clips
1123 for cp in (self, other):
1124 for c in cp._clips:
1125 _ap = _Clip(sp, sid)._append
1126 for v in c._nodups:
1127 _ap(LL(v.y, v.x, v.height, sid))
1128 sid += 1
1129 return sp
1131 def _sum1(self, _a_p, *args, **kwds): # in .karney, .points
1132 # Sum the area or perimeter of all clips
1133 return _MODS.fsums.fsum1((_a_p(c, *args, **kwds) for c in self._clips), floats=True)
1135 def _sum2(self, LL, _a_p, *args, **kwds): # in .sphericalNvector, -Trigonometry
1136 # Sum the area or perimeter of all clips
1138 def _lls(clip): # convert clip to LLs
1139 _LL = LL
1140 for v in clip:
1141 yield _LL(v.lat, v.lon) # datum=Sphere
1143 return _MODS.fsums.fsum1((_a_p(_lls(c), *args, **kwds) for c in self._clips), floats=True)
1145 def toLatLon(self, LatLon=None, closed=False, **LatLon_kwds):
1146 '''Yield all (non-duplicate) points and intersections
1147 as an instance of B{C{LatLon}}.
1149 @kwarg LatLon: Class to use (C{LatLon}) or if C{None},
1150 L{LatLonFHP} or L{LatLonGH}.
1151 @kwarg closed: If C{True}, close each clip (C{bool}).
1152 @kwarg LatLon_kwds: Optional, additional B{C{LatLon}}
1153 keyword arguments, ignore if
1154 C{B{LatLon} is None}.
1156 @raise TypeError: Invalid B{C{LatLon}}.
1158 @note: For intersections, C{height} is an instance
1159 of L{HeightX}, otherwise of L{Height}.
1160 '''
1161 if LatLon is None:
1162 LL, kwds = self._LL, {}
1163 elif issubclassof(LatLon, _LatLonBool, LatLonBase):
1164 LL, kwds = LatLon, LatLon_kwds
1165 else:
1166 raise _TypeError(LatLon=LatLon)
1168 for c in self._clips:
1169 lf, cid = None, c._id
1170 for v in c._nodups:
1171 ll = LL(v.y, v.x, **kwds)
1172 ll._height = v.height
1173 if ll._clipid != cid:
1174 ll._clipid = cid
1175 yield ll
1176 if lf is None:
1177 lf = ll
1178 if closed and lf:
1179 yield lf
1182class _CompositeFHP(_CompositeBase):
1183 '''(INTERNAL) A list of clips representing a I{composite}
1184 of L{LatLonFHP} points, duplicates and intersections
1185 with an other I{composite}.
1186 '''
1187 _LL = LatLonFHP
1188 _Union = False
1190 def __init__(self, lls, raiser=False, **name_kind_eps):
1191 # New L{_CompositeFHP}.
1192 if raiser:
1193 self._raiser = True
1194 _CompositeBase.__init__(self, lls, **name_kind_eps)
1196 def _classify(self):
1197 # 2) Classify intersection chains.
1198 L = _L
1199 for v in self._intersections():
1200 n, b = v, v._label
1201 if b in L.RIGHT_LEFT_ON: # next chain
1202 while True:
1203 n._label = None # n.__dict__.pop('_label')
1204 n = n._next
1205 if n is v or n._label is not L.ON_ON: # n._label and ...
1206 break
1207 a = L.LEFT_ON if n._label is L.ON_LEFT else L.RIGHT_ON
1208 v._label = n._label = L.BOUNCING_D if a is b else L.CROSSING_D
1210 # 3) Copy labels
1211 for v in self._intersections():
1212 v._linked._label = v._label
1214 def _clip(self, corners, Union=False, Clas=None,
1215 **closed_inull_raiser_eps):
1216 # Clip this composite with another one, C{corners},
1217 # using Foster-Hormann-Popa's algorithm.
1218 P = self
1219 Q = self._class(corners, closed_inull_raiser_eps,
1220 eps=P._eps, raiser=False)
1221 if Union:
1222 P._Union = Q._Union = True
1224 bt = Q._bottom_top_eps2
1225 lr = Q._left_right_eps2
1226 # compute and insert intersections
1227 for p1, p2, Pc in P._edges3(**closed_inull_raiser_eps):
1228 if not (_outside(p1.x, p2.x, *lr) or
1229 _outside(p1.y, p2.y, *bt)):
1230 e = _EdgeFHP(p1, p2)
1231 if e._dp2 > EPS2: # non-null edge
1232 for q1, q2, Qc in Q._edges3(**closed_inull_raiser_eps):
1233 for T, p, q in e._intersect3(q1, q2):
1234 p = Pc._intersection(T, *p)
1235 q = Qc._intersection(T, *q)
1236 # assert not p._linked
1237 # assert not q._linked
1238 p._link(q)
1240 # label and classify intersections
1241 P._labelize()
1242 P._classify()
1244 # check for special cases
1245 P._special_cases(Q)
1246 Q._special_cases(P)
1247 # handle identicals
1248 P._special_identicals(Q)
1250 # set Entry/Exit flags
1251 P._set_entry_exits(Q)
1252 Q._set_entry_exits(P)
1254 # handle splits and crossings
1255 P._splits_xings(Q)
1257 # yield the results
1258 return P._results(P._presults(Q), Clas, **closed_inull_raiser_eps)
1260 @property_RO
1261 def _identicals(self):
1262 # Yield all clips marked C{._identical}.
1263 for c in self._clips:
1264 if c._identical:
1265 yield c
1267 def _labelize(self):
1268 # 1) Intersections classification
1269 for p in self._intersections():
1270 q = p._linked
1271 # determine local configuration at this intersection
1272 # and positions of Q- and Q+ relative to (P-, I, P+)
1273 p1, p3 = p._prev_next2
1274 q1, q3 = q._prev_next2
1275 t = (q1._RPoracle(p1, p, p3),
1276 q3._RPoracle(p1, p, p3))
1277 # check intersecting and overlapping cases
1278 p._label = _RP2L.get(t, None)
1280 def _presults(self, other):
1281 # Yield the result clips, each as a generator
1282 # of the L{_LatLonFHP}s in that clip
1283 for cp in (self, other):
1284 for c in cp._clips:
1285 if c._pushback:
1286 yield c._all()
1287 for c in self._clips:
1288 for X in c._Xings():
1289 yield self._resultX(X)
1291 def _resultX(self, X):
1292 # Yield the results from CROSSING C{X}.
1293 L, U, v = _L, self._Union, X
1294 while v:
1295 v._checked = True
1296 r = v # in P or Q
1297 s = L.Toggle[v._en_ex]
1298 e = (s is L.EXIT) ^ U
1299 while True:
1300 v = v._next if e else v._prev
1301 yield v
1302 v._checked = True
1303 if v._en_ex is s or v is X:
1304 break
1305 if v is r: # full circle
1306 raise ClipError(full_circle=v, clipid=v._clipid)
1307 if v is not X:
1308 v = v._linked
1309 if v is X:
1310 break
1312 def _set_entry_exits(self, other): # MCCABE 14
1313 # 4) Set entry/exit flags
1314 L, U = _L, self._Union
1315 for c in self._clips:
1316 n, k = c._point2(True)
1317 if n:
1318 f = n
1319 s = L.EXIT if n._isinside(other) else L.ENTRY
1320 t = L.EXIT # first_chain_vertex = True
1321 while True:
1322 if n.isintersection:
1323 b = n._label
1324 if b is L.CROSSING:
1325 n._en_ex = s
1326 s = L.Toggle[s]
1327 elif b is L.BOUNCING and ((s is L.EXIT) ^ U):
1328 n._2split = c # see ._splits_xings
1329 elif b is L.CROSSING_D:
1330 n._en_ex = s
1331 if (s is t) ^ U:
1332 n._label = L.CROSSING
1333 t = L.Toggle[t]
1334 if t is L.EXIT: # first_chain_vertex == True
1335 s = L.Toggle[s]
1336 elif b is L.BOUNCING_D:
1337 n._en_ex = s
1338 if (s is t) ^ U:
1339 n._2xing = True # see ._splits_xings
1340 s = L.Toggle[s]
1341 t = L.Toggle[t]
1342 n = n._next # _, n = n._prev_next2
1343 if n is f:
1344 break # PYCHOK attr?
1345 if k:
1346 c._remove2(k)
1348 def _special_cases(self, other):
1349 # 3.5) Check special cases
1350 U = self._Union
1351 for c in self._clips:
1352 if c._noXings(U):
1353 c._noInters = True
1354 if c._all_ON_ON:
1355 c._identical = True
1356 else:
1357 p, _ = c._point2(False)
1358 if p and (p._isinside(other) ^ U):
1359 c._pushback = True
1361 def _special_identicals(self, other):
1362 # 3.5) Handle identicals
1363 _u = _Clip._update_all
1364 cds = dict((c._id, _u(c)) for c in other._identicals)
1365 # assert len(cds) == len(other._identicals)
1366 if cds: # PYCHOK no cover
1367 for c in self._identicals:
1368 c._update_all()
1369 for v in c._intersections():
1370 d = cds.get(v._linked._clipid, None)
1371 if d and d._ishole is c._ishole:
1372 c._pushback = True
1373 break # next c
1375 @property_RO
1376 def _2splits(self):
1377 # Yield all intersections marked C{._2split}
1378 for p in self._intersections():
1379 if p._2split:
1380 # assert isinstance(p._2split, _Clip)
1381 yield p
1383 def _splits_xings(self, other): # MCCABE 15
1384 # 5) Handle split pairs and 6) crossing candidates
1386 def _2A_dup2(p, P): # PYCHOK unused
1387 p1, p2 = p._prev_next2
1388 ap = p1._2A(p, p2)
1389 Pc = p._2split
1390 # assert Pc in P._clips
1391 # assert p in Pc
1392 return ap, Pc._dup(p)
1394 def _links2(ps, qs): # PYCHOK P unused?
1395 # Yield each link as a 2-tuple(p, q)
1396 id_qs = set(map(id, qs))
1397 if id_qs:
1398 for p in ps:
1399 q = p._linked
1400 if q and id(q) in id_qs:
1401 yield p, q
1403 L = _L
1404 E = L.ENTRY if self._Union else L.EXIT
1405 X = L.Toggle[E]
1406 for p, q in _links2(self._2splits, other._2splits):
1407 ap, pp = _2A_dup2(p, self)
1408 aq, qq = _2A_dup2(q, other)
1409 if (ap * aq) > 0: # PYCHOK no cover
1410 p._link(qq) # overwrites ...
1411 q._link(pp) # ... p-q link
1412 else:
1413 pp._link(qq)
1414 p._en_ex = q._en_ex = E
1415 pp._en_ex = qq._en_ex = X
1416 p._label = pp._label = \
1417 q._label = qq._label = L.CROSSING
1419 for p, q in _links2(self._2xings, other._2xings):
1420 p._label = q._label = L.CROSSING
1422 @property_RO
1423 def _2xings(self):
1424 # Yield all intersections marked C{._2xing}
1425 for p in self._intersections():
1426 if p._2xing:
1427 yield p
1430class _CompositeGH(_CompositeBase):
1431 '''(INTERNAL) A list of clips representing a I{composite}
1432 of L{LatLonGH} points, duplicates and intersections
1433 with an other I{composite}.
1434 '''
1435 _LL = LatLonGH
1436 _xtend = False
1438 def __init__(self, lls, raiser=False, xtend=False, **name_kind_eps):
1439 # New L{_CompositeGH}.
1440 if xtend:
1441 self._xtend = True
1442 elif raiser:
1443 self._raiser = True
1444 _CompositeBase.__init__(self, lls, **name_kind_eps)
1446 def _clip(self, corners, s_entry, c_entry, Clas=None,
1447 **closed_inull_raiser_xtend_eps):
1448 # Clip this polygon with another one, C{corners}.
1450 # Core of Greiner/Hormann's algorithm, enhanced U{Correia's
1451 # <https://GitHub.com/helderco/univ-polyclip>} implementation***
1452 # and extended to optionally handle so-called "degenerate cases"
1453 S = self
1454 C = self._class(corners, closed_inull_raiser_xtend_eps,
1455 raiser=False, xtend=False)
1456 bt = C._bottom_top_eps2
1457 lr = C._left_right_eps2
1458 # 1. find intersections
1459 for s1, s2, Sc in S._edges3(**closed_inull_raiser_xtend_eps):
1460 if not (_outside(s1.x, s2.x, *lr) or
1461 _outside(s1.y, s2.y, *bt)):
1462 e = _EdgeGH(s1, s2, **closed_inull_raiser_xtend_eps)
1463 if e._hypot2 > EPS2: # non-null edge
1464 for c1, c2, Cc in C._edges3(**closed_inull_raiser_xtend_eps):
1465 for y, x, sa, ca in e._intersect4(c1, c2):
1466 s = Sc._insert(y, x, s1, s2, sa)
1467 c = Cc._insert(y, x, c1, c2, ca)
1468 s._link(c)
1470 # 2. identify entry/exit intersections
1471 if S._first:
1472 s_entry ^= S._first._isinside(C, *bt)
1473 for v in S._intersections():
1474 v._entry = s_entry = not s_entry
1476 if C._first:
1477 c_entry ^= C._first._isinside(S)
1478 for v in C._intersections():
1479 v._entry = c_entry = not c_entry
1481 # 3. yield the result(s)
1482 return S._results(S._presults(), Clas, **closed_inull_raiser_xtend_eps)
1484 @property_RO
1485 def _first(self):
1486 # Get the very first vertex of the first clip
1487 for v in self:
1488 return v
1489 return None # PYCHOK no cover
1491 def _kwds(self, op, **more):
1492 # Get the kwds C{dict}.
1493 return _CompositeBase._kwds(self, op, xtend=self.xtend, **more)
1495 def _presults(self):
1496 # Yield the unchecked intersection(s).
1497 for c in self._clips:
1498 for v in c._intersections():
1499 if not v._checked:
1500 yield self._resultU(v)
1502 def _resultU(self, v):
1503 # Yield the result from an un-checked intersection.
1504 while v and not v._checked:
1505 v._check()
1506 yield v
1507 r = v
1508 e = v._entry
1509 while True:
1510 v = v._next if e else v._prev
1511 yield v
1512 if v._linked:
1513 break
1514 if v is r:
1515 raise ClipError(full_circle=v, clipid=v._clipid)
1516 v = v._linked # switch
1518 @property
1519 def xtend(self):
1520 '''Get the option to handle I{degenerate cases} (C{bool}).
1521 '''
1522 return self._xtend
1524 @xtend.setter # PYCHOK setter!
1525 def xtend(self, xtend):
1526 '''Set the option to handle I{degenerate cases} (C{bool}).
1527 '''
1528 self._xtend = bool(xtend)
1531class _EdgeFHP(object):
1532 # An edge between two L{LatLonFHP} points.
1534 X_INTERSECT = _Enum('Xi', 1) # C++ enum
1535 X_OVERLAP = _Enum('Xo', 5)
1536 P_INTERSECT = _Enum('Pi', 3)
1537 P_OVERLAP = _Enum('Po', 7)
1538 Ps = (P_INTERSECT, P_OVERLAP, X_OVERLAP)
1539 Q_INTERSECT = _Enum('Qi', 2)
1540 Q_OVERLAP = _Enum('Qo', 6)
1541 Qs = (Q_INTERSECT, Q_OVERLAP, X_OVERLAP)
1542 V_INTERSECT = _Enum('Vi', 4)
1543 V_OVERLAP = _Enum('Vo', 8)
1544 Vs = (V_INTERSECT, V_OVERLAP)
1546 def __init__(self, p1, p2, **unused):
1547 # New edge between points C{p1} and C{p2}, each a L{LatLonFHP}.
1548 self._p1_p2 = p1, p2
1549 self._dp = dp = p2 - p1
1550 self._dp2 = dp * dp # dot product, hypot2
1552 self._lr, \
1553 self._bt = _left_right_bottom_top_eps2(p1, p2)
1555 def _intersect3(self, q1, q2):
1556 # Yield intersection(s) Type or C{None}
1557 if not (_outside(q1.x, q2.x, *self._lr) or
1558 _outside(q1.y, q2.y, *self._bt)):
1559 dq = q2 - q1
1560 dq2 = dq * dq # dot product, hypot2
1561 if dq2 > EPS2: # like ._clip
1562 T, E = None, _EdgeFHP # self.__class__
1563 p1, p2 = self._p1_p2
1564 ap1 = p1._2A(q1, q2)
1565 ap2_1 = p2._2A(q1, q2) - ap1
1566 if fabs(ap2_1) > _0_EPS: # non-parallel edges
1567 aq1 = q1._2A(p1, p2)
1568 aq2_1 = q2._2A(p1, p2) - aq1
1569 if fabs(aq2_1) > _0_EPS:
1570 # compute and classify alpha and beta
1571 a, a_0, a_0_1, _ = _alpha4(-ap1 / ap2_1)
1572 b, b_0, b_0_1, _ = _alpha4(-aq1 / aq2_1)
1573 # distinguish intersection types
1574 T = E.X_INTERSECT if a_0_1 and b_0_1 else (
1575 E.P_INTERSECT if a_0_1 and b_0 else (
1576 E.Q_INTERSECT if a_0 and b_0_1 else (
1577 E.V_INTERSECT if a_0 and b_0 else None)))
1579 elif fabs(ap1) < _0_EPS: # parallel or colinear edges
1580 dp = self._dp
1581 d1 = q1 - p1
1582 # compute and classify alpha and beta
1583 a, a_0, a_0_1, _a_0_1 = _alpha4((d1 * dp) / self._dp2)
1584 b, b_0, b_0_1, _b_0_1 = _alpha4((d1 * dq) / (-dq2))
1585 # distinguish overlap type
1586 T = E.X_OVERLAP if a_0_1 and b_0_1 else (
1587 E.P_OVERLAP if a_0_1 and _b_0_1 else (
1588 E.Q_OVERLAP if _a_0_1 and b_0_1 else (
1589 E.V_OVERLAP if a_0 and b_0 else None)))
1591 if T:
1592 if T is E.X_INTERSECT:
1593 v = p1 + a * self._dp
1594 yield T, (v, p1, p2, a), (v, q1, q2, b)
1595 elif T in E.Vs:
1596 yield T, (p1,), (q1,)
1597 else:
1598 if T in E.Qs:
1599 yield T, (p1,), (p1, q1, q2, b)
1600 if T in E.Ps:
1601 yield T, (q1, p1, p2, a), (q1,)
1604class _EdgeGH(object):
1605 # An edge between two L{LatLonGH} points.
1607 _raiser = False
1608 _xtend = False
1610 def __init__(self, s1, s2, raiser=False, xtend=False, **unused):
1611 # New edge between points C{s1} and C{s2}, each a L{LatLonGH}.
1612 self._s1, self._s2 = s1, s2
1613 self._x_sx_y_sy = (s1.x, s2.x - s1.x,
1614 s1.y, s2.y - s1.y)
1615 self._lr, \
1616 self._bt = _left_right_bottom_top_eps2(s1, s2)
1618 if xtend:
1619 self._xtend = True
1620 elif raiser:
1621 self._raiser = True
1623 def _alpha2(self, x, y, dx, dy):
1624 # Return C{(alpha)}, see .points.nearestOn5
1625 a = (y * dy + x * dx) / self._hypot2
1626 d = (y * dx - x * dy) / self._hypot0
1627 return a, fabs(d)
1629 def _Error(self, n, *args, **kwds): # PYCHOK no cover
1630 t = unstr(_EdgeGH.__name__, self._s1, self._s2)
1631 t = _DOT_(t, _EdgeGH._intersect4.__name__)
1632 t = unstr(t, *args, **kwds)
1633 return ClipError(_case_, n, txt=t)
1635 @Property_RO
1636 def _hypot0(self):
1637 _, sx, _, sy = self._x_sx_y_sy
1638 return hypot(sx, sy) * _0_EPS
1640 @Property_RO
1641 def _hypot2(self):
1642 _, sx, _, sy = self._x_sx_y_sy
1643 return hypot2(sx, sy)
1645 def _intersect4(self, c1, c2, parallel=True): # MCCABE 14
1646 # Yield the intersection(s) of this and another edge.
1648 # @return: None, 1 or 2 intersections, each a 4-Tuple
1649 # (y, x, s_alpha, c_alpha) with intersection
1650 # coordinates x and y and both alphas.
1652 # @raise ClipError: Intersection unhandled.
1654 # @see: U{Intersection point of two line segments
1655 # <http://PaulBourke.net/geometry/pointlineplane/>}.
1656 c1_x, c1_y = c1.x, c1.y
1657 if not (_outside(c1_x, c2.x, *self._lr) or
1658 _outside(c1_y, c2.y, *self._bt)):
1659 x, sx, \
1660 y, sy = self._x_sx_y_sy
1662 cx = c2.x - c1_x
1663 cy = c2.y - c1_y
1664 d = cy * sx - cx * sy
1666 if fabs(d) > _0_EPS: # non-parallel edges
1667 dx = x - c1_x
1668 dy = y - c1_y
1669 ca = (sx * dy - sy * dx) / d
1670 if _0_EPS < ca < _EPS_1 or (self._xtend and
1671 _EPS_0 < ca < _1_EPS):
1672 sa = (cx * dy - cy * dx) / d
1673 if _0_EPS < sa < _EPS_1 or (self._xtend and
1674 _EPS_0 < sa < _1_EPS):
1675 yield (y + sa * sy), (x + sa * sx), sa, ca
1677 # unhandled, "degenerate" cases 1, 2 or 3
1678 elif self._raiser and not (sa < _EPS_0 or sa > _1_EPS): # PYCHOK no cover
1679 raise self._Error(1, c1, c2, sa=sa) # intersection at s1 or s2
1681 elif self._raiser and not (ca < _EPS_0 or ca > _1_EPS): # PYCHOK no cover
1682 # intersection at c1 or c2 or at c1 or c2 and s1 or s2
1683 sa = (cx * dy - cy * dx) / d
1684 e = 2 if sa < _EPS_0 or sa > _1_EPS else 3
1685 raise self._Error(e, c1, c2, ca=ca)
1687 elif parallel and (sx or sy) and (cx or cy): # PYCHOK no cover
1688 # non-null, parallel or colinear edges
1689 sa1, d1 = self._alpha2(c1_x - x, c1_y - y, sx, sy)
1690 sa2, d2 = self._alpha2(c2.x - x, c2.y - y, sx, sy)
1691 if max(d1, d2) < _0_EPS:
1692 if self._xtend and not _outside(sa1, sa2, _EPS_0, _1_EPS):
1693 if sa1 > sa2: # anti-parallel
1694 sa1, sa2 = sa2, sa1
1695 ca1, ca2 = _1_0, _0_0
1696 else: # parallel
1697 ca1, ca2 = _0_0, _1_0
1698 ca = fabs((sx / cx) if cx else (sy / cy))
1699 # = hypot(sx, sy) / hypot(cx, cy)
1700 if sa1 < 0: # s1 is between c1 and c2
1701 ca *= ca1 + sa1
1702 yield y, x, ca1, _alpha1(ca)
1703 else: # c1 is between s1 and s2
1704 yield (y + sa1 * sy), (x + sa1 * sx), sa1, ca1
1705 if sa2 > 1: # s2 is between c1 and c2
1706 ca *= sa2 - _1_0
1707 yield (y + sy), (x + sx), ca2, _alpha1(ca2 - ca)
1708 else: # c2 is between s1 and s2
1709 yield (y + sa2 * sy), (x + sa2 * sx), sa2, ca2
1710 elif self._raiser and not _outside(sa1, sa2, _0_0, _1_EPS):
1711 raise self._Error(4, c1, c2, d1=d1, d2=d2)
1714class _BooleanBase(object):
1715 # Shared C{Boolean[FHP|GH]} methods.
1717 def __add__(self, other):
1718 '''Sum: C{this + other} clips.
1719 '''
1720 return self._sum(_other(self, other), self.__add__) # PYCHOK OK
1722 def __and__(self, other):
1723 '''Intersection: C{this & other}.
1724 '''
1725 return self._boolean(other, False, False, self.__and__) # PYCHOK OK
1727 def __iadd__(self, other):
1728 '''In-place sum: C{this += other} clips.
1729 '''
1730 return self._inplace(self.__add__(other))
1732 def __iand__(self, other):
1733 '''In-place intersection: C{this &= other}.
1734 '''
1735 return self._inplace(self.__and__(other))
1737 def __ior__(self, other):
1738 '''In-place union: C{this |= other}.
1739 '''
1740 return self._inplace(self.__or__(other))
1742 def __or__(self, other):
1743 '''Union: C{this | other}.
1744 '''
1745 return self._boolean(other, True, True, self.__or__) # PYCHOK OK
1747 def __radd__(self, other):
1748 '''Reverse sum: C{other + this} clips.
1749 '''
1750 return _other(self, other)._sum(self, self.__radd__)
1752 def __rand__(self, other):
1753 '''Reverse intersection: C{other & this}
1754 '''
1755 return _other(self, other).__and__(self)
1757 def __ror__(self, other):
1758 '''Reverse union: C{other | this}
1759 '''
1760 return _other(self, other).__or__(self)
1762 def _boolean4(self, other, op):
1763 # Set up a new C{Boolean[FHP|GH]}.
1764 C = self.__class__
1765 kwds = C._kwds(self, op)
1766 a = C(self, **kwds)
1767 b = _other(self, other)
1768 return a, b, C, kwds
1770 def _inplace(self, r):
1771 # Replace this with a L{Boolean*} result.
1772 self._clips, r._clips = r._clips, None
1773# if self._raiser != r._raiser:
1774# self._raiser = r._raiser
1775# if self._xtend != r._xtend:
1776# self._xtend = r._xtend
1777# if self._eps != r._eps:
1778# self._eps = r._eps
1779 return self
1782class BooleanFHP(_CompositeFHP, _BooleanBase):
1783 '''I{Composite} class providing I{boolean} operations between two
1784 I{composites} using U{Forster-Hormann-Popa<https://www.ScienceDirect.com/
1785 science/article/pii/S259014861930007X>}'s C++ implementation, transcoded
1786 to pure Python.
1788 The supported operations between (composite) polygon A and B are:
1790 - C = A & B or A &= B, intersection of A and B
1792 - C = A + B or A += B, sum of A and B clips
1794 - C = A | B or A |= B, union of A and B
1796 - A == B or A != B, equivalent A and B clips
1798 - A.isequalTo(B, eps), equivalent within tolerance
1800 @see: Methods C{__eq__} and C{isequalTo}, function L{clipFHP4}
1801 and class L{BooleanGH}.
1802 '''
1803 _kind = _boolean_
1805 def __init__(self, lls, raiser=False, eps=EPS, **name):
1806 '''New L{BooleanFHP} operand for I{boolean} operation.
1808 @arg lls: The polygon points and clips (iterable of L{LatLonFHP}s,
1809 L{ClipFHP4Tuple}s or other C{LatLon}s).
1810 @kwarg raiser: If C{True}, throw L{ClipError} exceptions (C{bool}).
1811 @kwarg esp: Tolerance for eliminating null edges (C{degrees}, same
1812 units as the B{C{lls}} coordinates).
1813 @kwarg name: Optional name (C{str}).
1814 '''
1815 _CompositeFHP.__init__(self, lls, raiser=raiser, eps=eps, **name)
1817 def __isub__(self, other):
1818 '''Not implemented.'''
1819 return _NotImplemented(self, other)
1821 def __rsub__(self, other):
1822 '''Not implemented.'''
1823 return _NotImplemented(self, other)
1825 def __sub__(self, other):
1826 '''Not implemented.'''
1827 return _NotImplemented(self, other)
1829 def _boolean(self, other, Union, unused, op):
1830 # One C{BooleanFHP} operation.
1831 p, q, C, kwds = self._boolean4(other, op)
1832 r = p._clip(q, Union=Union, **kwds)
1833 return C(r, **kwds)
1836class BooleanGH(_CompositeGH, _BooleanBase):
1837 '''I{Composite} class providing I{boolean} operations between two
1838 I{composites} using the U{Greiner-Hormann<http://www.Inf.USI.CH/
1839 hormann/papers/Greiner.1998.ECO.pdf>} algorithm and U{Correia
1840 <https://GitHub.com/helderco/univ-polyclip>}'s implementation,
1841 modified and extended.
1843 The supported operations between (composite) polygon A and B are:
1845 - C = A - B or A -= B, difference A less B
1847 - C = B - A or B -= A, difference B less B
1849 - C = A & B or A &= B, intersection of A and B
1851 - C = A + B or A += B, sum of A and B clips
1853 - C = A | B or A |= B, union of A and B
1855 - A == B or A != B, equivalent A and B clips
1857 - A.isequalTo(B, eps), equivalent within tolerance
1859 @note: To handle I{degenerate cases} like C{point-edge} and
1860 C{point-point} intersections, use class L{BooleanFHP}.
1862 @see: Methods C{__eq__} and C{isequalTo}, function L{clipGH4}
1863 and class L{BooleanFHP}.
1864 '''
1865 _kind = _boolean_
1867 def __init__(self, lls, raiser=True, xtend=False, eps=EPS, **name):
1868 '''New L{BooleanFHP} operand for I{boolean} operation.
1870 @arg lls: The polygon points and clips (iterable of L{LatLonGH}s,
1871 L{ClipGH4Tuple}s or other C{LatLon}s).
1872 @kwarg raiser: If C{True}, throw L{ClipError} exceptions (C{bool}).
1873 @kwarg xtend: If C{True}, extend edges of I{degenerate cases}, an
1874 attempt to handle the latter (C{bool}).
1875 @kwarg esp: Tolerance for eliminating null edges (C{degrees}, same
1876 units as the B{C{lls}} coordinates).
1877 @kwarg name: Optional name (C{str}).
1878 '''
1879 _CompositeGH.__init__(self, lls, raiser=raiser, xtend=xtend, eps=eps, **name)
1881 def _boolean(self, other, s_entry, c_entry, op):
1882 # One C{BooleanGH} operation.
1883 s, c, C, kwds = self._boolean4(other, op)
1884 r = s._clip(c, s_entry, c_entry, **kwds)
1885 return C(r, **kwds)
1887 def __isub__(self, other):
1888 '''In-place difference: C{this -= other}.
1889 '''
1890 return self._inplace(self.__sub__(other))
1892 def __rsub__(self, other):
1893 ''' Reverse difference: C{other - this}
1894 '''
1895 return _other(self, other).__sub__(self)
1897 def __sub__(self, other):
1898 '''Difference: C{this - other}.
1899 '''
1900 return self._boolean(other, True, False, self.__sub__)
1903def _alpha1(alpha):
1904 # Return C{alpha} in C{[0..1]} range
1905 if _EPS_0 < alpha < _1_EPS:
1906 return max(_0_0, min(alpha, _1_0))
1907 t = _not_(Fmt.SQUARE(_ELLIPSIS_(0, 1)))
1908 raise ClipError(_alpha_, alpha, txt=t)
1911def _alpha4(a):
1912 # Return 4-tuple (alpha, -EPS < alpha < EPS,
1913 # 0 < alpha < 1,
1914 # not 0 < alpha < 1)
1915 return (a, False, True, False) if _0_EPS < a < _EPS_1 else (
1916 (a, False, False, True) if _0_EPS < fabs(a) else
1917 (a, True, False, False))
1920def _Cps(Cp, composites_points, where):
1921 # Yield composites and points as a C{Cp} composite.
1922 try:
1923 kwds = dict(kind=_points_, name__=where)
1924 for cp in composites_points:
1925 yield cp if isBoolean(cp) else Cp(cp, **kwds)
1926 except (AttributeError, ClipError, TypeError, ValueError) as x:
1927 raise _ValueError(points=cp, cause=x)
1930def _eps0(eps):
1931 # Adjust C{eps} or C{None}.
1932 return eps if eps and eps > EPS else 0
1935def isBoolean(obj):
1936 '''Check for C{Boolean} composites.
1938 @arg obj: The object (any C{type}).
1940 @return: C{True} if B{C{obj}} is L{BooleanFHP},
1941 L{BooleanGH} oe some other composite,
1942 C{False} otherwise.
1943 '''
1944 return isinstance(obj, _CompositeBase)
1947def _left_right_bottom_top_eps2(p1, p2):
1948 '''(INTERNAL) Return 2-tuple C{(left, right), (bottom, top)}, oversized.
1949 '''
1950 return (_min_max_eps2(p1.x, p2.x),
1951 _min_max_eps2(p1.y, p2.y))
1954def _low_high_eps2(lo, hi, eps):
1955 '''(INTERNAL) Return 2-tuple C{(lo, hi)}, oversized.
1956 '''
1957 lo *= (_1_0 + eps) if lo < 0 else (_1_0 - eps)
1958 hi *= (_1_0 - eps) if hi < 0 else (_1_0 + eps)
1959 return (lo or -eps), (hi or eps)
1962def _min_max_eps2(*xs):
1963 '''(INTERNAL) Return 2-tuple C{(min, max)}, oversized.
1964 '''
1965 lo, hi = min(xs), max(xs)
1966 lo *= _1_EPS if lo < 0 else _EPS_1
1967 hi *= _EPS_1 if hi < 0 else _1_EPS
1968 return (lo or _EPS_0), (hi or _0_EPS)
1971def _other(this, other):
1972 '''(INTERNAL) Check for compatible C{type}s.
1973 '''
1974 C = this.__class__
1975 if isinstance(other, C):
1976 return other
1977 raise _IsnotError(C.__name__, other=other)
1980def _outside(x1, x2, lo, hi):
1981 '''(INTERNAL) Is C{(x1, x2)} outside C{(lo, hi)}?
1982 '''
1983 return max(x1, x2) < lo or min(x1, x2) > hi
1986__all__ += _ALL_DOCS(_BooleanBase, _Clip,
1987 _CompositeBase, _CompositeFHP, _CompositeGH,
1988 _LatLonBool)
1990# **) MIT License
1991#
1992# Copyright (C) 2018-2024 -- mrJean1 at Gmail -- All Rights Reserved.
1993#
1994# Permission is hereby granted, free of charge, to any person obtaining a
1995# copy of this software and associated documentation files (the "Software"),
1996# to deal in the Software without restriction, including without limitation
1997# the rights to use, copy, modify, merge, publish, distribute, sublicense,
1998# and/or sell copies of the Software, and to permit persons to whom the
1999# Software is furnished to do so, subject to the following conditions:
2000#
2001# The above copyright notice and this permission notice shall be included
2002# in all copies or substantial portions of the Software.
2003#
2004# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
2005# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2006# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
2007# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
2008# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
2009# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
2010# OTHER DEALINGS IN THE SOFTWARE.
2012# ***) GNU GPL 3
2013#
2014# Copyright (C) 2011-2012 Helder Correia <Helder.MC@Gmail.com>
2015#
2016# This program is free software: you can redistribute it and/or
2017# modify it under the terms of the GNU General Public License as
2018# published by the Free Software Foundation, either version 3 of
2019# the License, or any later version.
2020#
2021# This program is distributed in the hope that it will be useful,
2022# but WITHOUT ANY WARRANTY; without even the implied warranty of
2023# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2024# GNU General Public License for more details.
2025#
2026# You should have received a copy of the GNU General Public License
2027# along with this program. If not, see <http://www.GNU.org/licenses/>.
2028#
2029# You should have received the README file along with this program.
2030# If not, see <https://GitHub.com/helderco/univ-polyclip>.