WayHeight.cpp

#define _USE_MATH_DEFINES
#include "WayHeight.h"

WayHeight::WayHeight(HeightData* H, OSM* O){
    o = O;
    h = H;
    dstep0 = 0.01;
    glacerate = int(2/dstep0);
    dmin = 0.5;
    dminur = 0.15;
    rlimit = 2;
    flach2 = 50;

    reset_cross_markers(o->get_first_KOO());
    mark_cross(o->get_first_Way());
    alloc_crossdata(o->get_first_KOO());
    mark_NoHeights();
    alloc_neighbours(o->get_first_Way());
    call_height_t();
    add_raw_HeightData(o->get_first_KOO());
    glaze();
    //show_d_h(o->get_first_KOO());
    //show_d_confidence(o->get_first_KOO());
    calc_crossheight(o->get_first_KOO());
    reduce_data(o->get_first_KOO());
    
    dismark_NoHeights();
    alloc_NoHeights_neighbours();
    mark_NoHeights();
    add_NoHeights_HeightData(o->get_first_KOO());
    dismark_NoHeights();
}
WayHeight::WayHeight(HeightData* H,double* lat, double* lon,
                     int count,Neighbour** nb){
    OSM ot;
    o = &ot;
    h = H;
    double minlat = lat[0], maxlat = lat[0], minlon = lon[0], maxlon = lon[0];
    KOO* nodes = new KOO[count];
    KOO** node = new KOO*[count];
    for(int i = 0; i < count; i++){
        if(minlat > lat[i]) minlat = lat[i];
        if(maxlat < lat[i]) maxlat = lat[i];
        if(minlon > lon[i]) minlon = lon[i];
        if(maxlon < lon[i]) maxlon = lon[i];
        nodes[i].lat = lat[i];
        nodes[i].lon = lon[i];
        nodes[i].l = NULL;
        nodes[i].cd = NULL;
        nodes[i].status = NULL;
        node[i] = &(nodes[i]);
    }
    for(int i = 1; i < count; i++)
        nodes[i-1].r = &(nodes[i]);
    nodes[count-1].r = NULL;
    minlat -= 0.1;
    maxlat += 0.1;
    minlon -= 0.2;
    maxlon += 0.2;
    Way* w= new Way;
    w->type = 1;
    w->nodec = count;
    w->l = w->r = NULL;
    w->node = node;
    dstep0 = 0.01;
    glacerate = int(2/dstep0);
    dmin = 0.5;
    dminur = 0.15;
    rlimit = 2;
    flach2 = 50;
    // trick to avoid stack overflow by deep rekursion of heavy functions
    node[0]->r = node[count-1];
    reset_cross_markers(node[0]);
    mark_cross(w);
    alloc_crossdata(node[0]);
    alloc_neighbours(w);
    h->reset_t(minlat,maxlat,minlon,maxlon);
    add_raw_HeightData(node[0]);
    glaze();
    calc_crossheight(node[0]);
    reduce_data(node[0]);
    *nb = &(node[0]->cd->neighbours[0]);
}

WayHeight::~WayHeight(){}

