Created
December 4, 2017 10:11
-
-
Save AmiZya/18fb7bf705cd52275359ad881cf04af5 to your computer and use it in GitHub Desktop.
Graham scan implementation in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import random | |
| import tkinter as tk | |
| class EnveloppeConvexe: | |
| def __init__(self, points): | |
| self.pts = sorted(points) | |
| def teste(self, p, q, r): | |
| """teste si p->q->r est un virage à gauche""" | |
| sum1 = q[0] * r[1] + p[0] * q[1] + r[0] * p[1] | |
| sum2 = q[0] * p[1] + r[0] * q[1] + p[0] * r[1] | |
| if sum1 == sum2: | |
| raise RuntimeError("Points alignes") | |
| return sum1 < sum2 | |
| def tourne_a_gauche(self, i, j, k): | |
| """même chose avec les numéros des points""" | |
| return self.teste(self.pts[i], self.pts[j], self.pts[k]) | |
| def enveloppe(self): | |
| """ retourne la liste des sommets de l'enveloppe | |
| convexe dans le sens trigonométrique""" | |
| pass | |
| return conv | |
| def triangulation(self): | |
| """ retourne une liste d'arêtes d'une triangulation""" | |
| pass | |
| return aretes | |
| def au_hasard(self, numPoints=10, sqrLength=600): | |
| min, max = 0, sqrLength | |
| self.pts = [] | |
| for i in range(numPoints): | |
| rand = random.randint | |
| x = rand(min + 1, max - 1) | |
| y = rand(min + 1, max - 1) | |
| self.pts.append((x, y)) | |
| self.pts.sort() | |
| return self.pts | |
| def lireFichier(self, file): | |
| self.pts = [] | |
| with open(file, 'r') as f: | |
| for line in f: | |
| coords = line.split(',') | |
| self.pts.append((int(coords[0].strip()), int(coords[1].strip()))) | |
| self.pts.sort() | |
| return self.pts | |
| class Affichage: | |
| @staticmethod | |
| def convexe(p, c, boxsize, ptsize=3): | |
| root = tk.Tk() | |
| pass | |
| @staticmethod | |
| def triangulation(p, t, boxsize, ptsize=3): | |
| root = tk.Tk() | |
| pass | |
| e = EnveloppeConvexe([]) | |
| p = e.lireFichier('points.txt') | |
| c = e.enveloppe() | |
| # p = e.pts | |
| Affichage.convexe(p, c, 600) | |
| t = e.triangulation() | |
| Affichage.triangulation(p, t, 600) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment