прикреплённый файл:2013-11-29-polynom.py к странице LecturesVMSH/Python/2013-11-29

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Лежит ли точка внутри многоугольника. В первой строке вводятся три целых числа – N (3≤N≤100000) и координаты точки. Далее в N строках задается по паре целых чисел – координаты очередной вершины простого (непересекающегося, но, возможно, невыпуклого) многоугольника в порядке обхода по или против часовой стрелки. Выведите одну строку: “YES”, если заданная точка содержится в приведённом многоугольнике или на его границе, и “NO” в противном случае.
   5 
   6     рисовать многоугольник
   7     вводить многоугольник не текстом, а мышью (например, левая кнопка мыши начинает ввод или добавляет очередную точку, правая завершает ввод)
   8     при перемещении курсора (если многоугольник готов) отображать, лежит ли точка внутри него
   9 
  10     <!> генерировать несамопересекающийся случайный многоугольник, а не вводить его мышью (как?)
  11 '''
  12 
  13 import pygame, random
  14 from math import *
  15 
  16 size = width, height = 1000,700
  17 screen = pygame.display.set_mode(size)
  18 black = pygame.Color("black")
  19 tan = pygame.Color("tan")
  20 red = pygame.Color("tomato")
  21 green = pygame.Color("limegreen")
  22 
  23 def TriAngle(a,o,b):
  24     res = atan2(a[1]-o[1], a[0]-o[0]) - atan2(b[1]-o[1], b[0]-o[0])
  25     if res > pi:
  26         res -= pi
  27     elif res < -pi:
  28         res += pi
  29     return res
  30 
  31 def CheckInDot(pos, poly):
  32     global indot
  33     s = 0
  34     # dpoly — список пар последовательных вершин
  35     dpoly = zip(poly,poly[1:]+poly[:1])
  36     for a,b in dpoly:
  37         s += TriAngle(a, pos, b)
  38     return abs(s) > pi/2
  39 
  40 def InputLoop(event):
  41     '''Обработка событий в режиме ввода'''
  42     global polynom, status
  43     if event.type == pygame.MOUSEBUTTONDOWN:
  44         if event.button == 1:
  45             polynom.append(event.pos)
  46         elif event.button == 2:
  47             GenPoly()
  48             status = "Input done"
  49         elif event.button == 3:
  50             if len(polynom)>2:
  51                 status = "Input done"
  52 
  53 def InputRedraw():
  54     '''Перерисовка в режиме ввода'''
  55     screen.fill(black)
  56     if polynom:
  57         for pos in polynom:
  58             pygame.draw.circle(screen, tan, pos, 2)
  59         if len(polynom)>1:
  60             pygame.draw.lines(screen, tan, False, polynom)
  61 
  62 def InputLogic():
  63     pass
  64 
  65 def ShowLoop(event):
  66     '''Обработка событий в режиме показа'''
  67     global status, dotpos
  68     if event.type == pygame.MOUSEMOTION:
  69         dotpos = event.pos
  70     elif event.type == pygame.MOUSEBUTTONDOWN:
  71         status = "Show done"
  72 
  73 def ShowRedraw():
  74     screen.fill(black)
  75     if polynom:
  76         pygame.draw.lines(screen, tan, True, polynom)
  77     if dotpos:
  78         pygame.draw.circle(screen, dotin and green or red, dotpos, 3)
  79 
  80 def ShowLogic():
  81     global dotin
  82     if dotpos:
  83         dotin = CheckInDot(dotpos, polynom)
  84 
  85 def CheckStatus():
  86     global status, polynom, dotpos, CurrentLoop, CurrentLogic, CurrentRedraw
  87     if status == "Show done":
  88         pygame.mouse.set_visible(True)
  89         polynom,dotpos = [],None
  90         CurrentLoop, CurrentLogic, CurrentRedraw = InputLoop, InputLogic, InputRedraw
  91     elif status == "Input done":
  92         pygame.mouse.set_visible(False)
  93         CurrentLoop, CurrentLogic, CurrentRedraw = ShowLoop, ShowLogic, ShowRedraw
  94     status = ""
  95 
  96 def PseudoVect(dot, a, b):
  97     return (a[0]-b[0])*(dot[1]-b[1])-(a[1]-b[1])*(dot[0]-b[0])
  98 
  99 def GenPoly():
 100     global polynom
 101     polydots = [(random.randrange(1,width-1),random.randrange(1,height-1)) for i in xrange(random.randrange(3,12))]
 102     P,p=min(polydots),max(polydots)
 103     polynom = sorted([dot for dot in polydots if PseudoVect(dot,p,P)>0]) +\
 104               sorted([dot for dot in polydots if PseudoVect(dot,p,P)<=0],reverse=True)
 105 
 106 again=True
 107 # CurrentLoop — обработчик текущего режима. Заодно по нему можно выяснить и сам режим.
 108 CurrentLoop, CurrentLogic, CurrentRedraw = InputLoop, InputLogic, InputRedraw
 109 polynom,dotpos,status = [],None,""
 110 while again:
 111     event = pygame.event.wait()
 112     # Общие события
 113     if event.type == pygame.QUIT:
 114         again = False
 115     CurrentLoop(event)
 116     CurrentLogic()
 117     CheckStatus()
 118     CurrentRedraw()
 119     pygame.display.flip()