Σημειωματάριο Τρίτης 28 Απρ. 2015

Μερικά classes για απλά γεωμετρικά αντικείμενα

Σήμερα θα υλοποιήσουμε κάποια classes για γεωμετρικά αντικείμενα (σημεία, ευθύγραμμα τμήματα και κύκλους). Για κάθε τέτοιο class θα υλοποιήσουμε κάποιες γενικές μεθόδους (που θα υπάρχουν σε κάθε class με το ίδιο όνομα) καθώς και κάποιες ειδικές μεθόδους (π.χ. για να αποφασίσουμε αν ένα σημείο είναι πάνω σε ένα ευθύγραμμο τμήμα).

Επικεφαλίδα του προγράμματος

Στην αρχή του προγράμματος έχουμε κάποιες γραμμές κώδικα:

import numpy as np
import matplotlib.pyplot as plt
import math
plt.axes().set_aspect('equal') # Για ίσα μέτρα στους άξονες

που σκοπό έχουν να φέρουν τις βιβλιοθήκες που θα χρησιμοποιήσουμε. Η τελευταία εντολή είναι εκεί για να εξασφαλίσει ότι όταν σχεδιάσουμε κάτι τότε 1cm στον άξονα των \(x\) ή στον άξονα των \(y\) αντιστοιχεί στις ίδιες μονάδες άξονα. Με άλλα λόγια, για να σχεδιάζεται τετράγωνο και όχι απλά ορθογώνιο όταν εμείς σχεδιάζουμε ένα τετράγωνο.

class Point

Ένα σημείο καθορίζεται από τις \(x\) και \(y\) συντεταγμένες του και αυτές είναι που περνάμε στην __init__ για να δημιουργήσουμε το σημείο. Αυτές οι συνεταγμένες αποθηκεύονται στα πεδία (attributes) self.x και self.y.

Για να δημιουργήσουμε ένα σημείο δίνουμε μια εντολή της μορφής p = Point(2.1, 0.2).

Στη μέθοδο __str__ (η οποία καλείται όταν κάνουμε print p όπου p ένα αντικείμενο τύπου class Point) επιστρέφουμε μια αναπαράσταση του σημείου μας σε μορφή κειμένου.

Στη μέθοδο move, η οποία παίρνει (εκτός από το self) μια παράμετρο v, επίσης τύπου class Point, μεταφέρουμε το σημείο κατά το διάνυσμα v, προσθέτουμε δηλ. στις συντεταγμένες του σημείου τις συντεταγμένες του v.

Για να δώσουμε εντολή στο σημείο p να μεταφερθεί κατά (1, 2.3) π.χ. δίνουμε την εντολή p.move(Point(1, 2.3)).

Για να δώσουμε την εντολή στο σημείο p να στραφεί (με κέντρο την αρχή των αξόνων) κατά μια γωνία theta δίνουμε την εντολή p.turn(theta). Η μέθοδος turn τροποποιεί κατάλληλα τις συντεταγμένες του σημείου. Θυμίζουμε ότι αν στρίψουμε το σημείο με συντεταγμένες \((x, y)\) κατά \(\theta\) αναφορικά με κέντρο την αρχή των αξόνων τότε παίρνουμε το σημείο \[ (\cos{\theta}\cdot x - sin{\theta}\cdot y, \sin{\theta}\cdot x + \cos{\theta}\cdot y). \]

Η μέθοδος draw ζωγραφίζει το σημείο στο επίπεδο. Δίνουμε την εντολή p.draw() για να ζωγραφιστεί το σημείο p.

Η μέθοδος distancefrom παίρνει, εκτός από το self, παράμετρο ένα άλλο σημείο p και επιστρέφει την (Ευκλείδια) απόσταση του self από το p.

Τη μέθοδο isin τη σχολιάζουμε παρακάτω.

class Segment

Ένα ευθύγραμμο τμήμα ορίζεται από δύο σημεία και αυτά περνάμε στη συνάρτηση __init__ που δημιουργεί ένα ευθύγραμμο τμήμα. Για να δημιουργήσουμε ένα ευθύγραμμο τμήμα μπορούμε να δώσουμε μια εντολή της μορφής s = Segment(Point(1, 0), Point(0,1)).

Η μέθοδος __str__ μας ορίζει πώς τυπώνουμε ένα ευθύγραμμο τμήμα.

