import Tkinter
import numpy as np
class cpunto2D:
    def __init__(self, x, y):
        self.x=x                  # Coordenadas del punto en unidades de pantalla
        self.y=y
class cborde2D:
    def __init__(self,e,f):
        self.e=e
        self.f=f
class celemento2D:
    def __init__(self,b,r,t,l):
        self.b=b
        self.r=r
        self.t=t
        self.l=l

class triang2D:
    def __init__(self,p0,p1,p2):
        self.p0=p0
        self.p1=p1
        self.p2=p2
#    def muestra(self):
#        print("muestra triang",self.p0.x,self.p0.y,"-",self.p1.x,self.p1.y,"-",self.p2.x,self.p2.y)


def prod_cru(p1,p2,p3):
    # p1 y p2 son extremos de dos vectores con origen en p3
    # si devuelve >0 p1 va hacia p2 en sentido antihorario
    # si devuelve <0 p1 va a p2 en sentido horario
    x1=p1.x-p3.x
    y1=p1.y-p3.y
    x2=p2.x-p3.x
    y2=p2.y-p3.y
    if x1*y2-x2*y1>0. :
        return bool(1)
    else:
        return bool(0)        
        

class triang2D:
    def __init__(self,p0,p1,p2):
        self.p0=p0
        self.p1=p1
        self.p2=p2
#    def muestra(self):
#        print("muestra triang",self.p0.x,self.p0.y,"-",self.p1.x,self.p1.y,"-",self.p2.x,self.p2.y)


def prod_cru(p1,p2,p3):
    # p1 y p2 son extremos de dos vectores con origen en p3
    # si devuelve >0 p1 va hacia p2 en sentido antihorario
    # si devuelve <0 p1 va a p2 en sentido horario
    x1=p1.x-p3.x
    y1=p1.y-p3.y
    x2=p2.x-p3.x
    y2=p2.y-p3.y
    if x1*y2-x2*y1>0. :
        return bool(1)
    else:
        return bool(0)        
        
def dibuja_tri(t):
    lienzo.create_oval(g2px(t.p0.x-tama),g2py(t.p0.y-tama),g2px(t.p0.x+tama),g2py(t.p0.y+tama),fill="red")
    lienzo.create_oval(g2px(t.p1.x-tama),g2py(t.p1.y-tama),g2px(t.p1.x+tama),g2py(t.p1.y+tama),fill="red")
    lienzo.create_oval(g2px(t.p2.x-tama),g2py(t.p2.y-tama),g2px(t.p2.x+tama),g2py(t.p2.y+tama),fill="red")
    lienzo.create_line(g2px(t.p0.x),g2py(t.p0.y),g2px(t.p1.x),g2py(t.p1.y),fill="blue")
    lienzo.create_line(g2px(t.p1.x),g2py(t.p1.y),g2px(t.p2.x),g2py(t.p2.y),fill="blue")
    lienzo.create_line(g2px(t.p2.x),g2py(t.p2.y),g2px(t.p0.x),g2py(t.p0.y),fill="blue")
    return

def dibuja_pol(p):
    # dibuja poligono solo para desarrollo
    return
    for i in range(len(p)):
        print("pae",len(p),p[i].e.x,p[i].e.y,p[i].f.x,p[i].f.y)
        lienzo.create_line(g2px(p[i].e.x),g2py(p[i].e.y),g2px(p[i].f.x),g2py(p[i].f.y),fill="red")
    return

def dibuja(p):
    #dibuja puntos
    tama=.1
    for i in range(len(p)):
        lienzo.create_oval(g2px(p[i].x-tama),g2py(p[i].y-tama),g2px(p[i].x+tama),g2py(p[i].y+tama),fill="red")
    return

# defino variables globales
w_max=300.0     # ancho de ventana
h_max=300.0     # alto de ventana

x_min=0.0    #rango de las x
x_max=40.0
y_min=0.0    #rango de las y
y_max=40.0

tama=.2     #tamano de punto

div_x=8     #cantidad divisiones en x
div_y=5     # cantidad divisiones en y


def g2px(w,x_min=x_min,x_max=x_max,w_max=w_max):
    # transforma la coorde x de geometria 
# al dominio w_max (eje horizontal de pantalla)
# al poner por ejemplo x_min=x_min estoy usando variable global para pasar
# como argumento
        d=int((w-x_min)/(x_max-x_min)*w_max)
        return d


