прикреплённый файл:celyetochG.py к странице LecturesVMSH/2011-03-09

   1 #!/usr/bin/python
   2 # coding: UTF8
   3 
   4 from random import *
   5 from math import *
   6 
   7 def semiplane(M,M1,M2):
   8     '''Лежит ли точка M в положительной полуплоскости прямой M₁M₂?'''
   9     return (M2[0]-M1[0])*(M[1]-M1[1])-(M2[1]-M1[1])*(M[0]-M1[0]) > 0
  10 
  11 def part_semiplane(M,M1,M2):
  12     '''Лежит ли точка M в положительной полуплоскости отрезка M₁M₂?'''
  13     M3,M4=(M1[0]+(M1[1]-M2[1]),M1[1]-(M1[0]-M2[0])),(M2[0]+(M2[1]-M1[1]),M2[1]-(M2[0]-M1[0]))
  14     return not semiplane(M,M1,M2) and semiplane(M,M1,M3) == semiplane(M,M2,M4)
  15 
  16 def len2(M1,M2):
  17     '''Расстояние между двумя точками'''
  18     return sqrt((M1[0]-M2[0])**2+(M1[1]-M2[1])**2)
  19 
  20 def area3(M1,M2,M3):
  21     '''Площадь и длины сторон треугольника по трём точкам'''
  22     a,b,c=len2(M1,M2),len2(M2,M3),len2(M3,M1)
  23     p=(a+b+c)/2.
  24     z=p*(p-a)*(p-b)*(p-c)
  25     if z<0: return 0,a,b,c    # погрешность вычисления
  26     return sqrt(p*(p-a)*(p-b)*(p-c)),a,b,c
  27 
  28 def area(M1,M2,M3):
  29     '''Площадь треугольника по трём точкам'''
  30     return area3(M1,M2,M3)[0]
  31 
  32 def polygen(N, maxX=800-5, maxY=600-5, minX=5, minY=5):
  33     '''Сгенерировать последовательность точек-вершин несамопересекающегося
  34     (возможно, невыпуклого) многоугольника'''
  35     def cmpx(a,b): return cmp(a[0],b[0])
  36     Dots=zip(sample(xrange(minX,maxX),N),sample(xrange(minY,maxY),N))
  37     Dots.sort(cmpx)
  38     D1,D2=[],[]
  39     for x,y in Dots:
  40         if semiplane((x,y),Dots[0],Dots[-1]): D1.append((x,y))
  41         else: D2.insert(0,(x,y))
  42     return D1+D2
  43 
  44 def angleOLD(M,M1,M2):
  45     '''Угол M1-M-M2''' 
  46     # S=a*b*sin(ab)/2
  47     # ab=arcsin(2*s/(a*b))
  48     S,a,b,c=area3(M,M1,M2)
  49     sign = (semiplane(M1,M,M2) and 1 or -1)
  50     try:
  51         bc = asin(2*S/(a*c))
  52     except:
  53         print 2*S, a*c, 2*S-a*c, a, c
  54         raise
  55     if b*b>a*a+c*c:
  56         return (pi-bc)*sign
  57     else:
  58         return bc*sign
  59 
  60 def angle(M,M1,M2):
  61     '''Угол M1-M-M2''' 
  62     # S=a*b*sin(ab)/2
  63     # ab=arcsin(2*s/(a*b))
  64     S,a,b,c=area3(M,M1,M2)
  65     sign = (semiplane(M1,M,M2) and 1 or -1)
  66     if not a*c: return 0    # вырожденный треугольник
  67     if 2*S>a*c: bc=pi/2     # погрешность вычислнения
  68     else:      bc = asin(2*S/(a*c))
  69     if b*b>a*a+c*c:
  70         return (pi-bc)*sign
  71     else:
  72         return bc*sign
  73 
  74 if __name__ == "__main__":
  75     import pygame, sys
  76     pygame.init()
  77     screen=pygame.display.set_mode((1024,768))
  78     Trg=[(10,10,),(20,20),(30,30)]
  79     Colors=[pygame.Color(c) for c in ("red","green","yellow")]
  80 
  81     while True:
  82         event = pygame.event.wait()
  83         for event in [event]+pygame.event.get():
  84             if   event.type == pygame.QUIT: sys.exit()
  85             elif event.type == pygame.KEYUP:
  86               if   event.key == 27: sys.exit()
  87               else:
  88                   screen.fill(pygame.Color("black"))
  89                   pygame.draw.lines(screen, pygame.Color("khaki"), True, polygen(20,1020,760))
  90             elif event.type == pygame.MOUSEBUTTONDOWN:
  91                 Trg[(event.button-1)%3]=event.pos
  92                 screen.fill(pygame.Color("black"))
  93                 pygame.draw.line(screen,pygame.Color("khaki"), Trg[0],Trg[1],1)
  94                 pygame.draw.line(screen,pygame.Color("khaki"), Trg[0],Trg[2],1)
  95                 for m,c in zip(Trg,Colors):
  96                     pygame.draw.circle(screen,c,m,3)
  97                 print angle(*Trg)
  98         pygame.display.flip()