Μη τη μέθοδο move μεταφέρουμε το ευθύγραμμο τμήμα κατά το διάνυσμα v. Παρατηρείστε ότι για να μεταφέρουμε το ευθύγραμμο τμήμα self απλά μεταφέρουμε τα δύο άκρα του self.a και self.b τα οποία είναι τύπου class Point. Ομοίως για να στρίψουμε το ευθύγραμμό τμήμα κατά γωνία theta (με τη μέθοδο turn) λέμε απλά στα δύο άκρα του να στρίψουν κατά theta καλώντας για το κάθε άκρο τη μέθοδο turn (για σημεία).

Η μέθοδος draw ζωγραφίζει το ευθ. τμήμα self καλώντας κατάλληλα την plot χρησιμοποιώντας τις συντεταγμένες των δύο άκρων.

Τέλος η μέθοδος midpoint επιστρέφει ένα αντικείμενο τύπου class Point το οποίο έχει ως συντεταγμένες αυτές του μέσου του ευθυγράμμου τμήματος self. Έτσι ο κώδικας

p = Point(1,2)
q = Point(3, 10)
s = Segment(p, q)
m = s.midpoint()

αναθέτει το όνομα m σε ένα αντικείμενο τύπου class Point με συντεταγμένες (2, 6).

class Circle

Ένας κύκλος ορίζεται από το κέντρο του (τύπου class Point) και από την ακτίνα του (θετικός αριθμός). Αυτές είναι και οι παράμετροι που περνάμε στην κατασκευάστρια __init__. Τα αντικείμενα αυτά αποθηκεύονται στα self.c και self.r αντίστοιχα.

Η μέθοδος move για τον κύκλο απλά μετακινεί το κέντρο του και αντίστοιχα η μέθοδος turn για τον κύκλο απλά στρίβει το κέντρο του.

Η μέθοδος draw σχεδιάζει τον κύκλο με κέντρο το \((c_x, c_y)\) και ακτίνα \(R>0\) χρησιμοποιώντας την παραμετρική του εξίσωση \[ x(t) = c_x + R \cos{t},\ \ \ y(t) = c_y + R\sin{t}.\ \ \ \ (0\le t\le 2\pi) \]

Η μέθοδος isin του class Point

Με τη μέθοδο isin επιστρέφουμε True ή False ανάλογα με το αν το σημείο self είναι μέσα στο ευθύγραμμο τμήμα s (αν το s που περνάμε είναι ευθύγραμμο τμήμα) ή αν το σημείο self είναι στο εσωτερικό του κύκλου s (αν το s που περνάμε είναι κύκλος). Για αυτό και χρησιμοποιούμε τη μέθοδο isiinstance για να δούμε αν το s είναι τύπου Segment ή τύπου Circle, και ανάλογα κάνουμε διαφορετικό έλεγχο.

Στην περίπτωση που το s είναι κύκλος απλά ελέγχουμε αν η απόσταση (υπολογίζεται με τη μέθοδο distancefrom) του self από το κέντρο του κύκλου είναι μικρότερη ή ίση της ακτίνας του κύκλου.

Στην περίπτωση που το s είναι ευθύγραμμο τμήμα ελέγχουμε αν το άθροισμα των αποστάσεων του self από τα δύο άκρα του ευθυγράμμου τμήματος ισούται με το μήκος του ευθυγράμμου τμήματος αφού τότε και μόνο τότε είναι το σημείο self στο εσωτερικό του ευθυγράμμου τμήματος. Ο έλεγχος μιας ισότητας για πραγματικούς αριθμούς γίνεται πάντα εντός κάποιας ανοχής (tolerance) μια και οι πραγματικοί αριθμοί (floating point numbers) δεν αναπαρίστανται σχεδόν ποτέ ακριβώς στον υπολογιστή.

Το κυρίως πρόγραμμα

Στο κυρίως πρόγραμμα με τις γραμμές

A = Point(0,0); B = Point(1,1); C = Point(2, -0.5)

AB = Segment(A, B); BC = Segment(B, C)

M = AB.midpoint()

K = Circle(B, 0.5)

Δημιουργούνται τα σημεία A, B, C, μέσω αυτών τα ευθ. τμήματα AB, BC, το σημείο M που είναι το μέσο του AB και ο κύκλος K.

Έπειτα με τις γραμμές

if M.isin(K):
    print "OK, in circle"
else:
    print "Not in circle"
    
if M.isin(AB):
    print "OK, in segment"
else:
    print "Not in segment"

δοκιμάζουμε το αν δουλεύει σωστά η μέθοδος isin του class Point.

Στις γραμμές

allpoints = [A, B, C, M]
allobjects = allpoints + [AB, BC, K]

for x in allobjects:
    x.draw()
for x in allpoints:
    x.turn(math.pi/4)
for x in allobjects:
    x.draw()