def g2py(w,y_min=y_min,y_max=y_max,h_max=h_max):
    # transforma la coorde y de geometria 
# al dominio h_max (eje vertical de pantalla)
# al poner por ejemplo x_min=x_min estoy usando variable global para pasar
# como argumento
        d=h_max-int((w-y_min)/(y_max-y_min)*h_max)

        return d



def puntea(ld,lr,lu,ll,i,j):
    global nodo
    xx=(lr[j].x-ll[j].x)/div_x*i+ll[j].x
    yy=(lu[i].y-ld[i].y)/div_y*j+ld[i].y
    nodo=nodo+1
    lienzo.create_oval(g2px(xx-tama),g2py(yy-tama),g2px(xx+tama),g2py(yy+tama),fill="blue")
    return xx,yy
        

def lineal(p1,p2,px):
    # devuelve coordenada en y para un punto px sobre recta que pasa por p1 y p2
    y=(x-p1.x)/(p2.x-p1.x)*(p2.y-p1.y)+p1.y
    return y
    
def lineal_lista(p1,p2,div):
    # devuelve una lista en z para una recta que pasa por p1 y p2 y se divide en div divisiones
    inc_x=(p2.x-p1.x)/div
    inc_y=(p2.y-p1.y)/div
    z=[]
    for i in range(div):
        z.append(cpunto2D(p1.x+i*inc_x,p1.y+i*inc_y))
    return z

def cuadra(p1,p2,p3,px):
    return
    # devuelve coordenada en y para un punto px sobre parabola que pasa por p1, p2 y p3
    a=np.array([[p1.x**2,p1.x,1],[p2.x**2,p2.x,1],[p3.x**2,p3.x,1]])
    b=np.array([p1.y,p2.y,p3.y])
    k=np.linalg.solve(a,b)
    c=k.tolist()
    y=c[0]*px**2+c[1]*x+c[2]
    return y
    
def cuadra_lista(p1,p2,p3,div,parametro):
    # devuelve lista de coordenada segun parametro
    # "v"  parabola vertical p1 y p2 son extremos y p3 el punto intermedio
    # "h"  parabola horizontal p1 y p2 son extremos y p3 el punto intermedio
    

    if parametro=="v":
        print("paso")
        a=np.array([[p1.x**2,p1.x,1],[p2.x**2,p2.x,1],[p3.x**2,p3.x,1]])
        b=np.array([p1.y,p2.y,p3.y])
        k=np.linalg.solve(a,b)
        c=k.tolist()
        inc_x=(p2.x-p1.x)/div
        z=[]
        for i in range(div):
            px=p1.x+i*inc_x
            py=c[0]*px**2+c[1]*px+c[2]
            z.append(cpunto2D(px,py))
    elif parametro=="h":
        a=np.array([[p1.y**2,p1.y,1],[p2.y**2,p2.y,1],[p3.y**2,p3.y,1]])
        b=np.array([p1.x,p2.x,p3.x])
        print(a)
        print(b)
        k=np.linalg.solve(a,b)
        c=k.tolist()
        
        inc_y=abs((p2.y-p1.y)/div)
        z=[]
        for i in range(div):
            if p2.y > p1.y:
                py=p1.y+i*inc_y
            else:
                py=p2.y+i*inc_y
            px=c[0]*py**2+c[1]*py+c[2]
            z.append(cpunto2D(px,py)) 
    else:
        print("error")
        exit()
        
    return z
    
def IsInCircumcircleOf(t,pp):
        # extraido de simple_delaunay.py de Vignesh Rajendiran
        a_x = t.p0.x
        a_y = t.p0.y

        b_x = t.p1.x
        b_y = t.p1.y

        c_x = t.p2.x
        c_y = t.p2.y

        # The point coordinates

        d_x = pp.x
        d_y = pp.y

        # If the following determinant is greater than zero then point lies inside circumcircle
        incircle = np.array([[a_x - d_x, a_y - d_y, (a_x - d_x) ** 2 + (a_y - d_y) ** 2],
                             [b_x - d_x, b_y - d_y, (b_x - d_x) ** 2 + (b_y - d_y) ** 2],
                             [c_x - d_x, c_y - d_y, (c_x - d_x) ** 2 + (c_y - d_y) ** 2]])

        if np.linalg.det(incircle) > 0:
            return True
        else:
            return False

def delaunay(pun):
    #definicion de super triangulo
#tres puntos extremos del supertriangulo que luego se retira
# debe contener a todos los puntos
    p=[]
