# Vstup:
# 2D souradnice dvou bodu (dva konce reky)
# posloupnost 2D souradnic, reprezentujicich prehradu

# Vystup: 
# posloupnost bodu, ktere spojuji dva konce reky a prochazeji
# prehradou

# Postup:
# - triangulace polygonu
# - nalezeni stredu trojuhelniku + jejich sousedu
# - nalezeni nejblizsiho stredu trojuhelniku k zadanym koncum reky
# - ohodnoceni vzdalenosti bodu (eulerovska vzdalenost)
# - dijkstrovym algoritmem nalezeni nejkratsi cesty od konci ke konci

# TODO:
# - kontroly vstupnich dat

import visual
from helpers import Point,SameSide,Triangle
from dijkstra import shortestPath
import sys

# 0 - normal
# 1 - verbose
# 2 - debug
loglevel = 1

def log(level, msg):
    global loglevel
    if level <= loglevel:
        print msg

def get_left_index(polygon):
    min = polygon[0].x
    idx = 0
    for i in range(0,len(polygon)):
        log(2, "get_left_index: polygon[i].x: %f, min: %f" % (polygon[i].x, min))
        if polygon[i].x < min:
            min = polygon[i].x
            idx = i
    return idx
        
def get_wrong_point(tr, polygon):
    """
    Otestuj jestli vsechny body z polygonu jsou mimo trojuhelnik.
    Pokud tam nejake body jsou, pak vrati nejlevejsi z nich.
    """
    wrong_points = []
    for p in polygon:
        if p==tr.p1 or p==tr.p2 or p==tr.p3:
            continue
        if tr.contains(p):
            wrong_points.append(p)

    log(2, "get_wrong_point: all wrong points: [%s]" % (",".join(["%s" % str(p) for p in wrong_points])))

    if len(wrong_points)>0:
        idx = get_left_index(wrong_points)
        return wrong_points[idx]
    else:
        return None
    

def get_valid_triangle(testpoint_index, polygon):
    log(2, "get_valid_triangle: processing polygon: %s" % polygon)

    newtr = Triangle(polygon[testpoint_index], polygon[(testpoint_index+1)%len(polygon)],polygon[testpoint_index-1])

    log(2, "get_valid_triangle: testing triangle: %s" % newtr)
    wrong_point_present = True
    while wrong_point_present:
    # test if the triangle is valid
        wrong_point = get_wrong_point(newtr, polygon)
        log(2, "get_valid_triangle: wrong point: %s" % wrong_point)
        if wrong_point:
            newtr.replaceRight(wrong_point)
            log(2, "get_valid_triangle: wrong point replaced: %s" % newtr)
            wrong_point_present = True
        else:
            wrong_point_present = False
            
    return newtr
    
def get_middle_triangle(tr, plg):
    """
    Zjisti, ktery z bodu trojuhelniku je v ramci polygonu prostredni
    """
    # tohle by urcite slo nejak efektivneji :(
    
    log(2, "get_middle_triangle: tr: %s, polygon: %s" % (repr(tr), repr(plg)))
    log(2, "get_middle_triangle: tr: %s, polygon: (%s)" % (str(tr), ",".join([str(p) for p in plg])))
    for i in range(0,len(plg)):
        if (tr.p1 == plg[i] and tr.p2==plg[i-1] and tr.p3==plg[(i+1)%len(plg)]) \
           or (tr.p1 == plg[i] and tr.p3==plg[i-1] and tr.p2==plg[(i+1)%len(plg)]) \
           or (tr.p2 == plg[i] and tr.p1==plg[i-1] and tr.p3==plg[(i+1)%len(plg)]) \
           or (tr.p2 == plg[i] and tr.p3==plg[i-1] and tr.p1==plg[(i+1)%len(plg)]) \
           or (tr.p3 == plg[i] and tr.p1==plg[i-1] and tr.p2==plg[(i+1)%len(plg)]) \
           or (tr.p3 == plg[i] and tr.p2==plg[i-1] and tr.p1==plg[(i+1)%len(plg)]):
            return i
    log(2, "get_middle_triangle: failed")
    return None

