Coverage for pygeodesy/booleans.py: 94%
973 statements
« prev ^ index » next coverage.py v7.2.2, created at 2023-04-12 11:45 -0400
« prev ^ index » next coverage.py v7.2.2, created at 2023-04-12 11:45 -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 _ValueError, _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_, _not_, \
29 _points_, _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, unstr
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.04.02'
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}
110class _LatLonBool(_Named):
111 '''(INTERNAL) Base class for L{LatLonFHP} and L{LatLonGH}.
112 '''
113 _alpha = None # point AND intersection else length
114 _checked = False # checked in phase 3 iff intersection
115 _clipid = INT0 # (polygonal) clip identifier, number
116 _dupof = None # original of a duplicate
117# _e_x_str = NN # shut up PyChecker
118 _height = Height(0) # interpolated height, usually meter
119 _linked = None # link to neighbor iff intersection
120 _next = None # link to the next vertex
121 _prev = None # link to the previous vertex
123 def __init__(self, lat_ll, lon=None, height=0, clipid=INT0, name=NN):
124 '''New C{LatLon[FHP|GH]} from separate C{lat}, C{lon}, C{height}
125 and C{clipid} scalars or from a previous C{LatLon[FHP|GH]},
126 a C{Clip[FHP|GH]4Tuple} or some other C{LatLon} instance.
128 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude
129 (C{LatLon[FHP|GH]}, aC{Clip[FHP|GH]4Tuple}
130 or some other C{LatLon}).
131 @kwarg lon: Longitude (C{scalar}), iff B{C{lat_ll}} is
132 scalar, ignored otherwise.
133 @kwarg height: Height (C{scalar}), conventionally C{meter}.
134 @kwarg clipid: Clip identifier (C{int}).
135 @kwarg name: Optional name (C{str}).
136 '''
137 if lon is None:
138 self.y, self.x = lat_ll.lat, lat_ll.lon
139 h = getattr(lat_ll, _height_, height)
140 c = getattr(lat_ll, _clipid_, clipid)
141 else:
142 self.y, self.x = lat_ll, lon
143 h, c = height, clipid
144 # don't duplicate defaults
145 if self._height != h:
146 self._height = h
147 if self._clipid != c:
148 self._clipid = c
149 if name:
150 self.name = name
152 def __abs__(self):
153 return max(fabs(self.x), fabs(self.y))
155 def __eq__(self, other):
156 return other is self or bool(_other(self, other) and
157 other.x == self.x and
158 other.y == self.y)
160 def __ne__(self, other): # required for Python 2
161 return not self.__eq__(other)
163 def __repr__(self):
164 '''String C{repr} of this lat-/longitude.
165 '''
166 if self._prev or self._next:
167 t = _ELLIPSIS_(self._prev, self._next)
168 t = _SPACE_(self, Fmt.ANGLE(t))
169 else:
170 t = str(self)
171 return t
173 def __str__(self):
174 '''String C{str} of this lat-/longitude.
175 '''
176 t = (_lat_, self.lat), (_lon_, self.lon)
177 if self._height:
178 X = _X_ if self.isintersection else NN
179 t += (_height_ + X, self._height),
180 if self._clipid:
181 t += (_clipid_, self._clipid),
182 if self._alpha is not None:
183 t += (_alpha_, self._alpha),
184# if self._dupof: # recursion risk
185# t += (_dupof_, self._dupof.name),
186 t = pairs(t, prec=8, fmt=Fmt.g, ints=True)
187 t = Fmt.PAREN(_COMMASPACE_.join(t))
188 if self._linked:
189 k = _DOT_ if self._checked else _BANG_
190 t = NN(t, self._e_x_str(k)) # PYCHOK expected
191 return NN(self.name, t)
193 def __sub__(self, other):
194 _other(self, other)
195 return self.__class__(self.y - other.y, # classof
196 self.x - other.x)
198 def _2A(self, p2, p3):
199 # I{Signed} area of a triangle, I{doubled}.
200 x, y = self.x, self.y
201 return (p2.x - x) * (p3.y - y) - \
202 (p3.x - x) * (p2.y - y)
204 def _2Abs(self, p2, p3, eps=_10EPS):
205 # I{Unsigned} area of a triangle, I{doubled}
206 # or 0 if below the given threshold C{eps}.
207 a = fabs(self._2A(p2, p3))
208 return 0 if a < eps else a
210 @property_RO
211 def clipid(self):
212 '''Get the I{clipid} (C{int} or C{0}).
213 '''
214 return self._clipid
216 def _equi(self, llb, eps):
217 # Is this LLB I{equivalent} to B{C{llb}} within
218 # the given I{non-negative} tolerance B{C{eps}}?
219 return not (fabs(llb.lon - self.x) > eps or
220 fabs(llb.lat - self.y) > eps)
222 @property_RO
223 def height(self):
224 '''Get the I{height} (C{Height} or C{int}).
225 '''
226 h = self._height
227 return HeightX(h) if self.isintersection else (
228 Height(h) if h else _LatLonBool._height)
230 def isequalTo(self, other, eps=None):
231 '''Is this point equal to an B{C{other}} within a given,
232 I{non-negative} tolerance, ignoring C{height}?
234 @arg other: The other point (C{LatLon}).
235 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).
237 @return: C{True} if equivalent, C{False} otherwise (C{bool}).
239 @raise TypeError: Invalid B{C{other}}.
240 '''
241 try:
242 return self._equi(other, _eps0(eps))
243 except (AttributeError, TypeError, ValueError):
244 raise _IsnotError(_LatLon_, other=other)
246 @property_RO
247 def isintersection(self):
248 '''Is this an intersection? May be C{ispoint} too!
249 '''
250 return bool(self._linked)
252 @property_RO
253 def ispoint(self):
254 '''Is this an I{original} point? May be C{isintersection} too!
255 '''
256 return self._alpha is None
258 @property_RO
259 def lat(self):
260 '''Get the latitude (C{scalar}).
261 '''
262 return self.y
264 def _link(self, other):
265 # Make this and an other point are neighbors.
266 # assert _other(self, other)
267 self._linked = other
268 other._linked = self
270 @property_RO
271 def lon(self):
272 '''Get the longitude (C{scalar}).
273 '''
274 return self.x
276 def _toClas(self, Clas, clipid):
277 # Return this vertex as a C{Clas} instance
278 # (L{Clip[FHP|GH]4Tuple} or L{LatLon[FHP|GH]}).
279 return Clas(self.lat, self.lon, self.height, clipid)
282class LatLonFHP(_LatLonBool):
283 '''A point or intersection in a L{BooleanFHP} clip or composite.
284 '''
285 _en_ex = None
286 _label = None
287 _2split = None # or C{._Clip}
288 _2xing = False
290 def __init__(self, lat_ll, *lon_h_clipid, **name):
291 '''New C{LatLonFHP} from separate C{lat}, C{lon}, C{h}eight
292 and C{clipid} scalars, or from a previous L{LatLonFHP},
293 a L{ClipFHP4Tuple} or some other C{LatLon} instance.
295 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude
296 (L{LatLonFHP}, C{LatLon} or L{ClipFHP4Tuple}).
297 @arg lon_h_clipid: Longitude (C{scalar}), C{h}eight and
298 C{clipid} iff B{C{lat_ll}} is scalar,
299 ignored otherwise.
300 @kwarg name: Optional name (C{str}).
301 '''
302 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **name)
304 def __add__(self, other):
305 _other(self, other)
306 return self.__class__(self.y + other.y, self.x + other.x)
308 def __mod__(self, other): # cross product
309 _other(self, other)
310 return self.x * other.y - self.y * other.x
312 def __mul__(self, other): # dot product
313 _other(self, other)
314 return self.x * other.x + self.y * other.y
316 def __rmul__(self, other): # scalar product
317 if not isscalar(other):
318 raise _IsnotError(_scalar_, other=other)
319 return self.__class__(self.y * other, self.x * other)
321 def _e_x_str(self, t): # PYCHOK no cover
322 if self._label:
323 t = NN(self._label, t)
324 if self._en_ex:
325 t = NN(t, self._en_ex)
326 return t
328 @property_RO
329 def _isduplicate(self):
330 # Is this point a I{duplicate} intersection?
331 p = self._dupof
332 return bool(p and self._linked
333 and p is not self
334 and p == self
335# and p._alpha in (None, self._alpha)
336 and self._alpha in (_0_0, p._alpha))
338# @property_RO
339# def _isduplicated(self):
340# # Return the number of I{duplicates}?
341# d, v = 0, self
342# while v:
343# if v._dupof is self:
344# d += 1
345# v = v._next
346# if v is self:
347# break
348# return d
350 def isenclosedBy(self, *composites_points):
351 '''Is this point inside one or more composites or polygons based
352 the U{winding number<https://www.ScienceDirect.com/science/
353 article/pii/S0925772101000128>}?
355 @arg composites_points: Composites and/or iterables of points
356 (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, L{LatLonFHP},
357 L{LatLonGH} or any C{LatLon}).
359 @raise ValueError: Some B{C{points}} invalid.
361 @see: U{Algorithm 6<https://www.ScienceDirect.com/science/
362 article/pii/S0925772101000128>}.
363 '''
364 class _Clips(object):
365 # Pseudo-_CompositeBase._clips tuple
367 @property_RO
368 def _clips(self):
369 for cp in _Cps(_CompositeFHP, composites_points,
370 LatLonFHP.isenclosedBy): # PYCHOK yield
371 for c in cp._clips:
372 yield c
374 return self._isinside(_Clips())
376 def _isinside(self, composite, *excludes):
377 # Is this point inside a composite I{winding number},
378 # excluding certain C{_Clip}s?
379 x, y, i = self.x, self.y, False
380 for c in composite._clips:
381 if c not in excludes:
382 w = 0
383 for p1, p2 in c._edges2():
384 # edge [p1,p2] must straddle y
385 if (p1.y < y) is not (p2.y < y): # or ^
386 r = p2.x > x
387 s = p2.y > p1.y
388 if p1.x < x:
389 b = r and (s is (p1._2A(p2, self) > 0))
390 else:
391 b = r or (s is (p1._2A(p2, self) > 0))
392 if b:
393 w += 1 if s else -1
394 if isodd(w):
395 i = not i
396 return i
398 @property_RO
399 def _prev_next2(self):
400 # Adjust 2-tuple (._prev, ._next) iff a I{duplicate} intersection
401 p, n = self, self._next
402 if self._isduplicate:
403 p = self._dupof
404 while p._isduplicate:
405 p = p._dupof
406 while n._isduplicate:
407 n = n._next
408 return p._prev, n
410# def _edge2(self):
411# # Return the start and end point of the
412# # edge containing I{intersection} C{v}.
413# n = p = self
414# while p.isintersection:
415# p = p._prev
416# if p is self:
417# break
418# while n.isintersection:
419# n = n._next
420# if n is self:
421# break
422# # assert p == self or not p._2Abs(self, n)
423# return p, n
425 def _RPoracle(self, p1, p2, p3):
426 # Relative Position oracle
427 if p1._linked is self: # or p1._linked2(self):
428 T = _RP.IS_Pm
429 elif p3._linked is self: # or p3._linked2(self):
430 T = _RP.IS_Pp
431 elif p1._2A(p2, p3) > 0: # left turn
432 T = _RP.LEFT if self._2A(p1, p2) > 0 and \
433 self._2A(p2, p3) > 0 else \
434 _RP.RIGHT # PYCHOK indent
435 else: # right turn (or straight)
436 T = _RP.RIGHT if self._2A(p1, p2) < 0 and \
437 self._2A(p2, p3) < 0 else \
438 _RP.LEFT # PYCHOK indent
439 return T
442class LatLonGH(_LatLonBool):
443 '''A point or intersection in a L{BooleanGH} clip or composite.
444 '''
445 _entry = None # entry or exit iff intersection
447 def __init__(self, lat_ll, *lon_h_clipid, **name):
448 '''New C{LatLonGH} from separate C{lat}, C{lon}, C{h}eight
449 and C{clipid} scalars, or from a previous L{LatLonGH},
450 L{ClipGH4Tuple} or some other C{LatLon} instance.
452 @arg lat_ll: Latitude (C{scalar}) or a lat/longitude
453 (L{LatLonGH}, C{LatLon} or L{ClipGH4Tuple}).
454 @arg lon_h_clipid: Longitude (C{scalar}), C{h}eight and
455 C{clipid} iff B{C{lat_ll}} is scalar,
456 ignored otherwise.
457 @kwarg name: Optional name (C{str}).
458 '''
459 _LatLonBool.__init__(self, lat_ll, *lon_h_clipid, **name)
461 def _check(self):
462 # Check-mark this vertex and its link.
463 self._checked = True
464 k = self._linked
465 if k and not k._checked:
466 k._checked = True
468 def _e_x_str(self, t): # PYCHOK no cover
469 return t if self._entry is None else NN(t,
470 (_e_ if self._entry else _x_))
472 def isenclosedBy(self, *composites_points):
473 '''Is this point inside one or more composites or polygons based
474 on the U{even-odd-rule<https://www.ScienceDirect.com/science/
475 article/pii/S0925772101000128>}?
477 @arg composites_points: Composites and/or iterables of points
478 (L{ClipFHP4Tuple}, L{ClipGH4Tuple}, L{LatLonFHP},
479 L{LatLonGH} or any C{LatLon}).
481 @raise ValueError: Some B{C{points}} invalid.
482 '''
483 class _Edges(object):
484 # Pseudo-_CompositeBase._edges3 method
486 def _edges3(self, **kwds):
487 for cp in _Cps(_CompositeGH, composites_points,
488 LatLonGH.isenclosedBy): # PYCHOK yield
489 for e in cp._edges3(**kwds):
490 yield e
492 return self._isinside(_Edges())
494 def _isinside(self, composite, *bottom_top):
495 # Is this vertex inside the composite I{even-odd rule}?
497 def _x(y, p1, p2):
498 # return C{x} at given C{y} on edge [p1,p2]
499 return (y - p1.y) / (p2.y - p1.y) * (p2.x - p1.x)
501 # The I{even-odd} rule counts the number of edges
502 # intersecting a ray emitted from this point to
503 # east-bound infinity. When I{odd} this point lies
504 # inside, if I{even} outside.
505 o, y = False, self.y
506 if not (bottom_top and _outside(y, y, *bottom_top)):
507 x = self.x
508 for p1, p2, _ in composite._edges3():
509 if (p1.y < y) is not (p2.y < y): # or ^
510 r = p2.x > x
511 if p1.x < x:
512 b = r and (_x(y, p1, p2) > x)
513 else:
514 b = r or (_x(y, p1, p2) > x)
515 if b:
516 o = not o
517 return o
520class _Clip(_Named):
521 '''(INTERNAL) A I{doubly-linked} list representing a I{closed}
522 polygon of L{LatLonFHP} or L{LatLonGH} points, duplicates
523 and intersections with other clips.
524 '''
525 _composite = None
526 _dups = 0
527 _first = None
528 _id = 0
529 _identical = False
530 _noInters = False
531 _last = None
532 _LL = None
533 _len = 0
534 _pushback = False
536 def __init__(self, composite, clipid=INT0):
537 '''(INTERNAL) New C{_Clip}.
538 '''
539 # assert isinstance(composite, _CompositeBase)
540 if clipid in composite._clipids:
541 raise ClipError(clipid=clipid, txt=_duplicate_)
542 self._composite = composite
543 self._id = clipid
544 self._LL = composite._LL
545 composite._clips = composite._clips + (self,)
547 def __contains__(self, point): # PYCHOK no cover
548 '''Is the B{C{point}} in this clip?
549 '''
550 for v in self:
551 if v is point: # or ==?
552 return True
553 return False
555 def __eq__(self, other):
556 '''Is this clip I{equivalent} to an B{C{other}} clip,
557 do both have the same C{len}, the same points, in
558 the same order, possibly rotated?
559 '''
560 return self._equi(_other(self, other), 0)
562 def __ge__(self, other):
563 '''See method C{__lt__}.
564 '''
565 return not self.__lt__(other)
567 def __gt__(self, other):
568 '''Is this clip C{"above"} an B{C{other}} clip,
569 located or stretched farther North or East?
570 '''
571 return self._bltr4 > _other(self, other)._bltr4
573 def __hash__(self): # PYCHOK no over
574 return hash(self._bltr4)
576 def __iter__(self):
577 '''Yield the points, duplicates and intersections.
578 '''
579 v = f = self._first
580 while v:
581 yield v
582 v = v._next
583 if v is f:
584 break
586 def __le__(self, other):
587 '''See method C{__gt__}.
588 '''
589 return not self.__gt__(other)
591 def __len__(self):
592 '''Return the number of points, duplicates and
593 intersections in this clip.
594 '''
595 return self._len
597 def __lt__(self, other):
598 '''Is this clip C{"below"} an B{C{other}} clip,
599 located or stretched farther South or West?
600 '''
601 return self._bltr4 < _other(self, other)._bltr4
603 def __ne__(self, other): # required for Python 2
604 '''See method C{__eq__}.
605 '''
606 return not self.__eq__(other)
608 _all = __iter__
610 @property_RO
611 def _all_ON_ON(self):
612 # Check whether all vertices are ON_ON.
613 L_ON_ON = _L.ON_ON
614 return all(v._label is L_ON_ON for v in self)
616 def _append(self, y_v, *x_h_clipid):
617 # Append a point given as C{y}, C{x}, C{h}eight and
618 # C{clipid} args or as a C{LatLon[FHP|GH]}.
619 self._last = v = self._LL(y_v, *x_h_clipid) if x_h_clipid else y_v
620 self._len += 1
621 # assert v._clipid == self._id
623 v._next = n = self._first
624 if n is None: # set ._first
625 self._first = p = n = v
626 else: # insert before ._first
627 v._prev = p = n._prev
628 p._next = n._prev = v
629 return v
631# def _appendedup(self, v, clipid=0):
632# # Like C{._append}, but only append C{v} if not a
633# # duplicate of the one previously append[edup]'ed.
634# y, x, p = v.y, v.x, self._last
635# if p is None or y != p.y or x != p.x or clipid != p._clipid:
636# p = self._append(y, x, v._height, clipid)
637# if v._linked:
638# p._linked = True # to force errors
639# return p
641 @Property_RO
642 def _bltr4(self):
643 # Get the bounds as 4-tuple C{(bottom, left, top, right)}.
644 return map2(float, _MODS.points.boundsOf(self, wrap=False))
646 def _bltr4eps(self, eps):
647 # Get the ._bltr4 bounds tuple, oversized.
648 if eps > 0: # > EPS
649 yb, xl, yt, xr = self._bltr4
650 yb, yt = _low_high_eps2(yb, yt, eps)
651 xl, xr = _low_high_eps2(xl, xr, eps)
652 t = yb, xl, yt, xr
653 else:
654 t = self._bltr4
655 return t
657 def _closed(self, raiser): # PYCHOK unused
658 # End a clip, un-close it and check C{len}.
659 p, f = self._last, self._first
660 if f and f._prev is p and p is not f and \
661 p._next is f and p == f: # PYCHOK no cover
662 # un-close the clip
663 f._prev = p = p._prev
664 p._next = f
665 self._len -= 1
666# elif f and raiser:
667# raise self._OpenClipError(p, f)
668 if len(self) < 3:
669 raise self._Error(_too_(_few_))
671 def _dup(self, q):
672 # Duplicate a point (or intersection) as intersection.
673 v = self._insert(q.y, q.x, q)
674 v._alpha = q._alpha or _0_0 # _0_0 replaces None
675 v._dupof = q._dupof or q
676 # assert v._prev is q
677 # assert q._next is v
678 return v
680 def _edges2(self, **unused):
681 # Yield each I{original} edge as a 2-tuple
682 # (p1, p2), a pair of C{LatLon[FHP|GH])}s.
683 p1 = p2 = f = self._first
684 while p2:
685 p2 = p2._next
686 if p2.ispoint:
687 yield p1, p2
688 p1 = p2
689 if p2 is f:
690 break
692 def _equi(self, clip, eps):
693 # Is this clip I{equivalent} to B{C{clip}} within
694 # the given I{non-negative} tolerance B{C{eps}}?
695 r, f = len(self), self._first
696 if f and r == len(clip) and self._bltr4eps(eps) \
697 == clip._bltr4eps(eps):
698 _equi = _LatLonBool._equi
699 for v in clip:
700 if _equi(f, v, eps):
701 s, n = f, v
702 for _ in range(r):
703 s, n = s._next, n._next
704 if not _equi(s, n, eps):
705 break # next v
706 else: # equivalent
707 return True
708 return False
710 def _Error(self, txt): # PYCHOK no cover
711 # Build a C{ClipError} instance
712 kwds = dict(len=len(self), txt=txt)
713 if self._dups:
714 kwds.update(dups=self._dups)
715 cp = self._composite
716 if self._id:
717 try:
718 i = cp._clips.index(self)
719 if i != self._id:
720 kwds[_clip_] = i
721 except ValueError:
722 pass
723 kwds[_clipid_] = self._id
724 return ClipError(cp._kind, cp.name, **kwds)
726 def _index(self, clips, eps):
727 # see _CompositeBase._equi
728 for i, c in enumerate(clips):
729 if c._equi(self, eps):
730 return i
731 raise ValueError(NN) # like clips.index(self)
733 def _insert(self, y, x, start, *end_alpha):
734 # insertVertex between points C{start} and
735 # C{end}, ordered by C{alpha} iff given.
736 v = self._LL(y, x, start._height, start._clipid)
737 n = start._next
738 if end_alpha:
739 end, alpha = end_alpha
740 v._alpha = alpha
741 v._height = favg(v._height, end._height, f=alpha)
742 # assert start is not end
743 while n is not end and n._alpha < alpha:
744 n = n._next
745 v._next = n
746 v._prev = p = n._prev
747 p._next = n._prev = v
748 self._len += 1
749# _Clip._bltr4._update(self)
750# _Clip._ishole._update(self)
751 return v
753 def _intersection(self, unused, q, *p1_p2_alpha):
754 # insert an intersection or make a point both
755 if p1_p2_alpha: # intersection on edge
756 v = self._insert(q.y, q.x, *p1_p2_alpha)
757 else: # intersection at point
758 v = q
759 # assert not v._linked
760 # assert v._alpha is None
761 return v
763 def _intersections(self):
764 # Yield all intersections, some may be points too.
765 for v in self:
766 if v.isintersection:
767 yield v
769 @Property_RO
770 def _ishole(self): # PYCHOK no cover
771 # Is this clip a hole inside its composite?
772 v = self._first
773 return v._isinside(self._composite, self) if v else False
775 @property_RO
776 def _nodups(self):
777 # Yield all non-duplicates.
778 for v in self:
779 if not v._dupof:
780 yield v
782 def _noXings(self, Union):
783 # Are all intersections non-CROSSINGs, -BOUNCINGs?
784 Ls = _L.BOUNCINGs if Union else _L.CROSSINGs
785 return all(v._label not in Ls for v in self._intersections())
787 def _OpenClipError(self, s, e): # PYCHOK no cover
788 # Return a C{CloseError} instance
789 t = NN(s, _ELLIPSIS_(_COMMASPACE_, e))
790 return self._Error(_SPACE_(_open_, t))
792 def _point2(self, insert):
793 # getNonIntersectionPoint and -Vertex
794 if not (insert and self._noInters):
795 for p in self._points(may_be=False): # not p._isduplicated?
796 return p, None
797 for n in self._intersections():
798 p, _ = n._prev_next2
799 k = p._linked
800 if k:
801 if n._linked not in k._prev_next2:
802 # create a pseudo-point
803 k = _0_5 * (p + n)
804 if insert:
805 k = self._insert(k.y, k.x, n._prev)
806 r = k # to remove later
807 else: # no ._prev, ._next
808 k._clipid = n._clipid
809 r = None
810 return k, r
811 return None, None
813 def _points(self, may_be=True):
814 # Yield all points I{in original order}, which may be intersections too.
815 for v in self:
816 if v.ispoint and (may_be or not v.isintersection):
817 yield v
819 def _remove2(self, v):
820 # Remove vertex C{v}.
821 # assert not v._isduplicated
822 if len(self) > 1:
823 p = v._prev
824 p._next = n = v._next
825 n._prev = p
826 if self._first is v:
827 self._first = n
828 if self._last is v:
829 self._last = p
830 self._len -= 1
831 else:
832 n = self._last = \
833 p = self._first = None
834 self._len = 0
835 return p, n
837 def _update_all(self): # PYCHOK no cover
838 # Zap the I{cached} properties.
839 _Clip._bltr4._update( self)
840 _Clip._ishole._update(self)
841 return self # for _special_identicals
843 def _Xings(self):
844 # Yield all I{un-checked} CROSSING intersections.
845 CROSSING = _L.CROSSING
846 for v in self._intersections():
847 if v._label is CROSSING and not v._checked:
848 yield v
851class _CompositeBase(_Named):
852 '''(INTERNAL) Base class for L{BooleanFHP} and L{BooleanGH}
853 (C{_CompositeFHP} and C{_CompositeGH}).
854 '''
855 _clips = () # tuple of C{_Clips}
856 _eps = EPS # null edges
857 _kind = _corners_
858 _LL = _LatLonBool # shut up PyChecker
859 _raiser = False
860 _xtend = False
862 def __init__(self, lls, name=NN, kind=NN, eps=EPS):
863 '''(INTERNAL) See L{BooleanFHP} and L{BooleanGH}.
864 '''
865 n = name or getattr(lls, _name_, NN)
866 if n:
867 self.name = n
868 if kind:
869 self._kind = kind
870 if self._eps < eps:
871 self._eps = eps
873 c = _Clip(self)
874 lp = None
875 for ll in lls:
876 ll = self._LL(ll)
877 if lp is None:
878 c._id = ll._clipid # keep clipid
879 lp = c._append(ll)
880 elif ll._clipid != lp._clipid: # new clip
881 c._closed(self.raiser)
882 c = _Clip(self, ll._clipid)
883 lp = c._append(ll)
884 elif abs(ll - lp) > eps: # PYCHOK lp
885 lp = c._append(ll)
886 else:
887 c._dups += 1
888 c._closed(self.raiser)
890 def __contains__(self, point): # PYCHOK no cover
891 '''Is the B{C{point}} in one of the clips?
892 '''
893 for c in self._clips:
894 if point in c:
895 return True
896 return False
898 def __eq__(self, other):
899 '''Is this I{composite} equivalent to an B{C{other}}, i.e.
900 do both contain I{equivalent} clips in the same or in a
901 different order? Two clips are considered I{equivalent}
902 if both have the same points etc. in the same order,
903 possibly rotated.
904 '''
905 return self._equi(_other(self, other), 0)
907 def __iter__(self):
908 '''Yield all points, duplicates and intersections.
909 '''
910 for c in self._clips:
911 for v in c:
912 yield v
914 def __ne__(self, other): # required for Python 2
915 '''See method C{__eq__}.
916 '''
917 return not self.__eq__(other)
919 def __len__(self):
920 '''Return the I{total} number of points.
921 '''
922 return sum(map(len, self._clips)) if self._clips else 0
924 def __repr__(self):
925 '''String C{repr} of this composite.
926 '''
927 c = len(self._clips)
928 c = Fmt.SQUARE(c) if c > 1 else NN
929 n = Fmt.SQUARE(len(self))
930 t = Fmt.PAREN(self) # XXX not unstr
931 return NN(self.__class__.__name__, c, n, t)
933 def __str__(self):
934 '''String C{str} of this composite.
935 '''
936 return _COMMASPACE_.join(map(str, self))
938 @property_RO
939 def _bottom_top_eps2(self):
940 # Get the bottom and top C{y} bounds, oversized.
941 return _min_max_eps2(min(v.y for v in self),
942 max(v.y for v in self))
944 def _class(self, corners, kwds, **dflts):
945 # Return a new instance
946 _g = kwds.get
947 kwds = dict((n, _g(n, v)) for n, v in dflts.items())
948 return self.__class__(corners or (), **kwds)
950 @property_RO
951 def _clipids(self): # PYCHOK no cover
952 for c in self._clips:
953 yield c._id
955 def clipids(self):
956 '''Return a tuple with all C{clipid}s, I{ordered}.
957 '''
958 return tuple(self._clipids)
960# def _clipidups(self, other):
961# # Number common C{clipid}s between this and an C{other} composite
962# return len(set(self._clipids).intersection(set(other._clipids)))
964 def _edges3(self, **raiser):
965 # Yield each I{original} edge as a 3-tuple
966 # C{(LatLon[FHP|GH], LatLon[FHP|GH], _Clip)}.
967 for c in self._clips:
968 for p1, p2 in c._edges2(**raiser):
969 yield p1, p2, c
971 def _encloses(self, lat, lon):
972 # see function .points.isenclosedBy
973 return self._LL(lat, lon).isenclosedBy(self)
975 @property
976 def eps(self):
977 '''Get the null edges tolerance (C{degrees}, usually).
978 '''
979 return self._eps
981 @eps.setter # PYCHOK setter!
982 def eps(self, eps):
983 '''Set the null edges tolerance (C{degrees}, usually).
984 '''
985 self._eps = eps
987 def _10eps(self, **eps):
988 # Get eps for _LatLonBool._2Abs
989 e = _xkwds_get(eps, eps=self._eps)
990 if e != EPS:
991 e *= _10EPS / EPS
992 else:
993 e = _10EPS
994 return e
996 def _equi(self, other, eps):
997 # Is this composite I{equivalent} to an B{C{other}} within
998 # the given, I{non-negative} tolerance B{C{eps}}?
999 cs, co = self._clips, other._clips
1000 if cs and len(cs) == len(co):
1001 if eps > 0:
1002 _index = _Clip._index
1003 else:
1004 def _index(c, cs, unused):
1005 return cs.index(c)
1006 try:
1007 cs = list(sorted(cs))
1008 for c in sorted(co):
1009 cs.pop(_index(c, cs, eps))
1010 except ValueError: # from ._index
1011 pass
1012 return False if cs else True
1013 else: # both null?
1014 return False if cs or co else True
1016 def _intersections(self):
1017 # Yield all intersections.
1018 for c in self._clips:
1019 for v in c._intersections():
1020 yield v
1022 def isequalTo(self, other, eps=None):
1023 '''Is this boolean/composite equal to an B{C{other}} within
1024 a given, I{non-negative} tolerance?
1026 @arg other: The other boolean/composite (C{Boolean[FHP|GB]}).
1027 @kwarg eps: Tolerance for equality (C{degrees} or C{None}).
1029 @return: C{True} if equivalent, C{False} otherwise (C{bool}).
1031 @raise TypeError: Invalid B{C{other}}.
1033 @see: Method C{__eq__}.
1034 '''
1035 if isinstance(other, _CompositeBase):
1036 return self._equi(other, _eps0(eps))
1037 raise _IsnotError(_boolean_, _composite_, other=other)
1039 def _kwds(self, op, **more):
1040 # Get all keyword arguments as C{dict}.
1041 kwds = dict(raiser=self.raiser, eps=self.eps,
1042 name=self.name or op.__name__)
1043 kwds.update(more)
1044 return kwds
1046 @property_RO
1047 def _left_right_eps2(self):
1048 # Get the left and right C{x} bounds, oversized.
1049 return _min_max_eps2(min(v.x for v in self),
1050 max(v.x for v in self))
1052 def _points(self, may_be=True): # PYCHOK no cover
1053 # Yield all I{original} points, which may be intersections too.
1054 for c in self._clips:
1055 for v in c._points(may_be=may_be):
1056 yield v
1058 @property
1059 def raiser(self):
1060 '''Get the option to throw L{ClipError} exceptions (C{bool}).
1061 '''
1062 return self._raiser
1064 @raiser.setter # PYCHOK setter!
1065 def raiser(self, throw):
1066 '''Set the option to throw L{ClipError} exceptions (C{bool}).
1067 '''
1068 self._raiser = bool(throw)
1070 def _results(self, _presults, Clas, closed=False, inull=False, **eps):
1071 # Yield the dedup'd results, as L{ClipFHP4Tuple}s
1072 C = self._LL if Clas is None else Clas
1073 e = self._10eps(**eps)
1074 for clipid, ns in enumerate(_presults):
1075 f = p = v = None
1076 for n in ns:
1077 if f is None:
1078 yield n._toClas(C, clipid)
1079 f = p = n
1080 elif v is None:
1081 v = n # got f, p, v
1082 elif inull or p._2Abs(v, n, eps=e):
1083 yield v._toClas(C, clipid)
1084 p, v = v, n
1085 else: # null, colinear, ... skipped
1086 v = n
1087 if v and (inull or p._2Abs(v, f, eps=e)):
1088 yield v._toClas(C, clipid)
1089 p = v
1090 if f and p != f and closed: # close clip
1091 yield f._toClas(C, clipid)
1093 def _sum(self, other, op):
1094 # Combine this and an C{other} composite
1095 LL = self._LL
1096 sp = self.copy(name=self.name or op.__name__)
1097 sp._clips, sid = (), INT0 # new clips
1098 for cp in (self, other):
1099 for c in cp._clips:
1100 _ap = _Clip(sp, sid)._append
1101 for v in c._nodups:
1102 _ap(LL(v.y, v.x, v.height, sid))
1103 sid += 1
1104 return sp
1106 def _sum1(self, _a_p, *args, **kwds): # in .karney, .points
1107 # Sum the area or perimeter of all clips
1108 return _MODS.fsums.fsum1((_a_p(c, *args, **kwds) for c in self._clips),
1109 floats=True)
1111 def _sum2(self, LL, _a_p, *args, **kwds): # in .sphericalNvector, -Trigonometry
1112 # Sum the area or perimeter of all clips
1114 def _lls(clip): # convert clip to LLs
1115 for v in clip:
1116 yield LL(v.lat, v.lon) # datum=Sphere
1118 return _MODS.fsums.fsum1((_a_p(_lls(c), *args, **kwds) for c in self._clips),
1119 floats=True)
1121 def toLatLon(self, LatLon=None, closed=False, **LatLon_kwds):
1122 '''Yield all (non-duplicate) points and intersections
1123 as an instance of B{C{LatLon}}.
1125 @kwarg LatLon: Class to use (C{LatLon}) or if C{None},
1126 L{LatLonFHP} or L{LatLonGH}.
1127 @kwarg closed: If C{True}, close each clip (C{bool}).
1128 @kwarg LatLon_kwds: Optional, additional B{C{LatLon}}
1129 keyword arguments, ignore if
1130 C{B{LatLon} is None}.
1132 @raise TypeError: Invalid B{C{LatLon}}.
1134 @note: For intersections, C{height} is an instance
1135 of L{HeightX}, otherwise of L{Height}.
1136 '''
1137 if LatLon is None:
1138 LL, kwds = self._LL, {}
1139 elif issubclassof(LatLon, _LatLonBool,
1140 _MODS.latlonBase.LatLonBase):
1141 LL, kwds = LatLon, LatLon_kwds
1142 else:
1143 raise _TypeError(LatLon=LatLon)
1145 for c in self._clips:
1146 lf, cid = None, c._id
1147 for v in c._nodups:
1148 ll = LL(v.y, v.x, **kwds)
1149 ll._height = v.height
1150 if ll._clipid != cid:
1151 ll._clipid = cid
1152 yield ll
1153 if lf is None:
1154 lf = ll
1155 if closed and lf:
1156 yield lf
1159class _CompositeFHP(_CompositeBase):
1160 '''(INTERNAL) A list of clips representing a I{composite}
1161 of L{LatLonFHP} points, duplicates and intersections
1162 with an other I{composite}.
1163 '''
1164 _LL = LatLonFHP
1165 _Union = False
1167 def __init__(self, lls, raiser=False, **name_kind_eps):
1168 # New L{_CompositeFHP}.
1169 if raiser:
1170 self._raiser = True
1171 _CompositeBase.__init__(self, lls, **name_kind_eps)
1173 def _classify(self):
1174 # 2) Classify intersection chains.
1175 L = _L
1176 for v in self._intersections():
1177 n, b = v, v._label
1178 if b in L.RIGHT_LEFT_ON: # next chain
1179 while True:
1180 n._label = None # n.__dict__.pop('_label')
1181 n = n._next
1182 if n is v or n._label is not L.ON_ON: # n._label and ...
1183 break
1184 a = L.LEFT_ON if n._label is L.ON_LEFT else L.RIGHT_ON
1185 v._label = n._label = L.BOUNCING_D if a is b else L.CROSSING_D
1187 # 3) Copy labels
1188 for v in self._intersections():
1189 v._linked._label = v._label
1191 def _clip(self, corners, Union=False, Clas=None,
1192 **closed_inull_raiser_eps):
1193 # Clip this composite with another one, C{corners},
1194 # using Foster-Hormann-Popa's algorithm.
1195 P = self
1196 Q = self._class(corners, closed_inull_raiser_eps,
1197 eps=P._eps, raiser=False)
1198 if Union:
1199 P._Union = Q._Union = True
1201 bt = Q._bottom_top_eps2
1202 lr = Q._left_right_eps2
1203 # compute and insert intersections
1204 for p1, p2, Pc in P._edges3(**closed_inull_raiser_eps):
1205 if not (_outside(p1.x, p2.x, *lr) or
1206 _outside(p1.y, p2.y, *bt)):
1207 e = _EdgeFHP(p1, p2)
1208 if e._dp2 > EPS2: # non-null edge
1209 for q1, q2, Qc in Q._edges3(**closed_inull_raiser_eps):
1210 for T, p, q in e._intersect3(q1, q2):
1211 p = Pc._intersection(T, *p)
1212 q = Qc._intersection(T, *q)
1213 # assert not p._linked
1214 # assert not q._linked
1215 p._link(q)
1217 # label and classify intersections
1218 P._labelize()
1219 P._classify()
1221 # check for special cases
1222 P._special_cases(Q)
1223 Q._special_cases(P)
1224 # handle identicals
1225 P._special_identicals(Q)
1227 # set Entry/Exit flags
1228 P._set_entry_exits(Q)
1229 Q._set_entry_exits(P)
1231 # handle splits and crossings
1232 P._splits_xings(Q)
1234 # yield the results
1235 return P._results(P._presults(Q), Clas, **closed_inull_raiser_eps)
1237 @property_RO
1238 def _identicals(self):
1239 # Yield all clips marked C{._identical}.
1240 for c in self._clips:
1241 if c._identical:
1242 yield c
1244 def _labelize(self):
1245 # 1) Intersections classification
1246 for p in self._intersections():
1247 q = p._linked
1248 # determine local configuration at this intersection
1249 # and positions of Q- and Q+ relative to (P-, I, P+)
1250 p1, p3 = p._prev_next2
1251 q1, q3 = q._prev_next2
1252 t = (q1._RPoracle(p1, p, p3),
1253 q3._RPoracle(p1, p, p3))
1254 # check intersecting and overlapping cases
1255 p._label = _RP2L.get(t, None)
1257 def _presults(self, other):
1258 # Yield the result clips, each as a generator
1259 # of the L{_LatLonFHP}s in that clip
1260 for cp in (self, other):
1261 for c in cp._clips:
1262 if c._pushback:
1263 yield c._all()
1264 for c in self._clips:
1265 for X in c._Xings():
1266 yield self._resultX(X)
1268 def _resultX(self, X):
1269 # Yield the results from CROSSING C{X}.
1270 L, U, v = _L, self._Union, X
1271 while v:
1272 v._checked = True
1273 r = v # in P or Q
1274 s = L.Toggle[v._en_ex]
1275 e = (s is L.EXIT) ^ U
1276 while True:
1277 v = v._next if e else v._prev
1278 yield v
1279 v._checked = True
1280 if v._en_ex is s or v is X:
1281 break
1282 if v is r: # full circle
1283 raise ClipError(full_circle=v, clipid=v._clipid)
1284 if v is not X:
1285 v = v._linked
1286 if v is X:
1287 break
1289 def _set_entry_exits(self, other): # MCCABE 14
1290 # 4) Set entry/exit flags
1291 L, U = _L, self._Union
1292 for c in self._clips:
1293 n, k = c._point2(True)
1294 if n:
1295 f = n
1296 s = L.EXIT if n._isinside(other) else L.ENTRY
1297 t = L.EXIT # first_chain_vertex = True
1298 while True:
1299 if n.isintersection:
1300 b = n._label
1301 if b is L.CROSSING:
1302 n._en_ex = s
1303 s = L.Toggle[s]
1304 elif b is L.BOUNCING and ((s is L.EXIT) ^ U):
1305 n._2split = c # see ._splits_xings
1306 elif b is L.CROSSING_D:
1307 n._en_ex = s
1308 if (s is t) ^ U:
1309 n._label = L.CROSSING
1310 t = L.Toggle[t]
1311 if t is L.EXIT: # first_chain_vertex == True
1312 s = L.Toggle[s]
1313 elif b is L.BOUNCING_D:
1314 n._en_ex = s
1315 if (s is t) ^ U:
1316 n._2xing = True # see ._splits_xings
1317 s = L.Toggle[s]
1318 t = L.Toggle[t]
1319 n = n._next # _, n = n._prev_next2
1320 if n is f:
1321 break # PYCHOK attr?
1322 if k:
1323 c._remove2(k)
1325 def _special_cases(self, other):
1326 # 3.5) Check special cases
1327 U = self._Union
1328 for c in self._clips:
1329 if c._noXings(U):
1330 c._noInters = True
1331 if c._all_ON_ON:
1332 c._identical = True
1333 else:
1334 p, _ = c._point2(False)
1335 if p and (p._isinside(other) ^ U):
1336 c._pushback = True
1338 def _special_identicals(self, other):
1339 # 3.5) Handle identicals
1340 _u = _Clip._update_all
1341 cds = dict((c._id, _u(c)) for c in other._identicals)
1342 # assert len(cds) == len(other._identicals)
1343 if cds: # PYCHOK no cover
1344 for c in self._identicals:
1345 c._update_all()
1346 for v in c._intersections():
1347 d = cds.get(v._linked._clipid, None)
1348 if d and d._ishole is c._ishole:
1349 c._pushback = True
1350 break # next c
1352 @property_RO
1353 def _2splits(self):
1354 # Yield all intersections marked C{._2split}
1355 for p in self._intersections():
1356 if p._2split:
1357 # assert isinstance(p._2split, _Clip)
1358 yield p
1360 def _splits_xings(self, other): # MCCABE 15
1361 # 5) Handle split pairs and 6) crossing candidates
1363 def _2A_dup2(p, P): # PYCHOK unused
1364 p1, p2 = p._prev_next2
1365 ap = p1._2A(p, p2)
1366 Pc = p._2split
1367 # assert Pc in P._clips
1368 # assert p in Pc
1369 return ap, Pc._dup(p)
1371 def _links2(ps, qs): # PYCHOK P unused?
1372 # Yield each link as a 2-tuple(p, q)
1373 id_qs = set(map(id, qs))
1374 if id_qs:
1375 for p in ps:
1376 q = p._linked
1377 if q and id(q) in id_qs:
1378 yield p, q
1380 L = _L
1381 E = L.ENTRY if self._Union else L.EXIT
1382 X = L.Toggle[E]
1383 for p, q in _links2(self._2splits, other._2splits):
1384 ap, pp = _2A_dup2(p, self)
1385 aq, qq = _2A_dup2(q, other)
1386 if (ap * aq) > 0: # PYCHOK no cover
1387 p._link(qq) # overwrites ...
1388 q._link(pp) # ... p-q link
1389 else:
1390 pp._link(qq)
1391 p._en_ex = q._en_ex = E
1392 pp._en_ex = qq._en_ex = X
1393 p._label = pp._label = \
1394 q._label = qq._label = L.CROSSING
1396 for p, q in _links2(self._2xings, other._2xings):
1397 p._label = q._label = L.CROSSING
1399 @property_RO
1400 def _2xings(self):
1401 # Yield all intersections marked C{._2xing}
1402 for p in self._intersections():
1403 if p._2xing:
1404 yield p
1407class _CompositeGH(_CompositeBase):
1408 '''(INTERNAL) A list of clips representing a I{composite}
1409 of L{LatLonGH} points, duplicates and intersections
1410 with an other I{composite}.
1411 '''
1412 _LL = LatLonGH
1413 _xtend = False
1415 def __init__(self, lls, raiser=False, xtend=False, **name_kind_eps):
1416 # New L{_CompositeGH}.
1417 if xtend:
1418 self._xtend = True
1419 elif raiser:
1420 self._raiser = True
1421 _CompositeBase.__init__(self, lls, **name_kind_eps)
1423 def _clip(self, corners, s_entry, c_entry, Clas=None,
1424 **closed_inull_raiser_xtend_eps):
1425 # Clip this polygon with another one, C{corners}.
1427 # Core of Greiner/Hormann's algorithm, enhanced U{Correia's
1428 # <https://GitHub.com/helderco/univ-polyclip>} implementation***
1429 # and extended to optionally handle so-called "degenerate cases"
1430 S = self
1431 C = self._class(corners, closed_inull_raiser_xtend_eps,
1432 raiser=False, xtend=False)
1433 bt = C._bottom_top_eps2
1434 lr = C._left_right_eps2
1435 # 1. find intersections
1436 for s1, s2, Sc in S._edges3(**closed_inull_raiser_xtend_eps):
1437 if not (_outside(s1.x, s2.x, *lr) or
1438 _outside(s1.y, s2.y, *bt)):
1439 e = _EdgeGH(s1, s2, **closed_inull_raiser_xtend_eps)
1440 if e._hypot2 > EPS2: # non-null edge
1441 for c1, c2, Cc in C._edges3(**closed_inull_raiser_xtend_eps):
1442 for y, x, sa, ca in e._intersect4(c1, c2):
1443 s = Sc._insert(y, x, s1, s2, sa)
1444 c = Cc._insert(y, x, c1, c2, ca)
1445 s._link(c)
1447 # 2. identify entry/exit intersections
1448 if S._first:
1449 s_entry ^= S._first._isinside(C, *bt)
1450 for v in S._intersections():
1451 v._entry = s_entry = not s_entry
1453 if C._first:
1454 c_entry ^= C._first._isinside(S)
1455 for v in C._intersections():
1456 v._entry = c_entry = not c_entry
1458 # 3. yield the result(s)
1459 return S._results(S._presults(), Clas, **closed_inull_raiser_xtend_eps)
1461 @property_RO
1462 def _first(self):
1463 # Get the very first vertex of the first clip
1464 for v in self:
1465 return v
1466 return None # PYCHOK no cover
1468 def _kwds(self, op, **more):
1469 # Get the kwds C{dict}.
1470 return _CompositeBase._kwds(self, op, xtend=self.xtend, **more)
1472 def _presults(self):
1473 # Yield the unchecked intersection(s).
1474 for c in self._clips:
1475 for v in c._intersections():
1476 if not v._checked:
1477 yield self._resultU(v)
1479 def _resultU(self, v):
1480 # Yield the result from an un-checked intersection.
1481 while v and not v._checked:
1482 v._check()
1483 yield v
1484 r = v
1485 e = v._entry
1486 while True:
1487 v = v._next if e else v._prev
1488 yield v
1489 if v._linked:
1490 break
1491 if v is r:
1492 raise ClipError(full_circle=v, clipid=v._clipid)
1493 v = v._linked # switch
1495 @property
1496 def xtend(self):
1497 '''Get the option to handle I{degenerate cases} (C{bool}).
1498 '''
1499 return self._xtend
1501 @xtend.setter # PYCHOK setter!
1502 def xtend(self, xtend):
1503 '''Set the option to handle I{degenerate cases} (C{bool}).
1504 '''
1505 self._xtend = bool(xtend)
1508class _EdgeFHP(object):
1509 # An edge between two L{LatLonFHP} points.
1511 X_INTERSECT = _Enum('Xi', 1) # C++ enum
1512 X_OVERLAP = _Enum('Xo', 5)
1513 P_INTERSECT = _Enum('Pi', 3)
1514 P_OVERLAP = _Enum('Po', 7)
1515 Ps = (P_INTERSECT, P_OVERLAP, X_OVERLAP)
1516 Q_INTERSECT = _Enum('Qi', 2)
1517 Q_OVERLAP = _Enum('Qo', 6)
1518 Qs = (Q_INTERSECT, Q_OVERLAP, X_OVERLAP)
1519 V_INTERSECT = _Enum('Vi', 4)
1520 V_OVERLAP = _Enum('Vo', 8)
1521 Vs = (V_INTERSECT, V_OVERLAP)
1523 def __init__(self, p1, p2, **unused):
1524 # New edge between points C{p1} and C{p2}, each a L{LatLonFHP}.
1525 self._p1_p2 = p1, p2
1526 self._dp = dp = p2 - p1
1527 self._dp2 = dp * dp # dot product, hypot2
1529 self._lr, \
1530 self._bt = _left_right_bottom_top_eps2(p1, p2)
1532 def _intersect3(self, q1, q2):
1533 # Return intersection Type or C{None}
1534 if not (_outside(q1.x, q2.x, *self._lr) or
1535 _outside(q1.y, q2.y, *self._bt)):
1536 dq = q2 - q1
1537 dq2 = dq * dq # dot product, hypot2
1538 if dq2 > EPS2: # like ._clip
1539 T, E = None, _EdgeFHP # self.__class__
1540 p1, p2 = self._p1_p2
1541 ap1 = p1._2A(q1, q2)
1542 ap2_1 = p2._2A(q1, q2) - ap1
1543 if fabs(ap2_1) > _0_EPS: # non-parallel edges
1544 aq1 = q1._2A(p1, p2)
1545 aq2_1 = q2._2A(p1, p2) - aq1
1546 if fabs(aq2_1) > _0_EPS:
1547 # compute and classify alpha and beta
1548 a, a_0, a_0_1, _ = _alpha4(-ap1 / ap2_1)
1549 b, b_0, b_0_1, _ = _alpha4(-aq1 / aq2_1)
1550 # distinguish intersection types
1551 T = E.X_INTERSECT if a_0_1 and b_0_1 else (
1552 E.P_INTERSECT if a_0_1 and b_0 else (
1553 E.Q_INTERSECT if a_0 and b_0_1 else (
1554 E.V_INTERSECT if a_0 and b_0 else None)))
1556 elif fabs(ap1) < _0_EPS: # parallel or colinear edges
1557 dp = self._dp
1558 d1 = q1 - p1
1559 # compute and classify alpha and beta
1560 a, a_0, a_0_1, _a_0_1 = _alpha4((d1 * dp) / self._dp2)
1561 b, b_0, b_0_1, _b_0_1 = _alpha4((d1 * dq) / (-dq2))
1562 # distinguish overlap type
1563 T = E.X_OVERLAP if a_0_1 and b_0_1 else (
1564 E.P_OVERLAP if a_0_1 and _b_0_1 else (
1565 E.Q_OVERLAP if _a_0_1 and b_0_1 else (
1566 E.V_OVERLAP if a_0 and b_0 else None)))
1568 if T:
1569 if T is E.X_INTERSECT:
1570 v = p1 + a * self._dp
1571 yield T, (v, p1, p2, a), (v, q1, q2, b)
1572 elif T in E.Vs:
1573 yield T, (p1,), (q1,)
1574 else:
1575 if T in E.Qs:
1576 yield T, (p1,), (p1, q1, q2, b)
1577 if T in E.Ps:
1578 yield T, (q1, p1, p2, a), (q1,)
1581class _EdgeGH(object):
1582 # An edge between two L{LatLonGH} points.
1584 _raiser = False
1585 _xtend = False
1587 def __init__(self, s1, s2, raiser=False, xtend=False, **unused):
1588 # New edge between points C{s1} and C{s2}, each a L{LatLonGH}.
1589 self._s1, self._s2 = s1, s2
1590 self._x_sx_y_sy = (s1.x, s2.x - s1.x,
1591 s1.y, s2.y - s1.y)
1592 self._lr, \
1593 self._bt = _left_right_bottom_top_eps2(s1, s2)
1595 if xtend:
1596 self._xtend = True
1597 elif raiser:
1598 self._raiser = True
1600 def _alpha2(self, x, y, dx, dy):
1601 # Return C{(alpha)}, see .points.nearestOn5
1602 a = (y * dy + x * dx) / self._hypot2
1603 d = (y * dx - x * dy) / self._hypot0
1604 return a, fabs(d)
1606 def _Error(self, n, *args, **kwds): # PYCHOK no cover
1607 t = unstr(_EdgeGH.__name__, self._s1, self._s2)
1608 t = _DOT_(t, _EdgeGH._intersect4.__name__)
1609 t = unstr(t, *args, **kwds)
1610 return ClipError(_case_, n, txt=t)
1612 @Property_RO
1613 def _hypot0(self):
1614 _, sx, _, sy = self._x_sx_y_sy
1615 return hypot(sx, sy) * _0_EPS
1617 @Property_RO
1618 def _hypot2(self):
1619 _, sx, _, sy = self._x_sx_y_sy
1620 return hypot2(sx, sy)
1622 def _intersect4(self, c1, c2, parallel=True): # MCCABE 14
1623 # Yield the intersections of this and another edge.
1625 # @return: None, 1 or 2 intersections, each a 4-Tuple
1626 # (y, x, s_alpha, c_alpha) with intersection
1627 # coordinates x and y and both alphas.
1629 # @raise ClipError: Intersection unhandled.
1631 # @see: U{Intersection point of two line segments
1632 # <http://PaulBourke.net/geometry/pointlineplane/>}.
1633 c1_x, c1_y = c1.x, c1.y
1634 if not (_outside(c1_x, c2.x, *self._lr) or
1635 _outside(c1_y, c2.y, *self._bt)):
1636 x, sx, \
1637 y, sy = self._x_sx_y_sy
1639 cx = c2.x - c1_x
1640 cy = c2.y - c1_y
1641 d = cy * sx - cx * sy
1643 if fabs(d) > _0_EPS: # non-parallel edges
1644 dx = x - c1_x
1645 dy = y - c1_y
1646 ca = (sx * dy - sy * dx) / d
1647 if _0_EPS < ca < _EPS_1 or (self._xtend and
1648 _EPS_0 < ca < _1_EPS):
1649 sa = (cx * dy - cy * dx) / d
1650 if _0_EPS < sa < _EPS_1 or (self._xtend and
1651 _EPS_0 < sa < _1_EPS):
1652 yield (y + sa * sy), (x + sa * sx), sa, ca
1654 # unhandled, "degenerate" cases 1, 2 or 3
1655 elif self._raiser and not (sa < _EPS_0 or sa > _1_EPS): # PYCHOK no cover
1656 raise self._Error(1, c1, c2, sa=sa) # intersection at s1 or s2
1658 elif self._raiser and not (ca < _EPS_0 or ca > _1_EPS): # PYCHOK no cover
1659 # intersection at c1 or c2 or at c1 or c2 and s1 or s2
1660 sa = (cx * dy - cy * dx) / d
1661 e = 2 if sa < _EPS_0 or sa > _1_EPS else 3
1662 raise self._Error(e, c1, c2, ca=ca)
1664 elif parallel and (sx or sy) and (cx or cy): # PYCHOK no cover
1665 # non-null, parallel or colinear edges
1666 sa1, d1 = self._alpha2(c1_x - x, c1_y - y, sx, sy)
1667 sa2, d2 = self._alpha2(c2.x - x, c2.y - y, sx, sy)
1668 if max(d1, d2) < _0_EPS:
1669 if self._xtend and not _outside(sa1, sa2, _EPS_0, _1_EPS):
1670 if sa1 > sa2: # anti-parallel
1671 sa1, sa2 = sa2, sa1
1672 ca1, ca2 = _1_0, _0_0
1673 else: # parallel
1674 ca1, ca2 = _0_0, _1_0
1675 ca = fabs((sx / cx) if cx else (sy / cy))
1676 # = hypot(sx, sy) / hypot(cx, cy)
1677 if sa1 < 0: # s1 is between c1 and c2
1678 ca *= ca1 + sa1
1679 yield y, x, ca1, _alpha1(ca)
1680 else: # c1 is between s1 and s2
1681 yield (y + sa1 * sy), (x + sa1 * sx), sa1, ca1
1682 if sa2 > 1: # s2 is between c1 and c2
1683 ca *= sa2 - _1_0
1684 yield (y + sy), (x + sx), ca2, _alpha1(ca2 - ca)
1685 else: # c2 is between s1 and s2
1686 yield (y + sa2 * sy), (x + sa2 * sx), sa2, ca2
1687 elif self._raiser and not _outside(sa1, sa2, _0_0, _1_EPS):
1688 raise self._Error(4, c1, c2, d1=d1, d2=d2)
1691class _BooleanBase(object):
1692 # Shared C{Boolean[FHP|GH]} methods.
1694 def __add__(self, other):
1695 '''Sum: C{this + other} clips.
1696 '''
1697 return self._sum(_other(self, other), self.__add__) # PYCHOK OK
1699 def __and__(self, other):
1700 '''Intersection: C{this & other}.
1701 '''
1702 return self._boolean(other, False, False, self.__and__) # PYCHOK OK
1704 def __iadd__(self, other):
1705 '''In-place sum: C{this += other} clips.
1706 '''
1707 return self._inplace(self.__add__(other))
1709 def __iand__(self, other):
1710 '''In-place intersection: C{this &= other}.
1711 '''
1712 return self._inplace(self.__and__(other))
1714 def __ior__(self, other):
1715 '''In-place union: C{this |= other}.
1716 '''
1717 return self._inplace(self.__or__(other))
1719 def __or__(self, other):
1720 '''Union: C{this | other}.
1721 '''
1722 return self._boolean(other, True, True, self.__or__) # PYCHOK OK
1724 def __radd__(self, other):
1725 '''Reverse sum: C{other + this} clips.
1726 '''
1727 return _other(self, other)._sum(self, self.__radd__)
1729 def __rand__(self, other):
1730 '''Reverse intersection: C{other & this}
1731 '''
1732 return _other(self, other).__and__(self)
1734 def __ror__(self, other):
1735 '''Reverse union: C{other | this}
1736 '''
1737 return _other(self, other).__or__(self)
1739 def _boolean4(self, other, op):
1740 # Set up a new C{Boolean[FHP|GH]}.
1741 C = self.__class__
1742 kwds = C._kwds(self, op)
1743 a = C(self, **kwds)
1744 b = _other(self, other)
1745 return a, b, C, kwds
1747 def _inplace(self, r):
1748 # Replace this with a L{Boolean*} result.
1749 self._clips, r._clips = r._clips, None
1750# if self._raiser != r._raiser:
1751# self._raiser = r._raiser
1752# if self._xtend != r._xtend:
1753# self._xtend = r._xtend
1754# if self._eps != r._eps:
1755# self._eps = r._eps
1756 return self
1759class BooleanFHP(_CompositeFHP, _BooleanBase):
1760 '''I{Composite} class providing I{boolean} operations between two
1761 I{composites} using U{Forster-Hormann-Popa<https://www.ScienceDirect.com/
1762 science/article/pii/S259014861930007X>}'s C++ implementation, transcoded
1763 to pure Python.
1765 The supported operations between (composite) polygon A and B are:
1767 - C = A & B or A &= B, intersection of A and B
1769 - C = A + B or A += B, sum of A and B clips
1771 - C = A | B or A |= B, union of A and B
1773 - A == B or A != B, equivalent A and B clips
1775 - A.isequalTo(B, eps), equivalent within tolerance
1777 @see: Methods C{__eq__} and C{isequalTo}, function L{clipFHP4}
1778 and class L{BooleanGH}.
1779 '''
1780 _kind = _boolean_
1782 def __init__(self, lls, raiser=False, eps=EPS, name=NN):
1783 '''New L{BooleanFHP} operand for I{boolean} operation.
1785 @arg lls: The polygon points and clips (iterable of L{LatLonFHP}s,
1786 L{ClipFHP4Tuple}s or other C{LatLon}s).
1787 @kwarg raiser: If C{True}, throw L{ClipError} exceptions (C{bool}).
1788 @kwarg esp: Tolerance for eliminating null edges (C{degrees}, same
1789 units as the B{C{lls}} coordinates).
1790 @kwarg name: Optional name (C{str}).
1791 '''
1792 _CompositeFHP.__init__(self, lls, raiser=raiser,
1793 eps=eps, name=name)
1795 def __isub__(self, other):
1796 '''Not implemented.'''
1797 return _NotImplemented(self, other)
1799 def __rsub__(self, other):
1800 '''Not implemented.'''
1801 return _NotImplemented(self, other)
1803 def __sub__(self, other):
1804 '''Not implemented.'''
1805 return _NotImplemented(self, other)
1807 def _boolean(self, other, Union, unused, op):
1808 # One C{BooleanFHP} operation.
1809 p, q, C, kwds = self._boolean4(other, op)
1810 r = p._clip(q, Union=Union, **kwds)
1811 return C(r, **kwds)
1814class BooleanGH(_CompositeGH, _BooleanBase):
1815 '''I{Composite} class providing I{boolean} operations between two
1816 I{composites} using the U{Greiner-Hormann<http://www.Inf.USI.CH/
1817 hormann/papers/Greiner.1998.ECO.pdf>} algorithm and U{Correia
1818 <https://GitHub.com/helderco/univ-polyclip>}'s implementation,
1819 modified and extended.
1821 The supported operations between (composite) polygon A and B are:
1823 - C = A - B or A -= B, difference A less B
1825 - C = B - A or B -= A, difference B less B
1827 - C = A & B or A &= B, intersection of A and B
1829 - C = A + B or A += B, sum of A and B clips
1831 - C = A | B or A |= B, union of A and B
1833 - A == B or A != B, equivalent A and B clips
1835 - A.isequalTo(B, eps), equivalent within tolerance
1837 @note: To handle I{degenerate cases} like C{point-edge} and
1838 C{point-point} intersections, use class L{BooleanFHP}.
1840 @see: Methods C{__eq__} and C{isequalTo}, function L{clipGH4}
1841 and class L{BooleanFHP}.
1842 '''
1843 _kind = _boolean_
1845 def __init__(self, lls, raiser=True, xtend=False, eps=EPS, name=NN):
1846 '''New L{BooleanFHP} operand for I{boolean} operation.
1848 @arg lls: The polygon points and clips (iterable of L{LatLonGH}s,
1849 L{ClipGH4Tuple}s or other C{LatLon}s).
1850 @kwarg raiser: If C{True}, throw L{ClipError} exceptions (C{bool}).
1851 @kwarg xtend: If C{True}, extend edges of I{degenerate cases}, an
1852 attempt to handle the latter (C{bool}).
1853 @kwarg esp: Tolerance for eliminating null edges (C{degrees}, same
1854 units as the B{C{lls}} coordinates).
1855 @kwarg name: Optional name (C{str}).
1856 '''
1857 _CompositeGH.__init__(self, lls, raiser=raiser, xtend=xtend,
1858 eps=eps, name=name)
1860 def _boolean(self, other, s_entry, c_entry, op):
1861 # One C{BooleanGH} operation.
1862 s, c, C, kwds = self._boolean4(other, op)
1863 r = s._clip(c, s_entry, c_entry, **kwds)
1864 return C(r, **kwds)
1866 def __isub__(self, other):
1867 '''In-place difference: C{this -= other}.
1868 '''
1869 return self._inplace(self.__sub__(other))
1871 def __rsub__(self, other):
1872 ''' Reverse difference: C{other - this}
1873 '''
1874 return _other(self, other).__sub__(self)
1876 def __sub__(self, other):
1877 '''Difference: C{this - other}.
1878 '''
1879 return self._boolean(other, True, False, self.__sub__)
1882def _alpha1(alpha):
1883 # Return C{alpha} in C{[0..1]} range
1884 if _EPS_0 < alpha < _1_EPS:
1885 return max(_0_0, min(alpha, _1_0))
1886 t = _not_(Fmt.SQUARE(_ELLIPSIS_(0, 1)))
1887 raise ClipError(_alpha_, alpha, txt=t)
1890def _alpha4(a):
1891 # Return 4-tuple (alpha, -EPS < alpha < EPS,
1892 # 0 < alpha < 1,
1893 # not 0 < alpha < 1)
1894 return (a, False, True, False) if _0_EPS < a < _EPS_1 else (
1895 (a, False, False, True) if _0_EPS < fabs(a) else
1896 (a, True, False, False))
1899def _Cps(Cp, composites_points, where):
1900 # Yield composites and points as a C{Cp} composite.
1901 try:
1902 kwds = dict(kind=_points_, name=where.__name__)
1903 for cp in composites_points:
1904 yield cp if isBoolean(cp) else Cp(cp, **kwds)
1905 except (AttributeError, ClipError, TypeError, ValueError) as x:
1906 raise _ValueError(points=cp, cause=x)
1909def _eps0(eps):
1910 # Adjust C{eps} or C{None}.
1911 return eps if eps and eps > EPS else 0
1914def isBoolean(obj):
1915 '''Check for C{Boolean} composites.
1917 @arg obj: The object (any C{type}).
1919 @return: C{True} if B{C{obj}} is L{BooleanFHP},
1920 L{BooleanGH} oe some other composite,
1921 C{False} otherwise.
1922 '''
1923 return isinstance(obj, _CompositeBase)
1926def _left_right_bottom_top_eps2(p1, p2):
1927 '''(INTERNAL) Return 2-tuple C{(left, right), (bottom, top)}, oversized.
1928 '''
1929 return (_min_max_eps2(p1.x, p2.x),
1930 _min_max_eps2(p1.y, p2.y))
1933def _low_high_eps2(lo, hi, eps):
1934 '''(INTERNAL) Return 2-tuple C{(lo, hi)}, oversized.
1935 '''
1936 lo *= (_1_0 + eps) if lo < 0 else (_1_0 - eps)
1937 hi *= (_1_0 - eps) if hi < 0 else (_1_0 + eps)
1938 return (lo or -eps), (hi or eps)
1941def _min_max_eps2(*xs):
1942 '''(INTERNAL) Return 2-tuple C{(min, max)}, oversized.
1943 '''
1944 lo, hi = min(xs), max(xs)
1945 lo *= _1_EPS if lo < 0 else _EPS_1
1946 hi *= _EPS_1 if hi < 0 else _1_EPS
1947 return (lo or _EPS_0), (hi or _0_EPS)
1950def _other(this, other):
1951 '''(INTERNAL) Check for compatible C{type}s.
1952 '''
1953 C = this.__class__
1954 if isinstance(other, C):
1955 return other
1956 raise _IsnotError(C.__name__, other=other)
1959def _outside(x1, x2, lo, hi):
1960 '''(INTERNAL) Is C{(x1, x2)} outside C{(lo, hi)}?
1961 '''
1962 return max(x1, x2) < lo or min(x1, x2) > hi
1965__all__ += _ALL_DOCS(_BooleanBase, _Clip,
1966 _CompositeBase, _CompositeFHP, _CompositeGH,
1967 _LatLonBool)
1969# **) MIT License
1970#
1971# Copyright (C) 2018-2023 -- mrJean1 at Gmail -- All Rights Reserved.
1972#
1973# Permission is hereby granted, free of charge, to any person obtaining a
1974# copy of this software and associated documentation files (the "Software"),
1975# to deal in the Software without restriction, including without limitation
1976# the rights to use, copy, modify, merge, publish, distribute, sublicense,
1977# and/or sell copies of the Software, and to permit persons to whom the
1978# Software is furnished to do so, subject to the following conditions:
1979#
1980# The above copyright notice and this permission notice shall be included
1981# in all copies or substantial portions of the Software.
1982#
1983# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
1984# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1985# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
1986# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
1987# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
1988# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
1989# OTHER DEALINGS IN THE SOFTWARE.
1991# ***) GNU GPL 3
1992#
1993# Copyright (C) 2011-2012 Helder Correia <Helder.MC@Gmail.com>
1994#
1995# This program is free software: you can redistribute it and/or
1996# modify it under the terms of the GNU General Public License as
1997# published by the Free Software Foundation, either version 3 of
1998# the License, or any later version.
1999#
2000# This program is distributed in the hope that it will be useful,
2001# but WITHOUT ANY WARRANTY; without even the implied warranty of
2002# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2003# GNU General Public License for more details.
2004#
2005# You should have received a copy of the GNU General Public License
2006# along with this program. If not, see <http://www.GNU.org/licenses/>.
2007#
2008# You should have received the README file along with this program.
2009# If not, see <https://GitHub.com/helderco/univ-polyclip>.