#busco los limites del supertriangulo

    x_max=pun[0].x
    x_min=pun[0].x
    y_max=pun[0].y
    y_min=pun[0].y
    sup_tri=[]
    for punto in pun:
        if punto.x>x_max:
            x_max=punto.x
        if punto.x<x_min:
            x_min=punto.x
        if punto.y>y_max:
            y_max=punto.y
        if punto.y<y_min:
            y_min=punto.y

# a es la base de un rectangulo que contiene a todos los puntos
# b es la altura del mismo        
    a=x_max-x_min
    b=y_max-y_min

# el vertice inferior izquierdo del super es el minimo menos la altura del rectangulo
    p.append(cpunto2D(x_min-b,y_min-1))
# el vertice inferior derecho del super es el minimo menos la altura del rectangulo
    p.append(cpunto2D(x_max+b,y_min-1))
# el vertice suerior del super es el medio de la base y de altura tiene del rectangulo mas media base
    p.append(cpunto2D(x_min+a/2,y_max+a/2+1))

# defino una lista con los triangulos de la triangulacion
    tri=[]
# agrego el supertrianguloa a la lista

    tri.append(triang2D(p[0],p[1],p[2]))
    
# para todos los puntos internos
    for i in pun:
        badtri=[]
    # me fijo si el punto esta dentro de un todos los triangulos que estan en triang
        for j in tri:
#        print("****************************************")
#        print("punto",pun.index(i),"triang",tri.index(j))
#        print("****************************************")
#        j.muestra()
            if IsInCircumcircleOf(j,i):
            # si esta adentro de algun triangulo, a ese triangulo lo pongo en la lista de badtriang
                badtri.append(j)
#            print("punto",pun.index(i)," adentro triangulo ",tri.index(j),IsInCircumcircleOf(j,i))
        poligono=[]
    # recorro toda la lista de badtriang buscando cuales lados de cada uno
    # son compratidoc con otro
        for l in badtri:
        # elijo un triangulo de bartriang
            compartido01=0
            compartido12=0
            compartido02=0
            for k in badtri:
            # lo comparo con todos los demas sacando la comparacion con el mismo
                if l!=k:
                # ojo que los lados que estan nominados por los vertices p0,p1 y p2, 
                # en otro triangulo pueden ser los mismos pero estar en otro orden
                # por eso tantas verificaciones
                # las combinacione sposibles son:
                #   los dos primeros los extremos del badtri l
                #   los dos segundos los extremos del badtri k
                #   01      01
                #           10
                #           02
                #           20
                #           12
                #           21
                #   02      01
                #           10
                #           02
                #           20
                #           12
                #           21
                #   12      01
                #           10
                #           02
                #           20
                #           12
                #           21
                
                    if l.p0==k.p0 and l.p1==k.p1:
                        compartido01=1
                    if l.p0==k.p1 and l.p1==k.p0:
                        compartido01=1
                    if l.p0==k.p0 and l.p1==k.p2:
                        compartido01=1
                    if l.p0==k.p2 and l.p1==k.p0:
                        compartido01=1
                    if l.p0==k.p1 and l.p1==k.p2:
                        compartido01=1
                    if l.p0==k.p2 and l.p1==k.p1:
                        compartido01=1    
                 
                 
                    if l.p0==k.p0 and l.p2==k.p1:
                        compartido02=1
                    if l.p0==k.p1 and l.p2==k.p0:
                        compartido02=1
                    if l.p0==k.p0 and l.p2==k.p2:
                        compartido02=1
                    if l.p0==k.p2 and l.p2==k.p0:
                        compartido02=1
                    if l.p0==k.p1 and l.p2==k.p2:
                        compartido02=1
                    if l.p0==k.p2 and l.p2==k.p1:
                        compartido02=1  
                    
                    if l.p1==k.p0 and l.p2==k.p1:
                        compartido12=1
                    if l.p1==k.p1 and l.p2==k.p0:
                        compartido12=1
                    if l.p1==k.p0 and l.p2==k.p2:
                        compartido12=1
                    if l.p1==k.p2 and l.p2==k.p0:
                        compartido12=1
                    if l.p1==k.p1 and l.p2==k.p2:
                        compartido12=1
                    if l.p1==k.p2 and l.p2==k.p1:
                        compartido12=1      
                    
                    
        # ahora busco los lados que no estan compartidos
        # y con ellos armo un poligono
            if compartido01==0:
                poligono.append(cborde2D(l.p0,l.p1))
            if compartido12==0:
                poligono.append(cborde2D(l.p1,l.p2))
            if compartido02==0:
                poligono.append(cborde2D(l.p2,l.p0))