def get_abc_triangle(tr, plg):
    
    log(2, "get_abc_triangle - tr: %s, tr: %s, polygon: %s" % (str(tr), repr(tr), plg))
    outstr = ",".join([ "(%f,%f)" % (one.x,one.y) for one in plg ])
    log(2, "get_abc_triangle - polygon: [%s]" % outstr)

    for i in range(0, len(plg)):
        if tr.p1 == plg[i] and tr.p2 == plg[i+1]:
            return (tr.p1, tr.p2, tr.p3)
        if tr.p2 == plg[i] and tr.p1 == plg[i+1]:
            return (tr.p2, tr.p1, tr.p3)

        if tr.p1 == plg[i] and tr.p3 == plg[i+1]:
            return (tr.p1, tr.p3, tr.p2)
        if tr.p3 == plg[i] and tr.p1 == plg[i+1]:
            return (tr.p3, tr.p1, tr.p2)

        if tr.p2 == plg[i] and tr.p3 == plg[i+1]:
            return (tr.p2, tr.p3, tr.p1)
        if tr.p3 == plg[i] and tr.p2 == plg[i+1]:
            return (tr.p3, tr.p2, tr.p1)

    raise ValueError("Cannot locate triangle in polygon")

def get_subpolygon(start, end, polygon):
    """
    Vrati polygon tvoreny body mezi bodem start a end ze vstupniho polygonu.
    Musi dat pozor na to, kdyz bod end je v polygonu jeste pred bodem start
    """
    log(2, "get_subpolygon - start: %s, end: %s, polygon: %s" % (repr(start), repr(end), polygon))
    retval = []
    started = False
    for p in polygon+polygon:
        if p==start:
            started = True
        if started:
            retval.append(p)
        if p==end and started:
            return retval


def split_polygon(tr, polygon):
    """
    Predpoklada, ze trojuhelnik tr je slozen ze dvou sousednich bodu (v ramci polygonu) (a,b) a jednoho
    nesousedniho (c).
    Pote rozdeli polygon na dva takove, ze (a,c) a (b,c) tvori novou hranici techto novych polygonu.
    """
    polygon_size = len(polygon)
    double_polygon = list(polygon)
    double_polygon.extend(double_polygon)
    # nalezeni sousednich bodu
    a,b,c = get_abc_triangle(tr,double_polygon)
    log(2, "a,b,c: %s %s %s" % (a,b,c))

    pol1 = get_subpolygon(c, a, polygon)
    pol2 = get_subpolygon(b, c, polygon)

    return (pol1, pol2)

def triangulate(polygon):
    """
    Rozdeli obecny n-uhelnik na sadu trojuhelniku
    """
    #http://www.siggraph.org/education/materials/HyperGraph/scanline/outprims/polygon1.htm
    log(2, "traingulate: processing polygon: %s" % polygon)
    res_trs = []
    while len(polygon)>3:

        left = get_left_index(polygon)
        log(2, "left point is: %s, index in polygon: %d" % (polygon[left], left))

        tr = get_valid_triangle(left, polygon)
        res_trs.append(tr)
        middle = get_middle_triangle(tr, polygon)

        # blba situace, kdy body ve vyrazovanem trojuhelniku nejsou sousedni
        # prakticky bychom potrebovali rozdelit polygon na vice polygonu a zpracovat je
        # samostatne (rekurze??)
        log(2, "traingulate: middle index: %s" % middle)
        if middle is None:
            pol1, pol2 = split_polygon(tr,polygon)
            log(2, "splitted polygon1: %s" % (pol1))
            log(2, "splitted polygon2: %s" % (pol2))
            
            t1 = triangulate(pol1)
            log(2, "triangles t1: %s" % (t1))
            t2 = triangulate(pol2)
            log(2, "triangles t2: %s" % (t2))
            res_trs.extend(t1)
            res_trs.extend(t2)
            return res_trs
        else:
            log(2, "middle point index: %d" % (middle))
            log(2, "middle point: %s" % (polygon[middle]))
            polygon.remove(polygon[middle])
            log(2, "resulting polygon: %s" % (polygon))
    
    if len(polygon)==3:
        res_trs.append(Triangle(polygon[0], polygon[1], polygon[2]))
    elif len(polygon)!=0:
        raise ValueError("We have %d points left in polygon" % len(polygon))
    return res_trs

def get_nearest_center(p, triangles):
    """
    Vrati dvojici - nejblizsi bod (trida Point) a vzdalenost
    """
    c = None
    min = 0
    for t in triangles:
        if p!=t:
            val = p.distanceFrom(t.center)
            if val<min or not c:
                c = t.center
                min = val
    return (c,min)

def create_graph(p1, p2, triangles):
    """
    Vytvori pythonovsky slovnik, ktery reprezentuje
    graf pro hledani nejkratsi cesty
    """
    G = {}
    c,dist = get_nearest_center(p1, triangles)
    G[p1] = {c:dist}
    G[c] = {p1:dist}
    c,dist = get_nearest_center(p2, triangles)
    G[p2] = {c:dist}
    G[c] = {p2:dist}
    for tr in triangles:
        p = tr.center
        if not G.has_key(p):
            G[p] = {}
        for otr in triangles:
            if otr==tr:
                continue
            if tr.isNeighbour(otr):
                G[p][otr.center] = p.distanceFrom(otr.center)

    return G

def najdi_cestu(reka1, reka2, polygon):
    triangles = []
    triangles = triangulate(list(polygon))
    log(1, "najdi_cestu: triangles: %s, polygon: %s" % (triangles, polygon))
    for tr in triangles:
        tr.countCenter()
        log(2, "najdi_cestu: triangle: %s, center: %s" % (tr, tr.center))

    G = create_graph(reka1, reka2, triangles)
    log(1, "G: %s" % G)
    spath = shortestPath(G, reka1, reka2)
    log(1, "spath: %s" % spath)

    visual.init()
    debug_triangles = [
        ]
    visual.showTriang(polygon, triangles, reka1, reka2, spath, debug_triangles)


if __name__=="__main__":
    plg = []
    for l in file("polygon.txt"):
        x,y = l.split()
        plg.append(Point(float(x),float(y)))

#    p2 = [(2049960,6361631), (2053587,6362067), (2053590,6362049), (2053581,6362023), (2053548,6362005), (2053548,6362005), (2053441,6361980), (2053228,6361922), (2053200,6361860), (2053115,6361853), (2052941,6361796), (2052916,6361802), (2052894,6361822), (2052612,6361772), (2052551,6361797), (2052472,6361787), (2052478,6361763), (2052466,6361753), (2052435,6361765), (2051907,6361663), (2051198,6361751), (2051096,6361756), (2051044,6361725)]
#    plg = [ Point(x,y) for (x,y) in p2 ]

#    name    |    start st_astext           |   end     st_astext
#-----------+------------------------------+------------------------------
# Ostravice | POINT(2053272.01 6354117.47) | POINT(2055788.87 6352415.43)
# Ostravice | POINT(2050242.41 6362144.44) | POINT(2050271 6362109.03)

    start = Point(2053272.01, 6354117.47)
    end = Point(2050271, 6362109.03)

    najdi_cestu(start, end, plg)

#	najdi_cestu(Point(10,10),Point(600,400),
#       ( Point(190,100), Point(220,240), 
#         Point(100,300), Point(340,430), 
#         Point(500,220), Point(430,50), 
#         Point(340,170) )
#	)

# vi: ts=4:sw=4:expandtab: