1     
2    from typing import TypeVar,List,Sequence; 
3    from math import pi,sqrt,atan2; 
4    from enum import Enum; 
5    #------------------------------------------------------------------------------# 
6     
7    Real=TypeVar('Real',int,float); 
8    #------------------------------------------------------------------------------# 
9     
10   twicePi=2.0*pi; 
11   halfPi=0.5*pi; 
12    
13   r2d=180.0/pi; 
14   d2r=pi/180.0; 
15   #------------------------------------------------------------------------------# 
16    
17   # The constants have to be adapted to the problem 
18   maxLength=10000.0; # area extension 
19   epsilon=0.005 
20   deltaAngles=epsilon/maxLength; # radian 
21   deltaCoordinates=epsilon; 
22    
23   def areCoordinatesEqual(c1,c2:Real)->bool: 
24       return abs(c2-c1)<deltaCoordinates; 
25    
26   def areLengthsEqual(l1,l2:Real)->bool: 
27       return abs(l2-l1)<deltaCoordinates; 
28    
29   def areAnglesEqual(a1,a2:Real)->bool: 
30       return abs(a2-a1)<deltaAngles; 
31   #------------------------------------------------------------------------------# 
32    
33   class BadError(Exception): 
34       def __init__(self,data): 
35           self.Data=data; 
36    
37   class InvalidDataError(Exception): 
38       def __init__(self,data): 
39           self.Data=data; 
40    
41   class InfinityPoints(Exception): 
42       def __init__(self): pass; 
43        
44   class NoPoint(Exception): 
45       def __init__(self): pass; 
46   #------------------------------------------------------------------------------# 
47    
48   class IntersectionKind(Enum): 
49       onePoint=1; 
50       noPoint=2; 
51       infinityPoints=3; 
52   # end IntersectionKind 
53   #------------------------------------------------------------------------------# 
54    
55   class Vectors(object): 
56       def __init__(self,x:Real=0.0,y:Real=0.0)->None: 
57           self.X=x; self.Y=y; 
58    
59       def toClone(self)->'Vectors': 
60           return Vectors(self.X,self.Y); 
61    
62       def __str__(self)->str: 
63           return str(self.X)+', '+str(self.Y); 
64    
65       def __eq__(self,vc:'Vectors')->bool: 
66           """ Test for equality og two vectors  
67           """ 
68           return (areCoordinatesEqual(self.X,vc.X) and 
69                   areCoordinatesEqual(self.Y,vc.Y)); 
70    
71       def lengthOf(self)->Real: 
72           """ Returns the length of the vector 
73           """ 
74           return sqrt(self.X*self.X+self.Y*self.Y); 
75    
76       def toUnitVector(self)->'Vectors': 
77           """ Returns a unit vector in the direction of self  
78           """ 
79           lg=sqrt(self.X*self.X+self.Y*self.Y); 
80           return Vectors(self.X/lg,self.Y/lg); 
81       # end toUnitVector 
82    
83       def __add__(self,vc:'Vectors')->'Vectors': 
84           """ Addition of two vectors  
85           """ 
86           return Vectors(self.X+vc.X,self.Y+vc.Y); 
87    
88       def __sub__(self,vc:'Vectors')->'Vectors': 
89           """ Subtraction of two vectors  
90           """ 
91           return Vectors(self.X-vc.X,self.Y-vc.Y); 
92    
93       def __mul__(self,sc:Real)->'Vectors': 
94           """ Multiplication with scalar to vector  
95           """ 
96           return Vectors(self.X*sc,self.Y*sc);  
97    
98       def smul(self,sc:Real)->None: 
99           """ Multiplication with scalar to self  
100          """ 
101          self.X*=sc; self.Y*=sc;  
102   
103      def __rmul__(self,sc:Real)->'Vectors': 
104          """ Right multiplication with scalar to vector  
105          """ 
106          return Vectors(self.X*sc,self.Y*sc); 
107   
108      def __truediv__(self,sc:Real)->'Vectors': 
109          """ Division with scalar to vector  
110          """ 
111          return Vectors(self.X/sc,self.Y/sc); 
112   
113      def sdiv(self,sc:Real)->None: 
114          """ Division with scalar to self  
115          """ 
116          self.X/=sc; self.Y/=sc; 
117   
118      def dotOp(self,vc:'Vectors')->Real: 
119          """ Dot product of two vectors 
120          """ 
121          return self.X*vc.X+self.Y*vc.Y; 
122   
123      def crossOp(self,vc:'Vectors')->Real: 
124          """ Cross product of two vectors 
125          """ 
126          return self.X*vc.Y-self.Y*vc.X; 
127   
128      def dirAngleOf(self)->Real: 
129          """ Direction angle of the vector relative to the x axis 
130              0<=dirAngleOf<2*Pi 
131          """ 
132          angle=atan2(self.Y,self.X); 
133          if angle<0.0: 
134              return angle+twicePi; 
135          else: 
136              return angle; 
137      # end directionAngle 
138   
139      def sameDirectionOf(self,withV:'Vectors')->bool: 
140          """ Test for equality of the directions of two vectors 
141          """ 
142          angleDiff=abs(withV.dirAngleOf()-self.dirAngleOf()); 
143          if angleDiff<pi: 
144              return angleDiff<deltaAngles; 
145          else: 
146              return (twicePi-angleDiff)<deltaAngles; 
147      # end sameDirectionOf 
148   
149      def isOrthogonalTo(self,vc:'Vectors')->bool: 
150          return abs(self.dotOp(vc))<epsilon; 
151      # end isOrthogonalTo 
152  # end Vectors 
153  #------------------------------------------------------------------------------# 
154   
155  class Points(object): 
156      def __init__(self,x:Real=0.0,y:Real=0.0)->None: 
157          self.X=x; self.Y=y; 
158   
159      def toClone(self)->'Points': 
160          return Points(self.X,self.Y); 
161   
162      def updateOf(self,withP:'Points')->None: 
163          self.X=withP.X; 
164          self.Y=withP.Y; 
165      # end updateOf 
166   
167      def __str__(self)->str: 
168          return str(self.X)+', '+str(self.Y); 
169   
170      def __eq__(self,pt:'Points')->bool: 
171          """ Test for equality of two points 
172          """ 
173          return (areCoordinatesEqual(self.X,pt.X) and 
174                  areCoordinatesEqual(self.Y,pt.Y)); 
175   
176      def __add__(self,vc:Vectors)->'Points': 
177          """ Addition: Point with vector to point 
178          """ 
179          return Points(self.X+vc.X,self.Y+vc.Y); 
180   
181      def __sub__(self,pt:'Points')->'Vectors': 
182          """ Subtraction: Point with point to vector 
183          """ 
184          return Vectors(self.X-pt.X,self.Y-pt.Y); 
185   
186      def distanceOf(self,toPoint:'Points')->Real: 
187          """ Distance between two points 
188          """ 
189          return Vectors.lengthOf(toPoint-self);  
190   
191      def areaOf(self,p1:'Points',p2:'Points')->Real: 
192          """ Area of the triangle with three points 
193          """ 
194          return 0.5*Vectors.crossOp(p1-self,p2-self); 
195  #end Points 
196  #------------------------------------------------------------------------------# 
197   
198  class Lines(object): 
199      def __init__(self,a:Real,b:Real,c:Real)->None: 
200          """ Implicite line equation is A*x+B*y=C 
201              with sqrt(A*A+B*B)=1 
202          """ 
203          d=sqrt(a**2+b**2); 
204          self.A=a/d; self.B=b/d; self.C=c/d; 
205          if areCoordinatesEqual(self.A,0.0): 
206              xlp=0.0; 
207              ylp=self.C/self.B; 
208              xdir=1.0; 
209              ydir=0.0; 
210          elif areCoordinatesEqual(self.B,0.0): 
211              xlp=self.C/self.A; 
212              ylp=0.0; 
213              xdir=0.0; 
214              ydir=1.0; 
215          else: 
216              xlp=0.0; 
217              ylp=self.C/self.B; 
218              xdir= self.B; 
219              ydir= -self.A; 
220          # end if 
221          self.LP=Points(xlp,ylp); 
222          self.DV=Vectors(xdir,ydir); # Unit vector 
223          # end __init__ 
224   
225      def toClone(self)->'Lines': 
226          return Lines(self.A,self.B,self.C); 
227   
228      def __str__(self)->str: 
229          return ('ABC: '+str(self.A)+' '+str(self.B)+' '+str(self.C)+ 
230                  '\n\tLP: '+str(self.LP)+' | DV: '+str(self.DV)); 
231   
232      def __eq__(self,ln:'Lines')->bool: 
233          # Equality of two lines 
234          return (self.LP==ln.LP) and ((self.DV==ln.DV) or (self.DV==(-1.0*ln.DV))); 
235   
236      @staticmethod 
237      def toLine(p1:Points,p2:Points)->'Lines': 
238          """ A line through two points 
239              :raises InvalidDataError 
240                  if p1==p2 
241          """ 
242          if p1==p2: 
243              raise InvalidDataError("toLine with identical points") 
244          a=p1.Y-p2.Y; 
245          b=p2.X-p1.X; 
246          c=a*p1.X + b*p1.Y; 
247          return Lines(a,b,c); 
248      # end toLine 
249   
250      def distanceOf(self,pt:Points)->Real: 
251          """ Signed distance of a point to the line 
252          """ 
253          return self.A*pt.X + self.B*pt.Y - self.C; 
254   
255      def nearestPointOf(self,fromP:Points)->Points: 
256          """ Nearest point on the line from a point 
257          """ 
258          lP=self.LP; 
259          dV=self.DV; 
260          t=Vectors.dotOp(dV,fromP-lP); 
261          lP=lP+t*dV; 
262          return lP; 
263      # end nearestPointOf 
264   
265      def isPointInside(self,pt:Points)->bool: 
266          """ Is a point on the line? 
267              The mathematical equation for a point pt on line is 
268                  pt.X*self.A+pt.Y*self.B-self.C=0 
269          """ 
270          np=self.nearestPointOf(pt); 
271          return pt==np; 
272      # end isPointInside 
273   
274      def areOnSameSide(self,pt1:'Points',pt2:Points)->bool: 
275          """ Are both points on the same side relative to the line? 
276              :Pre self.isPointInside(pt1)==False 
277              :Pre self.isPointInside(pt2)==False 
278          """ 
279          ds1=self.distanceOf(pt1); 
280          ds2=self.distanceOf(pt2); 
281          return (ds1>0 and ds2>0) or ((ds1<0 and ds2<0)) 
282      # end areOnSameSide 
283   
284      def areParallel(self,withLine:'Lines')->bool: 
285          """ Test whether two lines are parallel 
286              Note: Equal lines are considered to be NOT parallel 
287          """ 
288          if (self.LP==withLine.LP): 
289              return False; 
290          d1=self.DV; d2=withLine.DV; 
291          return (d1==d2) or (d1==(-1)*d2); 
292      # end areParallel 
293   
294      def intersectionOf(self,withLine:'Lines')->Points: 
295          """ Returns the point of intersection of two lines 
296              :raises InfinityPoints 
297                  if self==withLine 
298              :raises NoPoint 
299                  if self.areParallel(withLine)==true 
300          """ 
301          L1=self; L2=withLine; 
302          if L1==L2: 
303              raise InfinityPoints; 
304          if L1.areParallel(L2): 
305              raise NoPoint; 
306          lP1=L1.LP.toClone(); ### ??? 
307          lP2=L2.LP; 
308          dV1=L1.DV; 
309          dV2Ortho=Vectors(-L2.DV.Y,L2.DV.X); 
310          q=Vectors.dotOp(dV1,dV2Ortho); 
311          ts=Vectors.dotOp(dV2Ortho,lP2-lP1); 
312          ts/=q; 
313          return lP1+ts*dV1; 
314      # end intersectionOf 
315   
316      def getNormalVector(self)->Vectors: 
317          """ Returns a unit vector perpendicular to the line 
318          """ 
319          return Vectors(self.A,self.B); 
320      # end getNormalVector 
321   
322      def getParallelLine(self,withDistance:Real)->'Lines': 
323          """ Returns the line parallel to self with withDistance 
324          """ 
325          return Lines(self.A,self.B,self.C+withDistance); 
326      # end getParallelLine 
327  # end Lines 
328  #------------------------------------------------------------------------------# 
329   
330  class Rays(object): 
331      def __init__(self,startPoint:Points, 
332                        direction:Vectors)->None: 
333          self.StartPoint=startPoint; 
334          self.Direction=direction.toUnitVector(); 
335      # end __init__ 
336   
337      def toClone(self)->'Rays': 
338          return Rays(self.StartPoint,self.Direction); 
339   
340      def __str__(self)->str: 
341          return 'SP: '+str(self.StartPoint)+' | DV: '+str(self.Direction); 
342   
343      def __eq__(self,withRay:'Rays')->bool: 
344          # Equality of two rays 
345          return ((self.StartPoint==withRay.StartPoint) and 
346                   self.Direction==withRay.Direction); 
347   
348      @staticmethod 
349      def toRay(pt1:Points,pt2:Points)->'Rays': 
350          """ Returns a ray from point pt1 through point pt2 
351          """ 
352          return Rays(pt1,pt2-pt1); 
353       
354      def toLine(self)->Lines: 
355          """ To extend a ray to a line 
356          """ 
357          return (Lines.toLine(self.StartPoint, 
358                  self.StartPoint+self.Direction)); 
359   
360      def nearestPointOf(self,fromP:Points)->Points: 
361          """ Nearest point on the ray from a point 
362          """ 
363          lP=self.StartPoint.toClone(); 
364          dV=self.Direction; 
365          t=Vectors.dotOp(dV,fromP-lP); 
366          if t>=0.0:       
367              lP=lP+t*dV; 
368          return lP; 
369      # end nearestPointOf 
370   
371      def isPointInside(self,pt:Points)->bool: 
372          """ Is a point inside the ray 
373              (Inside means different from the start point) 
374          """ 
375          np=self.nearestPointOf(pt); 
376          if np==self.StartPoint: 
377              return False; 
378          else: 
379              return np==pt; 
380      # end isPointInside 
381   
382      def intersectionOf(self,withRay:'Rays')->Points: 
383          """ Returns the point of intersection of two rays 
384              :raises NoPoint 
385              :raises InfinityPoints 
386          """ 
387          ry1=self; 
388          ry2=withRay; 
389          ln1=ry1.toLine(); 
390          ln2=ry2.toLine(); 
391          if Lines.areParallel(ln1,ln2): 
392              raise NoPoint; 
393          if ln1==ln2: 
394              if (ry1.isPointInside(ry2.StartPoint) or 
395                  ry2.isPointInside(ry1.StartPoint)): 
396                  raise InfinityPoints; 
397              elif ((ry1.StartPoint==ry2.StartPoint) and 
398                    (ry1.Direction==ry2.Direction)): 
399                  raise InfinityPoints; 
400              else: 
401                  raise NoPoint; 
402          # end if 
403          ip=Lines.intersectionOf(ln1,ln2); 
404          if (ry1.isPointInside(ip) and 
405              ry2.isPointInside(ip)): 
406              return ip; 
407          else: 
408              raise NoPoint; 
409          # end if 
410      # end intersectionOf 
411  # end Rays 
412  #------------------------------------------------------------------------------# 
413   
414  class Segments(object): 
415      def __init__(self,p1:Points,p2:Points)->None: 
416          """ The oriented line segment from point p1 to point p2 
417          """ 
418          self.P1=p1; self.P2=p2; 
419   
420      def toClone(self)->'Segments': 
421          return Segments(self.P1,self.P2); 
422   
423      def update(self,withSegment:'Segments')->None: 
424          self.P1=withSegment.P1; 
425          self.P2=withSegment.P2; 
426      # end update 
427   
428      def __eq__(self,sgm:'Segments')->bool: 
429          """ Test for oriented equality of two segments 
430          """ 
431          return (self.P1==sgm.P1) and (self.P2==sgm.P2); 
432   
433      def __str__(self)->str: 
434          return str(self.P1)+' | '+str(self.P2); 
435   
436      def toLine(self)->Lines: 
437          """ Returns the extension of the segment to a line 
438          """ 
439          return Lines.toLine(self.P1,self.P2); 
440   
441      def isPointInside(self,pt:Points)->bool: 
442          """ Is a point inside the segment? 
443          """ 
444          ps1=self.P1; 
445          ps2=self.P2; 
446          rs1=Rays.toRay(ps1,ps2); 
447          rs2=Rays.toRay(ps2,ps1); 
448          return rs1.isPointInside(pt) and rs2.isPointInside(pt); 
449      # end isPointInside 
450   
451      def distanceOf(self,pt:Points)->bool: 
452          """ Returns the signed distance of a point from the segment 
453          :Pre pt is not a point of the segment 
454          """ 
455          From=pt; To=self; 
456          ln=To.toLine(); 
457          dOrtho=Vectors(ln.A,ln.B); 
458          if (Vectors.dotOp(From-To.P2,To.P2-To.P1)>0.0): 
459              sgn=1 if (Vectors.dotOp(dOrtho,From-To.P2)>=0) else -1; 
460              return sgn*From.distanceOf(To.P2); 
461          elif (Vectors.dotOp(From-To.P1,To.P1-To.P2)>0.0): 
462              sgn=1 if (Vectors.dotOp(dOrtho,From-To.P1)>=0) else -1; 
463              return sgn*From.distanceOf(To.P1); 
464          else: 
465              return ln.distanceOf(From); 
466          # end if 
467      # end distanceOf 
468   
469      def intersectionOf_withRay(self,withRay:Rays)->Points: 
470          """ Returns the point of intersection of the segment with the ray 
471              :raises NoPoint 
472              :raises InfinityPoints 
473          """ 
474          ps1=self.P1; 
475          ps2=self.P2; 
476          rs1=Rays.toRay(ps1,ps2); 
477          rs2=Rays.toRay(ps2,ps1); 
478   
479          intersectionKind1=IntersectionKind.onePoint; 
480          intersectionKind2=IntersectionKind.onePoint; 
481   
482          try: 
483              ip1=withRay.intersectionOf(rs1); 
484              if (ip1==ps1) or (ip1==ps2): 
485                  raise NoPoint; 
486          except NoPoint: 
487              intersectionKind1=IntersectionKind.noPoint; 
488          except InfinityPoints: 
489              intersectionKind1=IntersectionKind.infinityPoints; 
490          # end try 
491   
492          try: 
493              ip2=withRay.intersectionOf(rs2); 
494              if (ip2==ps1) or (ip2==ps2): 
495                  raise NoPoint; 
496          except NoPoint: 
497              intersectionKind2=IntersectionKind.noPoint; 
498          except InfinityPoints: 
499              intersectionKind1=IntersectionKind.infinityPoints; 
500          # end try 
501   
502          if ((intersectionKind1==IntersectionKind.onePoint) and 
503              (intersectionKind2==IntersectionKind.onePoint)): 
504              assert(ip1==ip2); # TBD 
505              return ip1; 
506          elif ((intersectionKind1==IntersectionKind.noPoint) and 
507                (intersectionKind2==IntersectionKind.noPoint)): 
508              raise NoPoint; 
509          elif ((intersectionKind1==IntersectionKind.noPoint) and 
510                (intersectionKind2==IntersectionKind.onePoint)): 
511              raise NoPoint; 
512          elif ((intersectionKind2==IntersectionKind.noPoint) and 
513                (intersectionKind1==IntersectionKind.onePoint)): 
514              raise NoPoint; 
515          else: 
516              raise InfinityPoints; # TBD 
517          # end if 
518      # end intersectionOf_withRay 
519   
520      def intersectionOf(self,withSegment:'Segments')->Points: 
521          """ Returns the point of intersection of two segments 
522              :raises NoPoint 
523              :raises InfinityPoints 
524          """ 
525          ps1=self.P1; 
526          ps2=self.P2; 
527          rs1=Rays.toRay(ps1,ps2); 
528          rs2=Rays.toRay(ps2,ps1); 
529          try: 
530              ip1=withSegment.intersectionOf_withRay(rs1); 
531              ip2=withSegment.intersectionOf_withRay(rs2); 
532          except InfinityPoints: 
533              if (withSegment.isPointInside(ps1) or 
534                  withSegment.isPointInside(ps2)): 
535                  raise InfinityPoints; 
536              else: 
537                  raise NoPoint; 
538              # end if 
539          except NoPoint: 
540              raise NoPoint; 
541          else: 
542              assert ip1==ip2; 
543              return ip1; 
544          # end try 
545      # end intersectionOf 
546   
547      def bisectorOf(self)->Lines: 
548          """ Returns the bisector to self, 
549              i.e. the line that is perpendicular 
550              to self and goes through its middle 
551          """ 
552          ln=self.toLine(); 
553          xMid=(self.P1.X+self.P2.X)/2.0; 
554          yMid=(self.P1.Y+self.P2.Y)/2.0; 
555          return Lines(-ln.B, 
556                        ln.A, 
557                       -ln.B*xMid + ln.A*yMid); 
558      # end bisectorOf 
559   
560      @staticmethod 
561      def areNotIntersecting(segments:Sequence['Segments'])->None: 
562          """ The segments in the list must not intersect 
563              :raises InvalidDataError 
564                  if two segments are intersecting 
565          """ 
566          for sgo in segments: 
567              for sgi in segments: 
568                  if not sgo==sgi: 
569                      try: 
570                          sgo.intersectionOf(sgi); 
571                      except NoPoint: 
572                          pass; # Requirement 
573                      except InfinityPoints: 
574                          raise InvalidDataError('Overlaping segments'); 
575                      else: 
576                          raise InvalidDataError('Overlaping segments'); 
577                      # end try 
578                  # end if 
579              # end for 
580          # end for 
581      # end areNotIntersecting 
582  # end Segments 
583  #------------------------------------------------------------------------------# 
584   
585  class Sectors(object): 
586      def __init__(self,startPoint:Points, 
587                        direction1:Vectors, 
588                        direction2:Vectors)->None: 
589          self.StartPoint=startPoint; 
590          self.Direction1=direction1.toUnitVector(); 
591          self.Direction2=direction2.toUnitVector(); 
592      # end __init__ 
593   
594      def toClone(self)->'Sectors': 
595          return Sectors(self.StartPoint,self.Direction1,self.Direction2); 
596   
597      def __str__(self)->str: 
598          return ('SP: '+str(self.StartPoint)+ 
599                  ' | DV1: '+str(self.Direction1)+ 
600                  ' | DV2: '+str(self.Direction2)); 
601   
602      def __eq__(self,withSector:'Sectors')->bool: 
603          return ((self.StartPoint==withSector.StartPoint) and 
604                   ((self.Direction1==withSector.Direction1) and 
605                   (self.Direction2==withSector.Direction2)) or 
606                   ((self.Direction1==withSector.Direction2) and 
607                   (self.Direction2==withSector.Direction1))); 
608   
609      @staticmethod 
610      def toSector(pt0:Points,pt1:Points,pt2:Points)->'Sectors': 
611          return Sectors(pt0,pt1-pt0,pt2-pt0); 
612   
613      def openingAngleOf(self)->Real: 
614          """ Gibt den nicht-orientierten Öffnungswinkel zurück 
615          """ 
616          return abs(self.Direction2.dirAngleOf()-self.Direction1.dirAngleOf()); 
617  # end Sectors 
618  #------------------------------------------------------------------------------# 
619   
620  class SectorWithSegments(Sectors): 
621      def __init__(self,startPoint:Points, 
622                        direction1:Vectors, 
623                        direction2:Vectors)->None: 
624          self.Segments=[]; 
625          Sectors.__init__(self,startPoint,direction1,direction2); 
626      # end __init__ 
627   
628      def __str__(self)->str: 
629          output=''; 
630          output+=Sectors.__str__(self); 
631          output+=' || '; 
632          for sgm in self.Segments: 
633              output+=str(sgm)+' | '; 
634          return(output); 
635      # end __str__ 
636   
637      def add(self,segment:Segments)->bool: 
638          """  Tries to add the segment to self 
639          """ 
640          p0=self.StartPoint; 
641          p1=segment.P1; p2=segment.P2; 
642          sec=Sectors.toSector(p0,p1,p2); 
643          if self==sec: 
644              self.Segments.append(segment); 
645              return True; 
646          else: 
647              return False; 
648          # end if 
649      # end add 
650   
651      @staticmethod 
652      def addToList(secwsgm:Sequence['SectorWithSegments'], 
653                    sgm:Segments)->None: 
654          """ Adds the segment to one of the sectors of the list 
655              :raises InvalidDataError 
656                  if there is no sector suitable for the segment 
657          """ 
658          added=False; 
659          for sec in secwsgm: 
660              added=False; 
661              if sec.add(sgm): 
662                  added=True; 
663                  break; 
664          # end for 
665          if not added: 
666              raise InvalidDataError('addToList'); 
667      # end addToList 
668   
669      def getMinimalDistanceSegment(self)->Segments: 
670          """ Returns the segment that is nearest to the StartPoint 
671              of the sector 
672          """ 
673          segments=self.Segments; 
674          toPoint=self.StartPoint; 
675          minSegment=segments[0]; 
676          minlg1=Vectors.lengthOf(minSegment.P1-toPoint); 
677          minlg2=Vectors.lengthOf(minSegment.P2-toPoint); 
678   
679          for sgm in segments: 
680              lg1=Vectors.lengthOf(sgm.P1-toPoint); 
681              lg2=Vectors.lengthOf(sgm.P2-toPoint); 
682   
683              if ((lg1<minlg1 and lg2<=minlg2) or 
684                  (lg1<=minlg1 and lg2<minlg2)): 
685                  minlg1=lg1; 
686                  minlg2=lg2; 
687                  minSegment.update(sgm); 
688              # end if 
689          # end for 
690   
691          return minSegment; 
692      # end getMinimalDistanceSegment 
693  # end SectorWithSegments 
694  #------------------------------------------------------------------------------# 
695   
696  class Triangles(object): 
697      def __init__(self,p0:Points,p1:Points,p2:Points)->None: 
698          self.P0=p0; self.P1=p1; self.P2=p2; 
699   
700      def __str__(self)->str: 
701          return str(self.P0)+' | '+str(self.P1)+' | '+str(self.P2); 
702   
703      def areaOf(self)->Real: 
704          return Points.areaOf(self.P0,self.P1,self.P2); 
705   
706      def isPointInside(self,pt:Points)->bool: 
707          areaT=Points.areaOf(self.P0,self.P1,self.P2); 
708          # Barycentric coordinates with (alpha+beta+gamma)=1 
709          alpha=Points.areaOf(pt,self.P1,self.P2)/areaT; 
710          beta =Points.areaOf(pt,self.P2,self.P0)/areaT; 
711          gamma=Points.areaOf(pt,self.P0,self.P1)/areaT; 
712           
713          return (0.0<alpha<1.0) and (0.0<beta<1.0) and (0.0<gamma<1.0); 
714              #! No use of some delta - TBD 
715      # end isPointInside 
716  # end Triangles 
717  #------------------------------------------------------------------------------# 
718   
719  class Polygons(object): 
720      def __init__(self,points:Sequence[Points])->None: 
721          self.NbPoints=len(points); 
722          self.Points=[]; 
723          self.Points+=points; 
724      # end __init__ 
725   
726      def toClone(self)->'Polygons': 
727          return Polygons(self.Points); 
728   
729      def __str__(self)->str: 
730          output=''; 
731          for pt in self.Points: 
732              output+=str(pt)+' | '; 
733   
734          return(output);           
735      # end __str__ 
736   
737      def distanceOf(self,pt:Points)->Real: 
738          dist=-1; 
739          for Ix in range(self.NbPoints-1): 
740              p1=self.Points[Ix]; 
741              p2=self.Points[Ix+1]; 
742              sgm=Segments(p1,p2); 
743              dist=min(maxLength,sgm.distanceOf(pt));            
744          # end for 
745          p1=self.Points[1]; 
746          p2=self.Points[self.NbPoints-1]; 
747          sgm=Segments(p1,p2); 
748          dist=min(dist,sgm.distanceOf(pt)); 
749          return dist; 
750      # end distanceOf 
751   
752      def areaOf(self)->Real: 
753          """ Returns the signed area of the polygon 
754          """ 
755          p0=self.Points[0]; 
756          area=0.0; 
757          for Ix in range(1,self.NbPoints-1): 
758              p1=self.Points[Ix]; 
759              p2=self.Points[Ix+1]; 
760              area+=Vectors.crossOp(p1-p0,p2-p0); 
761          # end for 
762          return 0.5*area; 
763      # end areaOf 
764   
765      def isPointOnside (self,pt0:Points)->bool: 
766          """ Is a point onside the polygon? 
767              Onside means: The point is inside or on the edges of the polygon 
768              This algorithm is adapted from 
769              'The GNAT Components Collection', www.adacore.com 
770          """ 
771          Ie=self.NbPoints-1; 
772          onInside= False; 
773          deltaY=-1.0; 
774          points=self.Points; 
775   
776          for Ix in range(Ie): 
777              deltaY=pt0.Y-points[Ix].Y; 
778   
779              if (((0.0<=deltaY and pt0.Y<points[Ie].Y) 
780                    or (points[Ie].Y<=pt0.Y and deltaY<0.0)) 
781                  and (pt0.X-points[Ix].X<(points[Ie].X-points[Ix].X)*deltaY 
782                    /(points[Ie].Y-points[Ix].Y))): 
783   
784                  onInside=not onInside; 
785           # end if 
786        # end for 
787   
788          return onInside; 
789     # end isPointOnside; 
790  # end Polygons 
791  #------------------------------------------------------------------------------# 
792   
793  class Circles(object): 
794      class NoCircle(Exception): 
795          def __init__(self): pass;  
796   
797      def __init__(self,point:Points,radius:Real)->None: 
798          self.C=point; 
799          self.R=radius; 
800      # end def 
801   
802      def toClone(self)->'Circles': 
803          return Circles(self.C,self.R); 
804   
805      def __str__(self)->str: 
806          return str(self.C)+' | '+str(self.R); 
807   
808      @staticmethod 
809      def toCircle(pt1:Points,pt2:Points,pt3:Points)->'Circles': 
810          """ Creates the circle through 3 points 
811              :raises NoCircle 
812                  if points are on a line 
813          """ 
814          sgm1=Segments(pt1,pt2); 
815          sgm2=Segments(pt2,pt3); 
816          bis1=sgm1.bisectorOf(); 
817          bis2=sgm2.bisectorOf(); 
818          try: 
819              center=Lines.intersectionOf(bis1,bis2); 
820          except (NoPoint,InfinityPoints): 
821              raise Circles.NoCircle; 
822          # end try 
823          radius=pt1.distanceOf(center); 
824          return Circles(center,radius); 
825      # end toCircle 
826   
827      def areaOf(self)->Real: 
828          return pi*self.R*self.R; 
829   
830      def distanceOf(self,pt:Points)->Real: 
831          """ Returns the signed distance of a point to the circle 
832          """ 
833          d=Points.distanceOf(self.C,pt); 
834          return d-self.R; 
835      # end distanceOf 
836   
837      def isPointInside(self,pt:Points)->bool: 
838          dist=self.distanceOf(pt); 
839          return (dist<0) and not areLengthsEqual(dist,0); 
840      # end isPointInside 
841  # end Circles 
842  #------------------------------------------------------------------------------# 
843   
844  class PolygonTrains(object): # Polygonzug 
845   
846      def __init__(self,points:Sequence[Points])->None: 
847          self.Points=[]; 
848          self.Points+=points; 
849      # end __init__ 
850   
851      def getClone(self)->'PolygonTrains': 
852          return PolygonTrains(self.Points); 
853   
854      def __str__(self)->str: 
855          output=''; 
856          for pt in self.Points: 
857              output+=str(pt)+' | '; 
858          return(output); 
859      # end __str__ 
860   
861      def getSegments(self)->List[Segments]: 
862          """ Returns the segments of the polygon train 
863          """ 
864          la=self.Points; 
865          fIx=0; lIx=len(la)-1; 
866          lf=la[fIx:lIx]; ll=la[fIx+1:lIx+1]; 
867          return [Segments(*tp) for tp in list(zip(lf,ll))]; 
868      # end getSegments 
869  # end PolygonTrains 
870  #------------------------------------------------------------------------------# 
871   
872  class ConesOfRays(object): # Strahlenbueschel 
873   
874      def __init__(self,startPoint:Points)->None: 
875          self.StartPoint=startPoint; 
876          self.Rays=[]; 
877      # end __init__ 
878   
879      def __str__(self)->str: 
880          output=''; 
881          for ray in self.Rays: 
882              angle=ray.Direction.dirAngleOf()*r2d; 
883              output+='\n'+str(angle)+' - '+str(ray)+' | '; 
884          # end for 
885          return(output); 
886      # end __str__ 
887   
888      def add(self,ray:Rays)->None: 
889          """ Add the ray to self 
890              :raises InvalidDataError 
891                  if start points of rays are different 
892          """ 
893          if not self.StartPoint==ray.StartPoint: 
894              raise InvalidDataError('different start points'); 
895          for elem in self.Rays: 
896              if elem==ray: return None; # No dublicates 
897          self.Rays.insert(0,ray); 
898      # end add 
899   
900      @staticmethod 
901      def createFromPoints(startPoint:Points, 
902                           points:Sequence[Points])->'ConesOfRays': 
903          """ Creates a cone of rays using a start point 
904              for the rays and some other points 
905          """ 
906          cone=ConesOfRays(startPoint); 
907          for pt in points: 
908              dirc=(pt-startPoint).toUnitVector(); 
909              cone.add(Rays(startPoint,dirc)); 
910          # end for 
911   
912          return cone; 
913      # end createFromPoints 
914  # ConesOfRays 
915  #------------------------------------------------------------------------------# 
916   
917      def divideIntersectedSegments(self,sgms:List[Segments])->None: 
918          """ Schneidet ein Strahl ein Segment im Innern, 
919              so wird dieses Segment in zwei Einzelsegmente zerlegt 
920          """ 
921          for ray in self.Rays: 
922              for sgm in sgms[:]: 
923                  try: 
924                      ip=sgm.intersectionOf_withRay(ray); 
925                  except NoPoint: 
926                      pass; 
927                  except InfinityPoints: 
928                      sgms.remove(sgm); 
929                      # Segment is part of ray; no extension, no visibility 
930                  else: 
931                      sgm1=Segments(sgm.P1,ip); 
932                      sgms.append(sgm1); 
933                      sgm2=Segments(sgm.P2,ip); 
934                      sgms.append(sgm2); 
935                      sgms.remove(sgm); 
936                  # end try 
937              # end for 
938          # end for 
939      # divideIntersectedSegments 
940  # end ConesOfRays 
941  #------------------------------------------------------------------------------# 
942  #------------------------------------------------------------------------------# 
943   
944  if __name__ == '__main__': 
945      print('\n# Beginning main ...'); 
946   
947      print('\n# Finished main.\n'); 
948  # end if main 
949   
950  #------------------------------------------------------------------------------# 
951  #------------------------------------------------------------------------------#