#!/usr/bin/env python
#coding=utf-8

# Algoritmo de Khuller e Matias para obtencao do par de pontos mais proximos
# Implementado por Guilherme Fonseca
# para o 26 Coloquio Brasileiro de Matematica, IMPA, Brasil.
# 
# Eu, Guilherme Fonseca, coloco este codigo em dominio publico. 07/07/2007
# This code is hereby placed in the public domain.

from __future__ import division   # Divisao de ponto flutuante
from Tkinter import *
from random import *
from math import *

# Largura e altura do canvas
tamanho = 600

# Inicializa janela Tkinter
raiz = Tk()
raiz.wm_title("Par de Pontos Mais Próximos")
texto = StringVar()
label = Label(raiz, textvariable=texto, font=("Helvetica",14))
label.pack()
canvas = Canvas(raiz, width=tamanho, height=tamanho)
canvas.pack()
button = Button(raiz, text="Continuar", command=raiz.quit)
button.pack()

def desenhaPonto(p, fill="blue"):
    canvas.create_oval((tamanho*p[0])-5, (tamanho*p[1])-5, (tamanho*p[0])+5, (tamanho*p[1])+5, fill=fill)

def riscaPonto(p, fill="red"):
    canvas.create_line((tamanho*p[0])-10, (tamanho*p[1])-10, (tamanho*p[0])+10, (tamanho*p[1])+10, fill=fill, width=2)
    canvas.create_line((tamanho*p[0])+10, (tamanho*p[1])-10, (tamanho*p[0])-10, (tamanho*p[1])+10, fill=fill, width=2)

def desenhaQuadriculado(k):
    x = 0
    while x<1:
        x += k
        canvas.create_line(tamanho*x, 0, tamanho*x, tamanho, fill="black", width=1, tag="quad")
        canvas.create_line(0, tamanho*x, tamanho, tamanho*x, fill="black", width=1, tag="quad")

def removeQuadriculado():
    canvas.delete("quad")

espera = raiz.mainloop

def lerPontos():
    """ Retorna uma lista de pontos.
        Cada ponto e' uma dupla de floats entre 0 e 1 """
    P = []
    def novoPonto(evento):
        P.append((evento.x/tamanho, evento.y/tamanho))
        desenhaPonto(P[-1])
    canvas.bind("<Button-1>", novoPonto)
    texto.set("Clique pela janela para criar pontos. Em seguida clique Continuar.")
    espera()
    canvas.unbind("<Button-1>")
    return P

def dist(p,q):
    """Distancia Euclidiana"""
    return sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2)

def vmp(P, p):
    """Vizinho mais proximo de p em P"""
    minDist = 10e10    # Infinito
    min_p = None
    for q in P:
        if q != p and dist(p,q) <= minDist:
            minDist = dist(p,q)
            min_p = q
    return min_p

def adjacencia(celula):
    """Lista de 9 celulas adjacentes"""
    x,y = celula
    return [(x+xd,y+yd) for xd in [-1,0,1] for yd in [-1,0,1]]

def removerPontos(P, fp):
    """Descricao no texto do curso"""
    def c(p):
        l = fp/(2*sqrt(2))
        return (int(p[0]/l),int(p[1]/l))

    desenhaQuadriculado(fp/(2*sqrt(2)))
    texto.set("Criado quadriculado com diagonal f(p)/2.")
    espera()

    P2 = []
    v = {}
    for q in P:
        v[c(q)] = v.get(c(q),0) + 1
    for q in P:
        remover = True
        for celula in adjacencia(c(q)):
            if ((celula == c(q) and v.get(celula,0)>=2) or
                (celula != c(q) and v.get(celula,0)>=1)):
                remover = False
        if remover:
            riscaPonto(q)
        else:
            P2.append(q)

    texto.set("Pontos com adjacência vazia foram removidos.")
    espera()
    removeQuadriculado()
    return P2

def pontoAproxMaisProximo(P):
    """Aproximacao de fator 2 sqrt(2) do par de pontos mais proximo"""
    while len(P) > 1:
        p = choice(P)
        desenhaPonto(p, "green")
        texto.set("Ponto aleatório marcado em verde.")
        espera()
        p2 = vmp(P, p)
        canvas.create_line(tamanho*p[0], tamanho*p[1], tamanho*p2[0], tamanho*p2[1], fill="#008000", width=1, tag="vmp")
        P = removerPontos(P, dist(p,p2))
        canvas.delete("vmp")
    return p,p2

def aproxParaExato(P, a):
    """Converte solucao aproximada em solucao exata"""
    def c(p):
        return (int(p[0]/a),int(p[1]/a))

    desenhaQuadriculado(a)
    texto.set("Par de pontos mais próximos (exato) está em células adjacentes.")
    espera()

    minDist = 10e10    # Infinito
    min_p = min_q = None
    v = {}
    for p in P:
        if c(p) in v:
            v[c(p)].append(p)
        else:
            v[c(p)] = [p]

    for p in P:
        for celula in adjacencia(c(p)):
            for q in v.get(celula,[]):    # No maximo 16 pontos por celula
                if p != q and dist(p,q) <= minDist:
                    minDist = dist(p,q)
                    min_p, min_q = p, q

    removeQuadriculado()
    return min_p,min_q


# Inicio

while True:
    canvas.delete(ALL)

    P = lerPontos()
    if P == []:
        break

    # Calcula aproximacao e desenha em amarelo
    p,p2 = pontoAproxMaisProximo(P)
    desenhaPonto(p,"yellow")
    desenhaPonto(p2,"yellow")
    texto.set("Aproximação do par de pontos mais próximos marcada em amarelo.")
    espera()

    # Redesenha a tela sem riscar pontos
    # Pontos aproximadamente mais proximos em amarelo
    canvas.delete(ALL)
    for q in P:
        desenhaPonto(q)
    desenhaPonto(p,"yellow")
    desenhaPonto(p2,"yellow")
    espera()

    # Obtem solucao exata e desenha em verde
    p,p2 = aproxParaExato(P,dist(p,p2))
    desenhaPonto(p,"green")
    desenhaPonto(p2,"green")
    texto.set("Par de pontos mais próximos (exato) marcado em verde.")
    espera()