#        print("poli",len(poligono))
#        print("badtri",len(badtri))
        
    # remuevo de tri los badtri
        for l in badtri:
#        print("====triangulos===============")
#        for r in tri:
#            r.muestra()
#        print("----badtri---")
    #l.muestra()
#        print("borro",tri.index(l),"===================")
            
            tri.remove(l)
#        print("largo de tri despues de remover",len(tri))
    # ahora parado en el punto que estoy analizando en el bucle mas externo
    # armo triangulos en triang tomando el punto como vertice y los extremos de cada segmento
    # como los otros vertices
        for ip in poligono:
        # armo los triangulos cuidando de que sea en sentido antihorario
            if prod_cru(ip.e,ip.f,i):
                tri.append(triang2D(i,ip.e,ip.f))
            else:
                tri.append(triang2D(i,ip.f,ip.e))    
#        print("estoy agregando triangulos desde poligono",len(tri))
        dibuja_pol(poligono)

#aca recorro los triangulos viendo si tiene vertices del supertriangulo
# si los tiene los saco.
# no puedo usar el remove porque al sacarlos me cambia los punteros
# y como esta dentro de un for
    tri_borrar=[]
    tri_salida=[]
    for i in tri:
    
#    print("====triangulos===============")
#    for r in tri:
#        r.muestra()
#    print("==FIN ==triangulos===============")
        tri_borrar.append(0)
        for h in p:
            if i.p0 ==h or i.p1==h or i.p2==h:
#            print("marco super",tri.index(i))
                tri_borrar[-1]=1
    tri_salida=[]
    for i in tri:
        if tri_borrar[tri.index(i)]==0:
            dibuja_tri(i)
            tri_salida.append(i)
    return tri_salida


###############################
#  este es el cuerpo del programa
#####################################


#definicion de boerdes extremos
p=[]
#cuatro puntos extremos
p.append(cpunto2D(10.,10.))    # abajo izquierda
p.append(cpunto2D(20.,15.))     # abajo derecha
p.append(cpunto2D(25.,25.))     #arriba derecha
p.append(cpunto2D(10.,20.))     # arriba izquierda
#puntos intermedios para cuadraticos
p.append(cpunto2D(15.,35.))     # medi de arriba
p.append(cpunto2D(15.,10.))     # medio de abajo
p.append(cpunto2D(12.,15.))      # medio izquierda



#borde inferior
cd=cuadra_lista(p[0],p[1],p[5],div_x,"v")    
for i in range(len(cd)):
    print(cd[i].x,cd[i].y)
print()

#borde derecho
cr=lineal_lista(p[1],p[2],div_y)
for i in range(len(cr)):
    print(cr[i].x,cr[i].y)
print()

#borde superior
cu=cuadra_lista(p[2],p[3],p[4],div_x,"v")
for i in range(len(cu)):
    print(cu[i].x,cu[i].y)
print()

#borde izquierdo
#cl=lineal_lista(p[3],p[0],div_y)
cl=cuadra_lista(p[3],p[0],p[6],div_y,"h")
for i in range(len(cl)):
    print(cl[i].x,cl[i].y)
print()

# pantalla de trabajo
w = Tkinter.Tk()
w.title("malla")
lienzo = Tkinter.Canvas(w, height=h_max, width=w_max, background="white",relief="sunken",borderwidth=1)
lienzo.grid(row=0,column=0,columnspan=4,rowspan=4) 


f=open("malla2.txt","w")
v=[]            # vertices
b=[]            # bordes
ee=[]            # elementos
nodo=0
for j in range(len(cl)):
    for i in range(len(cd)):
    
        #print("---",i,j,len(cd),len(cl))
        xx,yy=puntea(cd,cr,cu,cl,i,j)
        f.write("v,"+str(nodo)+","+str(xx)+","+str(yy)+chr(10))
        v.append(cpunto2D(xx,yy))


# dibuja los puntoa a triangular
dibuja(v)

tri_sal=delaunay(v)

for i in range(len(tri_sal)):
    dibuja_tri(tri_sal[i])
    f.write("e,"+str(i)+","+str(v.index(tri_sal[i].p0))+","+str(v.index(tri_sal[i].p1))+","+str(v.index(tri_sal[i].p2))+chr(10))
f.close()
w.mainloop()
exit()