τοποθετούμε όλα μας τα σημεία στη λίστα allpoints ενώ στη λίστα allobjects τοποθετούνται συνολικά όλα τα αντικείμενα (σημεία, τμήματα και κύκλοι).

Στο πρώτο loop σχεδιάζουμε όλα τα αντικείμενα καλώντας για καθένα από αυτά τη μέθοδο draw.

Στο δεύτερο loop στρίβουμε όλα τα σημεία κατά \(\pi/4\) καλώντας τη μέθοδο turn για καθένα από αυτά.

Στο τρίτο loop ξανασχεδιάζουμε όλα τα αντικείμενα. Παρατηρείστε ότι αν και δε δώσαμε εντολή στα ευθύγραμμα τμήμα και στον κύκλο να περιστραφούν, αυτό έχε συμβεί μια και τα αντικείμενα αυτά έχουν μέσα τους αποθηκευμένες αναφορές σε σημεία και όχι σε συντεταγμένες. Όταν τα σημεία αυτά αλλάξουν για τον οποιοδήποτε λόγο και πάμε να ξανασχεδιάσουμε τα αντικείμενα τότε αυτά θα εμφανιστούν αλλαγμένα.

%matplotlib inline 
# Η προηγούμενη γραμμή είναι περιττή για όσους δεν τρέχουν python στο περιβάλλον ipython
import numpy as np
import matplotlib.pyplot as plt
import math
plt.axes().set_aspect('equal') # Για ίσα μέτρα στους άξονες


class Point:
    
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
    def __str__(self):
        return 'Point({x}, {y})'.format(x=self.x, y=self.y)
    
    def move(self, v):
        self.x += v.x
        self.y += v.y
        
    def turn(self, theta):
        c = math.cos(theta); s = math.sin(theta)
        xx = c*self.x-s*self.y
        yy = s*self.x+c*self.y
        self.x = xx; self.y = yy
    
    def draw(self):
        plt.plot(self.x, self.y, 'bo')
        
    def distancefrom(self, p):
        return math.sqrt((p.x-self.x)**2+(p.y-self.y)**2)
        
    def isin(self, s):
        """ Επιστρέφει True αν και μόνο αν το σημείο self ανήκει στο ευθ. τμήμα s"""
        tolerance=1e-7
        if isinstance(s, Segment):
            rhs = s.a.distancefrom(s.b)
            lhs = s.a.distancefrom(self) + s.b.distancefrom(self)
            return abs(rhs-lhs) < tolerance
        elif isinstance(s, Circle):
            d = self.distancefrom(s.c)
            if d<=s.r:
                return True
            else:
                return False
        else:
            print "Error"
    

class Segment:
    
    def __init__(self, p1, p2):
        self.a = p1
        self.b = p2
        
    def __str__(self):
        return '[Segment from {a} to {b}]'.format(a=self.a, b=self.b)
    
    def move(self, v):
        self.a.move(v)
        self.b.move(v)
        
    def turn(self, theta):
        self.a.turn(theta)
        self.b.turn(theta)
        
    def draw(self):
        plt.plot([self.a.x, self.b.x], [self.a.y, self.b.y], 'r')
        
    def midpoint(self):
        return Point(0.5*(self.a.x+self.b.x), 0.5*(self.a.y+self.b.y))
    
class Circle:
    
    def __init__(self, center, radius):
        self.c = center
        self.r = radius
    
    def __str__(self):
        return '[Circle with center {p} and radius {r}]'.format(p=self.c, r=self.r)
    
    def move(self, v):
        self.c.move(v)
        
    def turn(self, theta):
        self.c.turn(theta)
    
    def draw(self):
        t=np.linspace(0, 2*np.pi, 100)
        x = self.c.x + self.r*np.cos(t)
        y = self.c.y + self.r*np.sin(t)
        plt.plot(x, y, 'g')

A = Point(0,0); B = Point(1,1); C = Point(2, -0.5)

AB = Segment(A, B); BC = Segment(B, C)

M = AB.midpoint()

K = Circle(B, 0.5)

if M.isin(K):
    print "OK, in circle"
else:
    print "Not in circle"
    
if M.isin(AB):
    print "OK, in segment"
else:
    print "Not in segment"

allpoints = [A, B, C, M]
allobjects = allpoints + [AB, BC, K]

for x in allobjects:
    x.draw()
for x in allpoints:
    x.turn(math.pi/4)
for x in allobjects:
    x.draw()

Not in circle
OK, in segment

Ένα φαινόμενο που παρατηρήσαμε και η εξήγησή του

