Exemples en Python

Exemple 1

Una càmera sensa el perfil d'una sèrie d'objectes que passen per una banda transportadora. Els perfils són captats com una poligonal simple i tancada.

Una poligonal és una seqüència de punts del pla \((p_0, p_1, \dots, p_k)\) que representa una seqüència de segments \( ([p_0,p_1], [p_1,p_2], \dots [p_k,p_0]) \) cap dels quals s'intersecta amb cap altre. Per a que una poligonal tingui sentit cal que la seqüència tingui com a mínim 3 punts.

Es vol construïr un programa que llegeix una sèrie de perfils i determina quants son dins d'un cercle de radi 1 i centrat en l'orígen. Assumeix que la seqüència de polígonals s'acaba amb una poligonal buida, és a dir sense cap punt. El format de la seqüència de poligonals és com el del següent exemple:

(x0,y0)
(x1,y1)
(xn,yn),
()
(x0,y0),
...,
(xk,yk),
()
()

Noteu que cada poligonal acaba sempre amb un punt buit () i que la poligonal buida (sense punts) actua de sentinella.

Solució

El primer que farem és implementar una classe Punt per representar un punt en el pla. Aquest punt serà després el component principal de les poligonals:

   1 from math import sqrt
   2 
   3 class Punt(object):
   4 
   5    def __init__(self, x=0.0, y=0.0):
   6       self.x = x
   7       self.y = y
   8 
   9    def dist(self,p):
  10       """
  11       Distància entre dos punts.
  12       """
  13       return sqrt((self.x - p.x) ** 2 + (self.y - p.y) ** 2)

Afegirem també una classe que representi cercles arbitraris en el pla. La seva representació contindrà un Punt (el centre) i un radi. A més Hi afegirem una operació que permeti saber si un Punt donat és dins o fora del cercle. Noteu que això passa si la distància entre el centre i el punt és menor que el radi:

   1 class Cercle(object):
   2 
   3    def __init__(self, c = Punt(), r=1.0):
   4       self.c = c
   5       self.r = r
   6 
   7    def dins(self, p):
   8       return self.c.dist(p) < self.r

Començarem implementant una classe que representi les poligonals. Cada poligonal la representarem com una llista de punts. Dotarem la classe de modificadors que permetin afegir nous punts a la poligonal, de la funció len que permetrà saber el nombre de punts de la poligonal i també d'una classe que permeti comprovar si una poligonal es troba completament inclosa en un cercle.

   1 class Poligonal(object):
   2 
   3    def __init__(self):
   4       self.lp = []
   5 
   6    def add(self, p):
   7       self.lp.append(p)
   8 
   9    def __len__(self):
  10       return len(self.lp)
  11 
  12    def dins(self,c):
  13       return all([c.dins(p) for p in self.lp])

En base a aquestes classes podem escriure ara un programa principal que resol l'enunciat simplement llegint la seqüència de poligonals. Per llegir la seqüència de poligonals podem usar unes funcions auxiliars:

   1 def llegir_punt():
   2    """
   3    Retorna un Punt o None si no hi ha més punts.
   4    """
   5    s = raw_input().strip().strip('()')
   6    if s :
   7       punts = s.split(',')
   8       return Punt(float(punts[0]), float(punts[1]))
   9    else:
  10       return None
  11 
  12 def llegir_poligonal():
  13     """
  14     Retorna una poligonal o None
  15     """
  16     p = llegir_punt()
  17     if p is None:
  18        return None
  19     else:
  20        poli = Poligonal()
  21        while p is not None:
  22           p.add(poli)
  23           p = llegir_punt()
  24        return poli

A partir d'aquí, crear una funció que compti les poligonals incloses en el cercle unitat és pot fer així:

   1 def compta_incloses():
   2    n = 0
   3    cu = Cercle()
   4    p = llegir_poligonal()
   5    while p is not none:
   6       if p.dins(cu):
   7          n += 1
   8       p = llegir_poligonal()
   9    return n

Amb tot això, el programa complet escrit en un únic mòdul és el següent:

   1 # -*- encoding: utf-8 -*-
   2 
   3 from math import sqrt
   4 
   5 
   6 class Punt(object):
   7 
   8    def __init__(self, x=0.0, y=0.0):
   9       self.x = x
  10       self.y = y
  11 
  12    def dist(self,p):
  13       """
  14       Distància entre dos punts.
  15       """
  16       return sqrt((self.x - p.x) ** 2 + (self.y - p.y) ** 2)
  17 
  18 
  19 class Cercle(object):
  20 
  21    def __init__(self, c = Punt(), r=1.0):
  22       self.c = c
  23       self.r = r
  24 
  25    def dins(self, p):
  26       return self.c.dist(p) < self.r
  27 
  28 
  29 class Poligonal(object):
  30 
  31    def __init__(self):
  32       self.lp = []
  33 
  34    def add(self, p):
  35       self.lp.append(p)
  36 
  37    def __len__(self):
  38       return len(self.lp)
  39 
  40    def dins(self,c):
  41       return all([c.dins(p) for p in self.lp])
  42 
  43 
  44 def llegir_punt():
  45    """
  46    Retorna un Punt o None si no hi ha més punts.
  47    """
  48    s = raw_input().strip().strip('()')
  49    if s :
  50       punts = s.split(',')
  51       return Punt(float(punts[0]), float(punts[1]))
  52    else:
  53       return None
  54 
  55 string
  56 def llegir_poligonal():
  57     """
  58     Retorna una poligonal o None
  59     """
  60     p = llegir_punt()
  61     if p is None:
  62        return None
  63     else:
  64        poli = Poligonal()
  65        while p is not None:
  66           p.add(poli)
  67           r = llegir_punt()
  68        return poli
  69 
  70 
  71 def compta_incloses():
  72    n = 0
  73    cu = Cercle()
  74    p = llegir_poligonal()
  75    while p is not None:
  76       if p.dins(cu):
  77          n += 1
  78    return n
  79 
  80 
  81 if __name__ == '__main__':
  82    print compta_incloses()