You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
299 lines
10 KiB
299 lines
10 KiB
# coding: utf-8
|
|
|
|
import sys
|
|
import math
|
|
|
|
|
|
def distanceAuCarre(v1, v2):
|
|
dx = (v1.x() - v2.x())
|
|
dy = (v1.y() - v2.y())
|
|
return dx**2 + dy**2
|
|
|
|
|
|
def conditionDeDelaunay(A, B, C, D):
|
|
dab2 = distanceAuCarre(A, B)
|
|
dad2 = distanceAuCarre(A, D)
|
|
dbc2 = distanceAuCarre(B, C)
|
|
dbd2 = distanceAuCarre(B, D)
|
|
dcd2 = distanceAuCarre(C, D)
|
|
cosa = (dab2 + dad2 - dbd2) / (2 * math.sqrt(dab2) * math.sqrt(dad2))
|
|
cosc = (dbc2 + dcd2 - dbd2) / (2 * math.sqrt(dbc2) * math.sqrt(dcd2))
|
|
sina2 = 1. - cosa * cosa
|
|
if(sina2 > 0.):
|
|
sina = math.sqrt(sina2)
|
|
else:
|
|
sina = 0.
|
|
sinc2 = 1. - cosc * cosc
|
|
if(sinc2 > 0.):
|
|
sinc = math.sqrt(sinc2)
|
|
else:
|
|
sinc = 0.
|
|
return sina * cosc + cosa * sinc >= 0
|
|
|
|
|
|
class Triangulation:
|
|
|
|
class QuadEdge:
|
|
'''Classe définissant un quad-edge : une arête connectée à deux faces et deux sommets'''
|
|
|
|
def __init__(self, f1, f2, v1, v2):
|
|
self.f1 = f1
|
|
self.f2 = f2
|
|
self.v1 = v1
|
|
self.v2 = v2
|
|
|
|
def __eq__(self, e):
|
|
'''Méthode qui teste si deux quad-edges ont même extrémités'''
|
|
if((self.v1 == e.v1) and (self.v2 == e.v2)):
|
|
return True
|
|
elif((self.v1 == e.v2) and (self.v2 == e.v1)):
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
def __str__(self):
|
|
return str(self.v1) + " - " + str(self.v2)
|
|
|
|
def remplaceFace(self, ancienneFace, nouvelleFace):
|
|
'''Méthode qui remplace une face adjacente au quad-edge par une autre'''
|
|
if(self.f1 == ancienneFace):
|
|
self.f1 = nouvelleFace
|
|
else:
|
|
self.f2 = nouvelleFace
|
|
|
|
def lanceAlgorithme(self):
|
|
# Construit la triangulation initiale. Complexité en O(n log(n))
|
|
self.construitTriangulationInitiale()
|
|
|
|
# Bascule les arêtes de la triangulation jusqu'à obtenir la triangulation de Delaunay
|
|
self.basculeAretes()
|
|
|
|
# Efface les sommets à l'infini
|
|
for _ in range(3):
|
|
self.graphe.sommets.pop()
|
|
|
|
def __init__(self, g):
|
|
'''Constructeur de la classe triangulation qui prend en entrée un nuage de points
|
|
et crée une triangulation de Delaunay'''
|
|
self.racine = None
|
|
self.quadEdges = []
|
|
self.graphe = g
|
|
self.lanceAlgorithme()
|
|
|
|
class Triangle:
|
|
def __init__(self, v1, v2, v3):
|
|
self.v1 = v1
|
|
self.v2 = v2
|
|
self.v3 = v3
|
|
self.t12 = None
|
|
self.t13 = None
|
|
self.t23 = None
|
|
self.e12 = None
|
|
self.e13 = None
|
|
self.e23 = None
|
|
|
|
def contient(self, v):
|
|
''' Méthode qui teste si un sommet est à l'intérieur d'un triangle'''
|
|
v1 = self.v1
|
|
v2 = self.v2
|
|
v3 = self.v3
|
|
det = (v1.x() - v3.x()) * (v2.y() - v3.y()) - \
|
|
(v1.y() - v3.y()) * (v2.x() - v3.x())
|
|
c1 = ((v2.y() - v3.y()) * (v.x() - v3.x()) +
|
|
(v3.x() - v2.x()) * (v.y() - v3.y())) * det
|
|
c2 = ((v3.y() - v1.y()) * (v.x() - v3.x()) +
|
|
(v1.x() - v3.x()) * (v.y() - v3.y())) * det
|
|
return (c1 > 0) and (c2 > 0) and (c1 + c2 < det * det)
|
|
|
|
def trouve(self, v):
|
|
'''Méthode récursive qui renvoie le triangle d'une triangulation qui contient un sommet.
|
|
Renvoie le triangle contenant v, None si v n'est pas dans la triangulation'''
|
|
|
|
t12 = self.t12
|
|
t13 = self.t13
|
|
t23 = self.t23
|
|
if(t12 == None):
|
|
return self
|
|
else:
|
|
if(t12.contient(v)):
|
|
return t12.trouve(v)
|
|
elif(t13.contient(v)):
|
|
return t13.trouve(v)
|
|
elif(t23.contient(v)):
|
|
return t23.trouve(v)
|
|
else:
|
|
return None
|
|
|
|
def aPourSommet(self, v):
|
|
'''Méthode qui teste si un sommet est un sommet d'un triangle
|
|
Renvoie vrai si v est un sommet du triangle'''
|
|
return self.v1 == v or self.v2 == v or self.v3 == v
|
|
|
|
def troisiemeSommet(self, a, b):
|
|
''' Renvoie le troisième sommet d'un triangle à partir des deux autres'''
|
|
|
|
if(self.v1 != a and self.v1 != b):
|
|
return self.v1
|
|
elif(self.v2 != a and self.v2 != b):
|
|
return self.v2
|
|
else:
|
|
return self.v3
|
|
|
|
def remplaceSommet(self, ancienSommet, nouveauSommet):
|
|
''' Méthode qui substitue un sommet par un autre dans un triangle '''
|
|
if(self.v1 == ancienSommet):
|
|
self.v1 = nouveauSommet
|
|
elif(self.v2 == ancienSommet):
|
|
self.v2 = nouveauSommet
|
|
elif(self.v3 == ancienSommet):
|
|
self.v3 = nouveauSommet
|
|
else:
|
|
raise Exception("Bad vertex" + ancienSommet)
|
|
|
|
def retrouveArete(self, v1, v2):
|
|
'''Méthode qui renvoie le quad-edge d'un triangle ayant deux sommets pour extrêmités'''
|
|
e = Triangulation.QuadEdge(None, None, v1, v2)
|
|
if(self.e12 == e):
|
|
return self.e12
|
|
elif(self.e13 == e):
|
|
return self.e13
|
|
elif(self.e23 == e):
|
|
return self.e23
|
|
else:
|
|
raise Exception("getEdge")
|
|
|
|
def remplaceArete(self, ancienneArete, nouvelleArete):
|
|
'''Méthode qui substitue le quad-edge d'un triangle par un autre'''
|
|
if(self.e12 == ancienneArete):
|
|
self.e12 = nouvelleArete
|
|
elif(self.e13 == ancienneArete):
|
|
self.e13 = nouvelleArete
|
|
elif(self.e23 == ancienneArete):
|
|
self.e23 = nouvelleArete
|
|
else:
|
|
raise Exception("changeEdge")
|
|
|
|
def construitTriangleInitial(self):
|
|
'''Méthode qui construit une triangulation initiale qui contient tous les sommets'''
|
|
xmin = sys.float_info.max
|
|
xmax = sys.float_info.min
|
|
ymin = sys.float_info.max
|
|
ymax = sys.float_info.min
|
|
|
|
for v in self.graphe.sommets:
|
|
if(v.x() > xmax):
|
|
xmax = v.x()
|
|
if(v.x() < xmin):
|
|
xmin = v.x()
|
|
if(v.y() > ymax):
|
|
ymax = v.y()
|
|
if(v.y() < ymin):
|
|
ymin = v.y()
|
|
|
|
largeur = xmax - xmin
|
|
hauteur = ymax - ymin
|
|
margex = 0.1 * largeur
|
|
margey = 0.1 * hauteur
|
|
|
|
v1 = self.graphe.ajouteSommet(
|
|
xmin - largeur / 2 - margex, ymin - margey)
|
|
v2 = self.graphe.ajouteSommet(
|
|
xmax + largeur / 2 + margex, ymin - margey)
|
|
v3 = self.graphe.ajouteSommet(
|
|
(xmin + xmax) / 2, ymax + hauteur + margey)
|
|
|
|
self.racine = Triangulation.Triangle(v1, v2, v3)
|
|
|
|
e12 = Triangulation.QuadEdge(None, self.racine, v1, v2)
|
|
e13 = Triangulation.QuadEdge(None, self.racine, v1, v3)
|
|
e23 = Triangulation.QuadEdge(None, self.racine, v2, v3)
|
|
self.racine.e12 = e12
|
|
self.racine.e13 = e13
|
|
self.racine.e23 = e23
|
|
|
|
def supprimeAretes(self):
|
|
for s in self.graphe.sommets:
|
|
s.aretes.clear()
|
|
|
|
def construitTriangulationInitiale(self):
|
|
self.quadEdges = []
|
|
self.construitTriangleInitial()
|
|
|
|
for v in self.graphe.sommets:
|
|
t = self.racine.trouve(v)
|
|
if(t != None):
|
|
t.t12 = Triangulation.Triangle(t.v1, t.v2, v)
|
|
t.t13 = Triangulation.Triangle(t.v1, t.v3, v)
|
|
t.t23 = Triangulation.Triangle(t.v2, t.v3, v)
|
|
|
|
e1v = Triangulation.QuadEdge(t.t12, t.t13, t.v1, v)
|
|
e2v = Triangulation.QuadEdge(t.t12, t.t23, t.v2, v)
|
|
e3v = Triangulation.QuadEdge(t.t13, t.t23, t.v3, v)
|
|
self.quadEdges.append(e1v)
|
|
self.quadEdges.append(e2v)
|
|
self.quadEdges.append(e3v)
|
|
|
|
t.t12.e12 = t.e12
|
|
t.e12.remplaceFace(t, t.t12)
|
|
t.t12.e13 = e1v
|
|
t.t12.e23 = e2v
|
|
|
|
t.t13.e12 = t.e13
|
|
t.e13.remplaceFace(t, t.t13)
|
|
t.t13.e13 = e1v
|
|
t.t13.e23 = e3v
|
|
|
|
t.t23.e12 = t.e23
|
|
t.e23.remplaceFace(t, t.t23)
|
|
t.t23.e13 = e2v
|
|
t.t23.e23 = e3v
|
|
|
|
def basculeAretes(self):
|
|
pile = []
|
|
for qe in self.quadEdges:
|
|
pile.append(qe)
|
|
|
|
while(len(pile) > 0):
|
|
e = pile.pop()
|
|
|
|
f1 = e.f1
|
|
f2 = e.f2
|
|
if(f1 != None and f2 != None):
|
|
v1 = e.v1
|
|
v2 = e.v2
|
|
|
|
v3 = f1.troisiemeSommet(v1, v2)
|
|
v4 = f2.troisiemeSommet(v1, v2)
|
|
|
|
if(not conditionDeDelaunay(v3, v1, v4, v2)):
|
|
v1v3 = f1.retrouveArete(v1, v3)
|
|
v2v3 = f1.retrouveArete(v2, v3)
|
|
v1v4 = f2.retrouveArete(v1, v4)
|
|
v2v4 = f2.retrouveArete(v2, v4)
|
|
f1.remplaceArete(v2v3, v1v4)
|
|
f2.remplaceArete(v1v4, v2v3)
|
|
v2v3.remplaceFace(f1, f2)
|
|
v1v4.remplaceFace(f2, f1)
|
|
f1.remplaceSommet(v2, v4)
|
|
f2.remplaceSommet(v1, v3)
|
|
e.v1 = v3
|
|
e.v2 = v4
|
|
pile.append(v1v3)
|
|
pile.append(v2v3)
|
|
pile.append(v1v4)
|
|
pile.append(v2v4)
|
|
|
|
def construitGrapheDeSortie(self, selectionneArete):
|
|
'''Méthode qui construit la triangulation de Delaunay à partir du nuage de points passé au constructeur'''
|
|
|
|
# Sélectionne les arêtes
|
|
graphe = self.graphe
|
|
racine = self.racine
|
|
for qe in self.quadEdges:
|
|
v1 = qe.v1
|
|
v2 = qe.v2
|
|
if(not (racine.aPourSommet(v1) or racine.aPourSommet(v2))):
|
|
v3 = qe.f1.troisiemeSommet(v1, v2)
|
|
v4 = qe.f2.troisiemeSommet(v1, v2)
|
|
selectionneArete(graphe, v1, v2, v3, v4)
|
|
return self.graphe
|
|
|