void WayHeight::reset_cross_markers(KOO* k){
    if(k != NULL){
        k->status = 0;
        reset_cross_markers(k->l);
        reset_cross_markers(k->r);
    }
}
void WayHeight::mark_cross(Way* w){
    if(w != NULL){
        if(w->type < 6){
            for(int i = 1; i<w->nodec-1 ;i++)
                w->node[i]->status++;
            w->node[0]->status = 2;
            w->node[w->nodec-1]->status = 2;
        }
        mark_cross(w->l);
        mark_cross(w->r);
    }
}
void WayHeight::alloc_crossdata(KOO* k){
    if(k!=NULL){
        if(k->status > 1){
            if(k->cd == NULL){
                k->cd = (crossdata*)malloc(sizeof(crossdata));
                k->cd->neighbours = NULL;
                k->cd->s = (STRONG*)malloc(sizeof(STRONG));
                k->cd->s->from = NULL;
                k->cd->s->via = NULL;
            }
            k->status = 2;
        }
        alloc_crossdata(k->l);
        alloc_crossdata(k->r);
    }
}
void WayHeight::alloc_neighbours(Way* w){
    if(w != NULL){
        if(w->type < 6){
            float d = 0;
            int iold = 0;
            for(int i = 1; i < w->nodec; i++){
                d = d + distance(w->node[i]  ->lat,w->node[i]  ->lon,
                                 w->node[i-1]->lat,w->node[i-1]->lon);
                if(w->node[i]->status > 1){
                    Neighbour *n1 = NULL, *n2 = NULL;
                    n1 = o->add_Neighbour(w->node[iold],&(w->node[iold]),
                                          w->node[i   ],w,d,i-iold+1,fw);
                    n2 = o->add_Neighbour(w->node[i],   &(w->node[iold]),
                                          w->node[iold],w,d,i-iold+1,bw);
                    
                    if(n1 != NULL && n2 != NULL){
                        n1->brthr = n2;
                        n2->brthr = n1;
                    }
                    else{
                        /*Kreisverkehr*/
                        if(n1 != NULL) n1->brthr = n1;
                        if(n2 != NULL) n2->brthr = n2;
                        if((n1 != NULL || n2 != NULL)&&w->node[i] != w->node[iold])
                            QMessageBox(QMessageBox::NoIcon,
                                        "Error",
                                        "Neighbour add failure").exec();
                    }
                    d = 0;
                    iold = i;
                }
            }
        }
        alloc_neighbours(w->l);
        alloc_neighbours(w->r);
    }
}
void WayHeight::call_height_t(){
    double latmin = 90, latmax = -90, lonmin = 180, lonmax = -180;
    check_brect(o->get_first_Way(),&latmin,&latmax,&lonmin,&lonmax);
    latmin -= 0.1;
    latmax += 0.1;
    lonmin -= 0.2;
    lonmax += 0.2;
    h->reset_t(latmin,latmax,lonmin,lonmax);
}
void WayHeight::check_brect(Way* w, double* latmin, double* latmax,
                         double* lonmin, double* lonmax){
    if(w != NULL){
        if(w->type < 6){
            if(w->maxlat > *latmax) *latmax = w->maxlat;
            if(w->maxlon > *lonmax) *lonmax = w->maxlon;
            if(w->minlat < *latmin) *latmin = w->minlat;
            if(w->minlon < *lonmin) *lonmin = w->minlon;
        }
        check_brect(w->l,latmin,latmax,lonmin,lonmax);
        check_brect(w->r,latmin,latmax,lonmin,lonmax);
    }
}
void WayHeight::add_raw_HeightData(KOO* k){
    if(k!=NULL){
        if(k->status > 1){
            Neighbour* nb = k->cd->neighbours;
            while(nb != NULL){
                if(nb->rd == fw){
                    long N, n = 0;
                    double t[3] = {0,0,0}, dstep = 0;
                    if(nb->d > 0){
                        N = qMax(long(2),long(1+ceil(nb->d/dstep0)));
                        double dN;
                        double d0 = 0, dlon, dlat, di, lon, lat;
                        dstep = nb->d / (N-1);
                        nb->tp = (trackpoint*)malloc(2*N*sizeof(trackpoint));
                    
                        for(int i = 0; i < nb->nodec-1; i++){
                            /*Fuer jedesWegstueck ...*/
                            di = distance(nb->node[i  ]->lat,nb->node[i  ]->lon,
                                          nb->node[i+1]->lat,nb->node[i+1]->lon);
                            if(di > 0){
                                dlon = (nb->node[i+1]->lon-nb->node[i]->lon)/(di/dstep);
                                dlat = (nb->node[i+1]->lat-nb->node[i]->lat)/(di/dstep);
                                t[2] = dlon * cos(M_PI/180.*k->lat);
                                t[1] = dlat / sqrt(t[2]*t[2]+dlat*dlat);
                                t[2] = t[2] / sqrt(t[2]*t[2]+dlat*dlat);
                            }
                            else
                                dlon = dlat = 0;
                            dN = (n*dstep-d0)/dstep;
                            lon = nb->node[i]->lon + dN*dlon;
                            lat = nb->node[i]->lat + dN*dlat;

                            while(n < N && n*dstep < d0+di){
                                /*falls ein zu verzeichnender Punkt auf das
                                Wegstueck faellt*/
                                nb->tp[N+n].h = h->height_t(lon,lat,&t[0],4);
                                nb->tp[N+n].d = float(n*dstep);
                                nb->tp[  n].h = 0;
                                nb->tp[  n].d = float(t[0]);

                                n++;
                                lon = lon + dlon;
                                lat = lat + dlat;
                            }

                            d0 = d0 + di;
                        }
                    }
                    else{
                        N = 2;
                        nb->tp = (trackpoint*)malloc(2*N*sizeof(trackpoint));
                        nb->tp[2*N-2].h = h->height_t(nb->node[0]->lon, nb->node[0]->lat,  &t[0],   4);
                        nb->tp[2*N-2].d = 0;
                        nb->tp[N-2].d = float(t[0]);
                        nb->tp[N-2].h = 0;
                    }
                    //if(nb->nodec == 0)
                    //  MessageBox(NULL,L"",NULL,NULL);
                    //t[1]=t[2]=0;
                    nb->tp[2*N-1].h = h->height_t(nb->node[nb->nodec-1]->lon,   nb->node[nb->nodec-1]->lat,  &t[0], 4);
                    nb->tp[2*N-1].d = float((N-1)*dstep);
                    nb->tp[N-1].d = float(t[0]);
                    nb->tp[N-1].h = 0;


                    nb->tpc = N;
                    nb->brthr->tp = nb->tp;
                    nb->brthr->tpc = N;

                }
                nb = nb->next;
            }
        }
        add_raw_HeightData(k->l);
        add_raw_HeightData(k->r);
    }
}
void WayHeight::glaze(){
    generate_PortionInstructions(o->get_first_KOO());
    for(int i = 0; i < glacerate; i++){
        portion_way(o->get_first_KOO());
        portion_cross(o->get_first_KOO());
        portion_divide(o->get_first_KOO());
    }
    delete_PortionInstructions(o->get_first_KOO());
}
void WayHeight::portion_way(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){  
            Neighbour* nb = k->cd->neighbours;
            while(nb != NULL){
                if(nb->rd == fw){
                    for(long i = 1; i < nb->tpc-1; i++){
                        nb->tp[i-1].h = nb->tp[i-1].h + nb->tp[i].d + nb->tp[i-1].d;
                        nb->tp[i+1].h = nb->tp[i+1].h + nb->tp[i].d + nb->tp[i+1].d;
                    }
                    nb->tp[1        ].h = nb->tp[1].h 
                                        + nb->tp[0].d 
                                        + nb->tp[1].d;
                    nb->tp[nb->tpc-2].h = nb->tp[nb->tpc-2].h 
                                        + nb->tp[nb->tpc-1].d 
                                        + nb->tp[nb->tpc-2].d;
                }
                nb = nb->next;
            }
        }
        portion_way(k->l);
        portion_way(k->r);
    }
}
void WayHeight::portion_cross(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){  
            PortionInstructionCol* pi = (PortionInstructionCol*) k->cd->s->from;
            while(pi != NULL){
                for(int i = 0; i < pi->Pcount; i++)
                    pi->PI[i].dest->h = float(  pi->PI[i].dest->h 
                                        + pi->src->d*pi->PI[i].cos);
                pi->src->h = pi->src->h + pi->src->d;
                pi = pi->next;
            }
        }
        portion_cross(k->l);
        portion_cross(k->r);
    }
}
void WayHeight::generate_PortionInstructions(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){  
            Neighbour* nb = k->cd->neighbours;
            PortionInstructionCol pic, *p = &pic;
    
            /*Abgehende Straße zaehlen*/
            int nbcount = 0;
            while(nb != NULL){
                nbcount++;
                nb = nb->next;
            }
            
            /*Richtungen berechnen*/
            double* phi = (double*)malloc(nbcount*sizeof(double)),dlon,dlat;
            nb = k->cd->neighbours;
            trackpoint** tp = (trackpoint**)malloc(nbcount*sizeof(trackpoint*));
            nbcount = 0;
            while(nb != NULL){
                if(nb->rd == fw){
                    dlon = nb->node[1]->lon-nb->node[0]->lon;
                    dlat = nb->node[1]->lat-nb->node[0]->lat;
                    tp[nbcount] = &(nb->tp[0]);
                }
                else{
                    dlon = nb->node[nb->nodec-2]->lon-nb->node[nb->nodec-1]->lon;
                    dlat = nb->node[nb->nodec-2]->lat-nb->node[nb->nodec-1]->lat;
                    tp[nbcount] = &(nb->tp[nb->tpc-1]);
                }
                dlon = dlon * cos(nb->node[0]->lat/180*M_PI);
                phi[nbcount] = atan2(dlat,dlon);
                nbcount++;
                nb = nb->next;
            }

            /*Verteilungsschluessel generieren*/
            nb = k->cd->neighbours;
            for(int i = 0; i < nbcount; i++){
                p->next = (PortionInstructionCol*)malloc(sizeof(PortionInstructionCol));
                p = p->next;
                p->Pcount = nbcount-1;
                p->next = NULL;
                p->nb = nb;
                p->SumCos = 0;
                p->PI = (PortionInstruction*)malloc(p->Pcount*sizeof(PortionInstruction));
                p->src = tp[i];
                int q = 0;
                for(int j = 0; j < nbcount; j++)
                    if(i != j){
                        p->PI[q].dest = tp[j];
                        p->PI[q].cos = -(cos(phi[i]-phi[j]));
                        if(p->PI[q].cos < 0) p->PI[q].cos = 0;
                        p->SumCos = p->SumCos + p->PI[q].cos;
                        q++;
                    }
                nb = nb->next;

                /*Verteilungsschlüssel speichern*/
                k->cd->s->from = pic.next;
            }
            free(phi);
            free(tp);
        }
        generate_PortionInstructions(k->l);
        generate_PortionInstructions(k->r);
    }
}
void WayHeight::delete_PortionInstructions(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){
            PortionInstructionCol *p0 = (PortionInstructionCol*) k->cd->s->from, *p = p0;
            while(p != NULL){
                p0 = p;
                free(p0->PI);
                p = p0->next;
                free(p0);
            }
        }
        delete_PortionInstructions(k->l);
        delete_PortionInstructions(k->r);
    }
}
void WayHeight::portion_divide(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){  
            /*Wegemitten mitteln, d.h. dividieren*/
            Neighbour* nb = k->cd->neighbours;
            while(nb != NULL){
                if(nb->rd == fw)
                    for(long i = 1; i < nb->tpc-1; i++){
                        nb->tp[i].d = float(nb->tp[i].h / 4.);
                        nb->tp[i].h = 0;
                    }
                nb = nb->next;
            }

            /*Kreuzungsenden mitteln*/
            PortionInstructionCol* pic = (PortionInstructionCol*) k->cd->s->from;
            while(pic != NULL){
                pic->src->d = float(pic->src->h / (3 + pic->SumCos));
                pic->src->h = 0;
                pic = pic->next;
            }
        }
        portion_divide(k->l);
        portion_divide(k->r);
    }
}
void WayHeight::show_d_h(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){  
            /*Wegemitten mitteln, d.h. dividieren*/
            Neighbour* nb = k->cd->neighbours;
            while(nb != NULL){
                if(nb->rd == fw)
                    for(long i = 0; i < nb->tpc; i++){
                        nb->tp[i].h = nb->tp[nb->tpc+i].h;
                        nb->tp[i].d = nb->tp[nb->tpc+i].d;
                    }
                nb = nb->next;
            }
        }
        show_d_h(k->l);
        show_d_h(k->r);
    }
}
void WayHeight::show_d_confidence(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){  
            /*Wegemitten mitteln, d.h. dividieren*/
            Neighbour* nb = k->cd->neighbours;
            while(nb != NULL){
                if(nb->rd == fw)
                    for(long i = 0; i < nb->tpc; i++){
                        nb->tp[i].h = nb->tp[i].d;
                        nb->tp[i].d = nb->tp[nb->tpc+i].d;
                    }
                nb = nb->next;
            }
        }
        show_d_confidence(k->l);
        show_d_confidence(k->r);
    }
}
void WayHeight::calc_crossheight(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){
            double rl = 0;              //reliability limit
            int i = 0, irl = 0;
            Neighbour* n = k->cd->neighbours, *c = NULL;
            /*Bestimme die unzuverlässigste Höhenangabe*/
            while(n != NULL){
                if((n->rd == fw && n->tp[0].d > rl)
                    ||(n->rd == bw && n->tp[n->tpc-1].d > rl)){
                    c = n;
                    irl = i;
                    if(n->rd == fw)
                        rl = n->tp[0].d;
                    else 
                        rl = n->tp[n->tpc-1].d;
                }
                n = n->next;
                i++;
            }
            
            if(rl>rlimit){
                /*falls die unzuverlaessigste Angabe ueber der Toleranz liegt
                muss eine neue verbindliche Hoehe für alle Wege bestimmt werden*/
                /*Die Richtung des Hanggradienten wird ermittelt*/
                double latcorr = cos(k->lat/180.*M_PI);
                double  phi = h->height_t(k->lon,k->lat,NULL,3);
                double dlat = - cos(phi)           * 0.08/111./10.;
                double dlon = - sin(phi)/latcorr * 0.08/111./10.;
                /*Entlang des Hanggradienten wird versucht, in fuenf 10-Meter-
                Schritten den Talboden zu erreichen*/
                double dxt = h->height_t(k->lon,k->lat,NULL,1);
                double dyt = h->height_t(k->lon,k->lat,NULL,2);
                double grad20 = dxt*dxt + dyt*dyt*latcorr*latcorr,
                       grad2 = grad20;
                irl = 0;
                for(int i = 1; i < 10; i++){
                    /*Versuche einen besseren Punkt für die Kreuzung zu finden*/
                    dxt = h->height_t(k->lon+dlon*i,k->lat+dlat*i,NULL,1);
                    dyt = h->height_t(k->lon+dlon*i,k->lat+dlat*i,NULL,2);
                    if( dxt*dxt + dyt*dyt*latcorr*latcorr < grad2*0.9){
                        /*Forderung: der Hang wird immer flacher, sonst
                        abbrechen*/
                        grad2 = dxt*dxt + dyt*dyt*latcorr*latcorr;
                        irl = i;
                    }
                    else
                        i = 10;
                }

                if(irl > 0 && 
                    grad2 < flach2 &&   //neuer Punkt liegt absolut flach
                    grad2 < grad20/5.&& //neueer Punkt liegt flacher als alter
                      h->height_t(k->lon+irl*dlon,k->lat+irl*dlat,NULL,0)
                    - h->height_t(k->lon+10*dlon,k->lat+irl*dlat,NULL,0) < 5
                                        //wenn man nochweiter geht, setzt sich
                                        //der Hang nicht fort
                                        ){
                    double newheight = h->height_t(k->lon+dlon*irl,
                                                   k->lat+dlat*irl,NULL,0);
                    double dh = h->height_t(k->lon,k->lat,NULL,0) - newheight;
                    n = k->cd->neighbours;
                    while(n != NULL){
                        if(n->d > 0){
                            if(n->rd == fw){
                                for(long i = n->tpc; i < 2*n->tpc -1; i++){
                                    n->tp[i].h = float(n->tp[i].h 
                                                 - (n->d - n->tp[i].d)/n->d * dh);
                                }
                            }
                            else{
                                for(long i = n->tpc; i < 2*n->tpc; i++){
                                    n->tp[i].h = float(n->tp[i].h 
                                                 - (       n->tp[i].d)/n->d * dh);
                                }
                            }
                        }
                        else{
                            if(n->rd == fw)n->tp[0].h = float(newheight);
                            else        n->tp[n->tpc-1].h = float(newheight);
                        }
                        n = n->next;
                    }
                }
            }
        }
        calc_crossheight(k->r);
        calc_crossheight(k->l);
    }   
}
void WayHeight::reduce_data(KOO* k){
if(k != NULL){
        if(k->cd != NULL){
            Neighbour* n = k->cd->neighbours;
            while(n != NULL){
                if(n->rd == fw){
                    select_heights(n,0,n->tpc-1);
                    finalize_data(n);
                }
                n = n->next;
            }
        }
        reduce_data(k->r);
        reduce_data(k->l);
    }
}
void WayHeight::select_heights(Neighbour* n,long s,long e){
    short keep = 0;
    double d0 = n->tp[n->tpc + s].d, d1 = n->tp[n->tpc + e].d;
    double d = d1 - d0;
    if(d > dminur){
        double h0 = n->tp[n->tpc + s].h, h1 = n->tp[n->tpc + e].h;
        double dh = h1 - h0;
        double grd = dh / d;
        long   max= 0,   min = 0,  maxur = 0,  minur = 0;
        double maxh = 0, minh = 0, maxhur = 0, minhur = 0;  

        for(long i = s + 1; i < e - 1; i++){
        /*Bestimme den konkavesten und den konvexesten Punkt auf der Strecke*/
            dh = n->tp[n->tpc + i].h - (h0 + (n->tp[n->tpc + i].d-d0)*grd);
            if(d > dmin && //n->tp[i].d < rlimit && 
                n->tp[n->tpc + i].d-d0 > dmin && d1-n->tp[n->tpc + i].d > dmin){
                /*aus verlaesslichen Daten*/
                if(dh > maxh){ maxh = dh; max = i;}
                if(dh < minh && n->tp[i].d < rlimit){ minh = dh; min = i;}
            }
            else
                if(n->tp[n->tpc + i].d-d0 > dminur && d1-n->tp[n->tpc + i].d > dminur){
                /*aus unverlaesslichen Daten*/
                if(dh > maxhur){ maxhur = dh; maxur = i;}
                if(dh < minhur){ minhur = dh; minur = i;}
                }
        }

        /*Widerhole den Prozess für die entstandenen Teilstrecken*/
        if( min > 0 && max > 0){
            long first = qMin(min,max);
            long second = qMax(min,max);
            select_heights(n, s     ,  first);
            select_heights(n, first , second);
            select_heights(n, second,      e);
            keep++;
        }
        else{
            if(min > 0){
                select_heights(n, s  , min);
                select_heights(n, min,   e);
                keep++;
            }
            if(max > 0){
                select_heights(n, s,   max);
                select_heights(n, max,   e);
                keep++;
            }
        }

        /*Falls nur unzuverlaessige Daten vorhanden waren: Versuche, ueber
        unzuverlaessige Stuetzpunkte weiterzumachen*/
        if( min == 0 && max == 0 && (minur != 0 || maxur != 0)){
            if( minhur + maxhur <= 0
                && n->tp[n->tpc + minur].h > qMin(h0,h1)
                && n->tp[n->tpc + minur].h < qMax(h0,h1)){
                select_heights(n, s    , minur);
                select_heights(n, minur,     e);
                keep++;
            }
            if(-minhur < maxhur
                && n->tp[n->tpc + maxur].h > qMin(h0,h1)
                && n->tp[n->tpc + maxur].h < qMax(h0,h1)){
                select_heights(n, s    , maxur);
                select_heights(n, maxur,     e);
                keep++;
            }
        }
    }

    if(!keep)
        /*zum Loeschen markieren, falls keine weiterverarbeitung erreicht
        wurde*/
        for(long i = n->tpc + s + 1; i < n->tpc + e; i++){
            n->tp[i].d = -1;    
        }

}
void WayHeight::finalize_data(Neighbour* n){
    /*sinvolle Hoehenpunkte zaehlen*/
    long tpc = 0;
    for(long i = n->tpc; i < 2*n->tpc; i++){
        if(n->tp[i].d >= 0) 
            tpc++;
    }

    /*daraus neue Daten anlegen*/
    trackpoint* tpt = (trackpoint*)malloc(tpc*sizeof(trackpoint));
    tpc = 0;
    for(long i = n->tpc; i < 2*n->tpc; i++)
        if(n->tp[i].d >= 0){
            tpt[tpc] = n->tp[i];
            tpc++;
        }
    
    /*Altes trackpoint-array loeschen*/
    free(n->tp);
    
    /*neues zuweisen*/
    n->tp = tpt;
    n->tpc = tpc;
    n->brthr->tp = tpt;
    n->brthr->tpc = tpc;

    /*Hoehenmeter ermitteln und speichern*/
    float hmup = 0, hmdown = 0;
    for(long i = 0; i < n->tpc-1; i++)
        if(n->tp[i].h < n->tp[i+1].h) hmup = hmup 
                                             + (n->tp[i+1].h - n->tp[i].h);
        else                          hmdown = hmdown 
                                             + (n->tp[i].h - n->tp[i+1].h);
    
    n->hm = hmup;
    n->brthr->hm = hmdown;
    
}
short WayHeight::check0(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){
            Neighbour* n = k->cd->neighbours;
            while(n != NULL){
                if(n->rd == fw)
                    if(n->tp[n->tpc].d != 0)
                        return 0;
                n = n->next;
            }
        }
        return (check0(k->l) && check0(k->r));
    }
    return 1;
}
void WayHeight::mark_NoHeights(){
    lines* l = *(o->NoHeight);
    while(l != NULL){
        l->way->type = l->way->type + 10;
        l = l->next;
    }
}
void WayHeight::dismark_NoHeights(){
    lines* l = *(o->NoHeight);
    while(l != NULL){
        l->way->type = l->way->type - 10;
        l = l->next;
    }
}
void WayHeight::alloc_NoHeights_neighbours(){
    lines* l = *(o->NoHeight);
    while(l != NULL){
        Way* w = l->way;
        if(w->type < 6){
            float d = 0;
            int iold = 0;
            for(int i = 1; i < w->nodec; i++){
                d = d + distance(w->node[i]  ->lat,w->node[i]  ->lon,
                                    w->node[i-1]->lat,w->node[i-1]->lon);
                if(w->node[i]->status > 1){
                    Neighbour *n1 = NULL, *n2 = NULL;
                    n1 = o->add_Neighbour(w->node[iold],&(w->node[iold]),
                                            w->node[i   ],w,d,i-iold+1,fw);
                    n2 = o->add_Neighbour(w->node[i],   &(w->node[iold]),
                                            w->node[iold],w,d,i-iold+1,bw);
                    
                    if(n1 != NULL && n2 != NULL){
                        n1->brthr = n2;
                        n2->brthr = n1;
                    }
                    else{
                        /*Kreisverkehr*/
                        if(n1 != NULL) n1->brthr = n1;
                        if(n2 != NULL) n2->brthr = n2;
                        if((n1 != NULL || n2 != NULL)&&w->node[i] != w->node[iold])
                            QMessageBox(QMessageBox::NoIcon,"Error",
                                        "Neighbour add failure").exec();
                    }
                    d = 0;
                    iold = i;
                }
            }
        }
        l = l->next;
    }
}
void WayHeight::add_NoHeights_HeightData(KOO* k){
    if(k != NULL){
        if(k->cd != NULL){  
            Neighbour* nb = k->cd->neighbours;
            while(nb != NULL){
                if(nb->way->type > 9 && nb->rd == fw){
                    nb->tpc = nb->brthr->tpc = 2;
                    nb->tp = nb->brthr->tp = 
                        (trackpoint*)malloc(2*sizeof(trackpoint));
                    KOO kfake;
                    nb->tp[0].d = 0;
                    nb->tp[1].d = nb->d;

                    /*fuer Startpunkt bestimmen*/
                    KOOlist kl1; kl1.next = NULL; kl1.k = &kfake;
                    trackpointlist tl1; tl1.next = NULL;
                    trace_to_HeightData(0,k,&kl1,&tl1);
                    trackpointlist* tt = tl1.next;
                    float srho = 0;
                    nb->tp[0].h = 0;
                    while(tt != NULL){
                        if(tt->t.d != 0){
                            nb->tp[0].h = nb->tp[0].h + tt->t.h * 1. / tt->t.d;
                            srho = srho + 1. / tt->t.d;
                            tt = tt->next;
                        }
                        else{
                            nb->tp[0].h = tt->t.h;
                            srho = 0;
                            tt = NULL;
                        }
                    }
                    if(srho > 0)
                        nb->tp[0].h = nb->tp[0].h / srho;
                    /*fuer Endpunkt bestimmen*/
                    KOOlist kl2; kl2.next = NULL; kl2.k = &kfake;
                    trackpointlist tl2; tl2.next = NULL;
                    trace_to_HeightData(0,k,&kl2,&tl2);
                    tt = tl2.next;
                    srho = 0;
                    nb->tp[1].h = 0;
                    while(tt != NULL){
                        if(tt->t.d != 0){
                            nb->tp[1].h = nb->tp[1].h + tt->t.h * 1. / tt->t.d;
                            srho = srho + 1. / tt->t.d;
                            tt = tt->next;
                        }
                        else{
                            nb->tp[1].h = tt->t.h;
                            srho = 0;
                            tt = NULL;
                        }
                    }
                    if(srho > 0)
                        nb->tp[1].h = nb->tp[1].h / srho;
                    /*Listen freigeben*/
                    KOOlist *kbuf1, *kbuf2;
                    trackpointlist *tbuf1, *tbuf2;
                    kbuf1 = kl1.next;
                    while(kbuf1 != NULL){
                        kbuf2 = kbuf1; kbuf1 = kbuf1->next; free(kbuf2);
                    }
                    kbuf1 = kl2.next;
                    while(kbuf1 != NULL){
                        kbuf2 = kbuf1; kbuf1 = kbuf1->next; free(kbuf2);
                    }
                    tbuf1 = tl1.next;
                    while(tbuf1 != NULL){
                        tbuf2 = tbuf1; tbuf1 = tbuf1->next; free(tbuf2);
                    }
                    tbuf1 = tl2.next;
                    while(tbuf1 != NULL){
                        tbuf2 = tbuf1; tbuf1 = tbuf1->next; free(tbuf2);
                    }
                }
                nb = nb->next;
            }
        }
        add_NoHeights_HeightData(k->l);
        add_NoHeights_HeightData(k->r);
    }
}
void WayHeight::trace_to_HeightData(float d, KOO* k, KOOlist* kl, trackpointlist *tl){
    if(k != NULL && !KOO_already_used(k,kl)){
        /*zuerst k als benutzt kennzeichnen*/
        KOOlist *ktnew = (KOOlist*) malloc(sizeof(KOOlist));
        ktnew->next = kl->next;
        kl->next = ktnew;
        ktnew->k = k;
        /*jett nach adäquaten Hoehendaten suchen*/
        Neighbour *nb = k->cd->neighbours;
        while(nb != NULL && nb->way->type > 9)
            nb = nb->next;
        if(nb != NULL){
            /*adäquate Hoehendaten in nb*/
            trackpointlist *tlnew = (trackpointlist*) malloc(sizeof(trackpointlist));
            tlnew->next = tl->next;
            tl->next = tlnew;
            if(nb->rd == fw)    tlnew->t = nb->tp[0];
            else                tlnew->t = nb->tp[nb->tpc-1];
            tlnew->t.d = d;
        }
        else{
            /*keine adäquaten Hoehendaten gefunden*/
            nb = k->cd->neighbours;
            while(nb != NULL){
                trace_to_HeightData(d + nb->d, nb->nb, kl, tl);
                nb = nb->next;
            }
        }
    }
}
int WayHeight::KOO_already_used(KOO* k, KOOlist* kl){
    while(kl != NULL){
        if(kl->k == k)
            return 1;
        else
            kl = kl->next;
    }
    return 0;
}