Στο παρακάτω πρόγραμμα έχουμε κρατήσει τις ίδιες ακριβώς class που είχαμε παραπάνω και αλλάξαμε μόνο το κυρίως πρόγραμμα, το οποίο είναι τώρα το παρακάτω:

p = Point(10, 0)
k = Circle(p, 2)

allobjects = [p, k]

N=15
theta = math.pi/N
v=Point(4.5, 2.5)

for i in range(N):
    p.turn(theta)
    p.move(v)
    for x in allobjects:
        x.draw()

Δημιουργούμε ένα σημείο p κι ένα κύκλο k γύρω από αυτό, επιλέγουμε μια γωνία theta (ίση με \(\pi/15\) με τις τιμές που έχουμε δώσει) και ένα διάνυσμα μεταφοράς v κι έπειτα, συνεχώς (για \(N\) φορές) στρίβουμε το σημείο κατά theta γύρω από το σημείο (0,0) και έπειτα το μεταφέρουμε κατά v. Οι δύο αυτές πράξεις επαναλαμβάνονται για \(N\) φορές όπως φαίνεται καθαρά στο loop.

Αυτό που παρατηρούμε είναι ότι οι νέες θέσεις του σημείου p είναι πάνω σε κύκλο. Μάλιστα αν κανείς πειραματιστεί με διαφορετικές τιμές για το \(N\) (από το οποίο καθορίζεται η γωνία theta) και το διάνυσμα μεταφοράς v (κάντε το) παρατηρεί ότι αλλάζει μεν το σχήμα αλλά παραμένει πάντα κύκλος.

Ας το αποδείξουμε λοιπόν αυτό.

Θεώρημα Ας είναι \(x\) ένα σημείο του επιπέδου, \(\theta\) μια γωνία (όχι ακέραιο πολλαπλάσιο του \(2\pi\)) και \(v\) ένα διάνυσμα. Ορίζουμε την ακολουθία σημείων του επιπέδου \[ x_0 = x, \] και \[ x_n = Rx_{n-1} + v,\ \ \ \ (n\ge 1) \] όπου \[ R = \left( \begin{array} \ \cos{\theta} & -\sin\theta\\ \sin\theta & \cos\theta \end{array} \right) \] είναι ο πίνακας που περιστρέφει ένα διάνυσμα (σημείο) του επιπέδου γύρω από την αρχή των αξόνων κατά \(\theta\). Τότε η ακολουθία σημείων \(x_n\) βρίσκεται πάνω σε ένα κύκλο.

Απόδειξη

Έχουμε \[ x_1 = Rx+v, \] \[ x_2 = R^2x+Rv+v \] \[ x_3 = R^3x+R^2v+Rv+v \] κλπ, και για γενικό \(n\) έχουμε εύκολα \[ x_n = R^n x + R^{n-1} v + R^{n-2} v + \cdots + Rv + v. \] Η τελευταία ισότητα γράφεται και ως \[ x_n = R^n x +(I+R+R^2+\cdots+R^{n-1}) v.\ \ \ \ (Ε) \] όπου \(I\) είναι ο \(3 \times 3\) ταυτοτικός πίνακας (που αφήνει αμετάβλητα όλα τα διανύσματα).

Το κλειδί εδώ είναι η ταυτότητα για την πεπερασμένη γεωμετρική πρόοδο \[ 1+a+a^2+a^3+\cdots+a^{n-1} = \frac{1-a^n}{1-a},\ \ \ \ (a \neq 1). \] Βέβαια στη μορφή αυτή η ταυτότητα ισχύει μόνο για αριθμούς \(\neq 1\) και όχι για πίνακες, αλλά εύκολα μπορεί κανείς να δείξει (πολλαπλασιάζοντας και τα δύο μέλη με τον πίνακα \(I-R\) και κάνοντας τις πράξεις στο αριστερό μέλος) ότι η ίδια ουσιαστικά ταυτότητα ισχύει και για κάθε τετράγωνο μη ταυτοτικό πίνακα \(R\) τέτοιο ώστε ο πίνακας \(I-R\) να είναι αντιστρέψιμος. \[ I + R + R^2 + R^3 + \cdots + R^{n-2} + R^{n-1} = (I-R^n) (I-R)^{-1}.\ \ \ \ (*) \] Για την εφαρμογή τη δικιά μας \(R\) είναι ένας πίνακας περιστροφής (όχι ο ταυτοτικός) και ο πίνακας \(I-R\) εύκολα βλέπουμε ότι είναι όντως αντιστρέψιμος. Αν δεν ήταν τότε θα υπήρχε ένα μη μηδενικό διάνυσμα \(w\) τέτοιο ώστε \[ (I-R)w = 0, \] ή, ισοδύναμα, \[ w = Rw, \] πράγμα όμως που είναι αδύνατο να συμβεί αφού κανένα μη μηδενικό διάνυσμα δε μένει αναλλοίωτο αν το περιστρέψουμε κατά \(\theta\) (όταν φυσικά το \(\theta\) δεν είναι ακέραιο πολλαπλάσιο του \(2\pi\)).

Μπορούμε συνεπώς να εφαρμόσουμε την ταυτότητα (*) που βλέπουμε παραπάνω στην εξίωση (Ε) και να πάρουμε \[ x_n = R^n x + (I-R^n)(I-R)^{-1} v = R^n x - R^n (I-R)^{-1}v + (I-R)^{-1} v, \] και θέτοντας \(u = (I-R)^{-1} v\) γράφουμε το ίδιο ως \[ x_n = R^n(x-u) + u, \] ή \[ x_n - u = R^n(x-u), \] και αφού \(\|Ry\| = \|y\|\) για κάθε διάνυσμα \(y\) (ο πίνακας \(R\) της περιστροφής είναι, όπως λέμε, ισομετρία, δεν αλλάζει δηλ. τα μήκη των διανυσμάτων) έπεται ότι \[ \forall n:\ \ \ \| x_n -u\| = \|x-u\|. \] Η απόσταση δηλ. του \(x_n\) από το σταθερό διάνυσμα \(u\) δεν εξαρτάται από το \(n\) και άρα όλα τα \(x_n\) βρίσκονται πάνω στον ίδιο κύκλο με κέντρο το \(u = (I-R)^{-1}v\).

%matplotlib inline 
# Η προηγούμενη γραμμή είναι περιττή για όσους δεν τρέχουν python στο περιβάλλον ipython
import numpy as np
import matplotlib.pyplot as plt
import math
plt.axes().set_aspect('equal') # Για ίσα μέτρα στους άξονες


class Point:
    
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
    def __str__(self):
        return 'Point({x}, {y})'.format(x=self.x, y=self.y)
    
    def move(self, v):
        self.x += v.x
        self.y += v.y
        
    def turn(self, theta):
        c = math.cos(theta); s = math.sin(theta)
        xx = c*self.x-s*self.y
        yy = s*self.x+c*self.y
        self.x = xx; self.y = yy
    
    def draw(self):
        plt.plot(self.x, self.y, 'bo')
        
    def distancefrom(self, p):
        return math.sqrt((p.x-self.x)**2+(p.y-self.y)**2)
        
    def isin(self, s):
        """ Επιστρέφει True αν και μόνο αν το σημείο self ανήκει στο ευθ. τμήμα s"""
        tolerance=1e-7
        if isinstance(s, Segment):
            rhs = s.a.distancefrom(s.b)
            lhs = s.a.distancefrom(self) + s.b.distancefrom(self)
            return abs(rhs-lhs) < tolerance
        elif isinstance(s, Circle):
            d = self.distancefrom(s.c)
            if d<=s.r:
                return True
            else:
                return False
        else:
            print "Error"
    

class Segment:
    
    def __init__(self, p1, p2):
        self.a = p1
        self.b = p2
        
    def __str__(self):
        return '[Segment from {a} to {b}]'.format(a=self.a, b=self.b)
    
    def move(self, v):
        self.a.move(v)
        self.b.move(v)
        
    def turn(self, theta):
        self.a.turn(theta)
        self.b.turn(theta)
        
    def draw(self):
        plt.plot([self.a.x, self.b.x], [self.a.y, self.b.y], 'r')
        
    def midpoint(self):
        return Point(0.5*(self.a.x+self.b.x), 0.5*(self.a.y+self.b.y))
    
class Circle:
    
    def __init__(self, center, radius):
        self.c = center
        self.r = radius
    
    def __str__(self):
        return '[Circle with center {p} and radius {r}]'.format(p=self.c, r=self.r)
    
    def move(self, v):
        self.c.move(v)
        
    def turn(self, theta):
        self.c.turn(theta)
    
    def draw(self):
        t=np.linspace(0, 2*np.pi, 100)
        x = self.c.x + self.r*np.cos(t)
        y = self.c.y + self.r*np.sin(t)
        plt.plot(x, y, 'g')

        
p = Point(10, 0)
k = Circle(p, 2)

allobjects = [p, k]

N=15
theta = math.pi/N
v=Point(4.5, 2.5)

for i in range(N):
    p.turn(theta)
    p.move(v)
    for x in allobjects:
        x.draw()