TYSetGeometriqueParcours.cpp

Go to the documentation of this file.

/*
 * Copyright (C) <2012> <EDF-R&D> <FRANCE>
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
/*
 *
 */
 
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#include "Tympan/models/common/3d.h"
#include "TYSetGeometriqueParcours.h"
#include "TYPointParcours.h"
#include <assert.h>
#include <algorithm>
 
TYPointParcours* TYSetGeometriqueParcours::_ListePointQSort = NULL;
TYPointParcours* TYSetGeometriqueParcours::_SrceQSort = NULL;
TYPointParcours* TYSetGeometriqueParcours::_DestQSort = NULL;
QMutex TYSetGeometriqueParcours::_mutex;
 
// Return Value Description for Qsort compare
//< 0 elem1 less than elem2
// 0 elem1 equivalent to elem2
//> 0 elem1 greater than elem2
int compareTYPolyligneParcours(const void* p1, const void* p2)
{
    TYPolyligneParcours* P1 = (TYPolyligneParcours*)p1;
    TYPolyligneParcours* P2 = (TYPolyligneParcours*)p2;
    int indexPointPoly1 = P1->indexePoint1();
    int indexPointPoly2 = P2->indexePoint1();
    assert(indexPointPoly1 >= 0);
    assert(indexPointPoly2 >= 0);
    // Si les 2 premiers indexes sont egaux, on regarde les suivants:
    if (indexPointPoly1 == indexPointPoly2)
    {
        indexPointPoly1 = P1->indexePoint2();
        indexPointPoly2 = P2->indexePoint2();
    }
    return (indexPointPoly1 - indexPointPoly2);
}
 
void TYSetGeometriqueParcours::Copy(TYSetGeometriqueParcours& geoIn)
{
    // Copie des points
    _ListePoint = new TYPointParcours[geoIn._nNbPointTotal];
    _nNbPointTotal = geoIn._nNbPointTotal;
    int i = 0, j = 0;
    for (i = 0; i < _nNbPointTotal; i++)
    {
        _ListePoint[i] = geoIn._ListePoint[i];
    }
    // Copie des polylignes
    _ListePolylines = new TYPolyligneParcours[geoIn._nNbPolylines];
    _nNbPolylines = geoIn._nNbPolylines;
    for (i = 0; i < _nNbPolylines; i++)
    {
        _ListePolylines[i].allouer(geoIn._ListePolylines[i].nombreDePoint());
        for (j = 0; j < geoIn._ListePolylines[i].nombreDePoint(); j++)
        {
            // Copie le pointeur du point de la polyligne copiée:
            _ListePolylines[i].ajoutePoint(j, geoIn._ListePolylines[i].pointPtr(j));
        }
    }
}
 
void TYSetGeometriqueParcours::SwapPolyligne(int i, int j)
{
    TYPolyligneParcours tmp;
    tmp = _ListePolylines[i];
    _ListePolylines[i] = _ListePolylines[j];
    _ListePolylines[j] = tmp;
}
 
int TYSetGeometriqueParcours::SupressionPolylignesRedondantes()
{
    int nNbDoublons = 0;
    // Cette methode elimine 2 sortes de segments:
    // 1. segments bouclant sur le meme point
    // 2. segments doubles (Ex: [P1,P2] & [P2,P1])
    // Pour ce traitement, on trie la liste de polyligne de 2 facons:
    // 1. l'indice du premier point doit etre le plus faible (swap au besoin dans chaque polyligne)
    // 2. suivant la valeur du premier indice
 
    // 1. Swap des indexes de points si necessaire
    int indexPoint1 = 0, indexPoint2 = 0, i = 0, j = 0;
    for (i = 0; i < _nNbPolylines; i++)
    {
        assert(_ListePolylines[i].nombreDePoint() == 2);
        indexPoint1 = _ListePolylines[i].indexePoint1();
        indexPoint2 = _ListePolylines[i].indexePoint2();
        assert(indexPoint1 >= 0);
        assert(indexPoint2 >= 0);
        if (indexPoint1 > indexPoint2)
        {
            // Swap
            _ListePolylines[i].setPoint(0, &(_ListePoint[indexPoint2]));
            _ListePolylines[i].setPoint(1, &(_ListePoint[indexPoint1]));
        }
    }
    // 2. QSort sur les polylignes (base sur le fait que toutes les polylignes contiennent 2 points
    // exactement)
    qsort((void*)_ListePolylines, (size_t)_nNbPolylines, sizeof(TYPolyligneParcours),
          compareTYPolyligneParcours);
 
    // 3."Suppression" des segments ayant les memes indexes
    i = 0;
    j = 1;
    int nOldNbPolylines = _nNbPolylines;
    while (i < _nNbPolylines)
    {
        indexPoint1 = _ListePolylines[i].indexePoint1();
        indexPoint2 = _ListePolylines[i].indexePoint2();
        while (j < nOldNbPolylines && indexPoint1 == _ListePolylines[j].indexePoint1() &&
               indexPoint2 == _ListePolylines[j].indexePoint2())
        {
            _nNbPolylines--;
            nNbDoublons++;
            j++;
        }
        i++;
        if (i != j && j < nOldNbPolylines)
        {
            _ListePolylines[i].Copy(_ListePolylines[j]);
        }
        j++;
    }
 
    // 4."Suppression" des segments bouclant sur le meme point
    for (i = 0; i < _nNbPolylines; i++)
    {
        indexPoint1 = _ListePolylines[i].indexePoint1();
        indexPoint2 = _ListePolylines[i].indexePoint2();
        if (indexPoint1 == indexPoint2)
        {
            if (i != (_nNbPolylines - 1))
            {
                _ListePolylines[i].Copy(_ListePolylines[_nNbPolylines - 1]);
            }
            i--; // reverifier si la nouvelle n'est pas redondante
            _nNbPolylines--;
            nNbDoublons++;
        }
    }
 
    return nNbDoublons;
}
 
int TYSetGeometriqueParcours::MergePointsDoubles()
{
    int i = 0, j = 0, index = 0, doublons = 0;
    // 1. On modifie les identifiants des points doubles (on suppose qu'ils sont dans l'ordre):
    for (i = 0; i < _nNbPointTotal; i++)
    {
        for (j = i; j < _nNbPointTotal; j++)
        {
            // Ne pas merger les points appartenant a 2 types de courbes (infra & topo)
            bool bPointAppartenantAuMemeType = ((_ListePoint[i].isEcran == _ListePoint[j].isEcran) &&
                                                (_ListePoint[i].isInfra == _ListePoint[j].isInfra));
            if ((bPointAppartenantAuMemeType) && (_ListePoint[j].Identifiant > i) &&
                (TYPointParcours::Confondus(&(_ListePoint[i]), &(_ListePoint[j]))))
            {
                _ListePoint[j].Identifiant = -i; // les points inutilises ont des indexes negatifs
                doublons++;
            }
        }
    }
    // 2. On modifie les ptr sur points des polylignes:
    for (i = 0; i < _nNbPolylines; i++)
    {
        for (j = 0; j < _ListePolylines[i].nombreDePoint(); j++)
        {
            index = _ListePolylines[i].indexePoint(j);
            do // attention, le point peut faire reference a un point lui-meme doublon (donc ayant un id
               // negatif)
            {
                index = abs(index);
                index = _ListePoint[index].Identifiant;
            } while (index < 0);
            _ListePolylines[i].setPoint(j, &(_ListePoint[index]));
        }
    }
    return doublons;
}
 
void TYSetGeometriqueParcours::RamenerPointsTraversantLaFrontiere(
    TYPointParcours& Srce, TYPointParcours& Dest, int* IndexePointsFrontiere, int& NbPointsFrontiere,
    std::vector<bool>& pEstUnPointIntersectant, bool bCoteGauche, bool* PointsAGauche, bool* PointsADroite)
{
    int i = 0, indexePoint = 0, indexePoint1 = 0, indexePoint2 = 0;
    int nAncienNbPointTotal = _nNbPointTotal / 2; // cf SeparationDroiteGauche
    // Initialisation
    NbPointsFrontiere = 0;
    pEstUnPointIntersectant.clear();
    for (i = 0; i < _nNbPointTotal; i++)
    {
        pEstUnPointIntersectant.push_back(false);
    }
    for (i = 0; i < _nNbPolylines; i++)
    {
        // 1. Recherche des segments traversant [SR]
        // Attention !! On considere que les polylignes ne sont que des segments (nb point = 2).
        assert(2 == _ListePolylines[i].nombreDePoint());
        // Indexe du point dans la liste de point:
        indexePoint1 = _ListePolylines[i].indexePoint1();
        indexePoint2 = _ListePolylines[i].indexePoint2();
        // Est-ce qu'un des points est des deux cotes ?
        if (PointsAGauche[indexePoint1] == PointsADroite[indexePoint1])
        {
            // Oui le marquer
            pEstUnPointIntersectant[indexePoint1] = true;
            IndexePointsFrontiere[NbPointsFrontiere] = indexePoint1;
            NbPointsFrontiere++;
            continue;
        }
        if (PointsAGauche[indexePoint2] == PointsADroite[indexePoint2])
        {
            // Oui le marquer
            pEstUnPointIntersectant[indexePoint2] = true;
            IndexePointsFrontiere[NbPointsFrontiere] = indexePoint2;
            NbPointsFrontiere++;
            continue;
        }
        // Y a-t-il passage de frontiere ?
        bool b2PointsAGauche = PointsAGauche[indexePoint1] && PointsAGauche[indexePoint2];
        bool b2PointsADroite = PointsADroite[indexePoint1] && PointsADroite[indexePoint2];
        if (b2PointsAGauche || b2PointsADroite)
        {
            continue; // non
        }
        int nIndexePointFrontiereDansSegment = 0;
        if (bCoteGauche)
        {
            nIndexePointFrontiereDansSegment = PointsADroite[indexePoint1] ? 0 : 1;
        }
        else
        {
            nIndexePointFrontiereDansSegment = PointsAGauche[indexePoint1] ? 0 : 1;
        }
        indexePoint = _ListePolylines[i].indexePoint(nIndexePointFrontiereDansSegment);
        // Retenir l'autre point
        // 2. Modification du point donnant lieu a un point frontiere
        // Ce passage de frontiere peut donner lieu a 2 points d'intersections sur SR,
        // si une autre polyligne rejoint ce point (indexePoint) de l'autre ci��te
        //=> on cree un nouveau point ayant les memes coordonnees:
        _ListePoint[nAncienNbPointTotal] = _ListePoint[indexePoint];
        _ListePoint[nAncienNbPointTotal].Identifiant = nAncienNbPointTotal;
        // Modifier la reference dans la polyligne
        _ListePolylines[i].setPoint(nIndexePointFrontiereDansSegment, &(_ListePoint[nAncienNbPointTotal]));
        indexePoint = nAncienNbPointTotal;
        nAncienNbPointTotal++;
 
        // Marquer le point frontiere:
        IndexePointsFrontiere[NbPointsFrontiere] = indexePoint;
        pEstUnPointIntersectant[indexePoint] = true;
        // Calculer l'intersection avec [SR]:
        TYPointParcours::IntersectionDroites(Srce, Dest, _ListePoint[indexePoint1], _ListePoint[indexePoint2],
                                             _ListePoint[indexePoint]);
        NbPointsFrontiere++;
    }
}
 
void TYSetGeometriqueParcours::MarquePointsADroiteEtAGauche(TYPointParcours& Srce, TYPointParcours& Dest,
                                                            bool*& PointsAGauche, bool*& PointsADroite)
{
    // 1. Etablir une liste des points a droite, une autre de ceux a gauche
    // Rq: on a 2 listes car on prend aussi les points sur la frontiere
    // Inversion S-R si necessaire
    // bool bSAGaucheDeR = ListePointSR[0].x < ListePointSR[1].x;
    // Signe de l'angle
    // sign = (vec1.cross(vec2)._z > 0) ? -1 : 1;
    PointsAGauche = new bool[_nNbPointTotal];
    PointsADroite = new bool[_nNbPointTotal];
    TYPointParcours SR = Dest;
    SR.x -= Srce.x;
    SR.y -= Srce.y;
    for (int i = 0; i < _nNbPointTotal; i++)
    {
        // Est-ce un point racine ?
        if (_ListePoint[i].Identifiant == i)
        {
            TYPointParcours SP = _ListePoint[i];
            SP.x -= Srce.x;
            SP.y -= Srce.y;
            PointsAGauche[i] = TYPointParcours::ZCross(SR, SP) > 0;
            PointsADroite[i] = TYPointParcours::ZCross(SR, SP) < 0;
        }
        else
        {
            PointsAGauche[i] = false;
            PointsADroite[i] = false;
        }
    }
}
 
void TYSetGeometriqueParcours::SeparationDroiteGauche(bool* PointsAGauche, bool* PointsADroite,
                                                      TYSetGeometriqueParcours& geoGauche,
                                                      TYSetGeometriqueParcours& geoDroite, int compteurIter)
{
    int i = 0, j = 0, indexePoint = 0;
    // 2.  Marquer les polylignes où au moins un point est a gauche (idem pour la droite)
    bool* bAuMoinsUnPointAGauche = new bool[_nNbPolylines];
    bool* bAuMoinsUnPointADroite = new bool[_nNbPolylines];
    for (i = 0; i < _nNbPolylines; i++)
    {
        bAuMoinsUnPointAGauche[i] = false;
        bAuMoinsUnPointADroite[i] = false;
        // Cette polyligne a-t-elle au moins un point a gauche (/ droite)?
        for (j = 0; j < _ListePolylines[i].nombreDePoint() &&
                    (!bAuMoinsUnPointADroite[i] || !bAuMoinsUnPointAGauche[i]);
             j++)
        {
            indexePoint = _ListePolylines[i].indexePoint(j);
            if (indexePoint < _nNbPointTotal)
            {
                bAuMoinsUnPointAGauche[i] = bAuMoinsUnPointAGauche[i] || PointsAGauche[indexePoint];
                bAuMoinsUnPointADroite[i] = bAuMoinsUnPointADroite[i] || PointsADroite[indexePoint];
            }
        }
    }
    // 3. Les listes (geo) gauche, doite et principale doivent etre independantes
    //=>on en cree de nouvelles
    // Copie des points
    // facteur 2 : precaution due au fait que les points a ramener a la frontiere peuvent donner 2 points
    // d'intersection
    geoGauche._ListePoint = new TYPointParcours[2 * _nNbPointTotal];
    geoDroite._ListePoint = new TYPointParcours[2 * _nNbPointTotal];
    for (i = 0; i < _nNbPointTotal; i++)
    {
        geoGauche._ListePoint[i] = _ListePoint[i];
        geoDroite._ListePoint[i] = _ListePoint[i];
    }
    geoGauche._nNbPointTotal = 2 * _nNbPointTotal;
    geoDroite._nNbPointTotal = 2 * _nNbPointTotal;
    // Copie des polylignes
    geoGauche.AllouerPolylignes(_nNbPolylines);
    geoDroite.AllouerPolylignes(_nNbPolylines);
    geoGauche._nNbPolylines = 0;
    geoDroite._nNbPolylines = 0;
 
    for (i = 0; i < _nNbPolylines; i++)
    {
        // Fix issue #139
        // Source and receptor have indexes of MAX_INT and MAX_INT-1
        // They must not be processed here because it's useless and provokes outofbound access on static
        // arrays
        if (polyligneContientSouR(i))
        {
            continue;
        }
 
        if (bAuMoinsUnPointAGauche[i])
        {
            // On ajoute cette polyligne
            geoGauche._ListePolylines[geoGauche._nNbPolylines].allouer(_ListePolylines[i].nombreDePoint());
            // Copie des references de point
            for (j = 0; j < _ListePolylines[i].nombreDePoint(); j++)
            {
                // Indexe du point dans la liste de point:
                indexePoint = _ListePolylines[i].indexePoint(j);
                // Copie de la reference:
                geoGauche._ListePolylines[geoGauche._nNbPolylines].ajoutePoint(
                    j, &(geoGauche._ListePoint[indexePoint]));
            }
            geoGauche._nNbPolylines++;
        }
        if (bAuMoinsUnPointADroite[i])
        {
            // On ajoute cette polyligne
            geoDroite._ListePolylines[geoDroite._nNbPolylines].allouer(_ListePolylines[i].nombreDePoint());
            // Copie des references de point
            for (j = 0; j < _ListePolylines[i].nombreDePoint(); j++)
            {
                // Indexe du point dans la liste de point:
                indexePoint = _ListePolylines[i].indexePoint(j);
                // Copie de la reference:
                geoDroite._ListePolylines[geoDroite._nNbPolylines].ajoutePoint(
                    j, &(geoDroite._ListePoint[indexePoint]));
            }
            geoDroite._nNbPolylines++;
        }
    }
    // CherchePointsAGauche(PointsAGauche, geoGauche._ListePolylines, geoGauche._nNbPolylines,
    // geoGauche._ListePoint, geoGauche._nNbPointTotal);
    SAFE_DELETE_LIST(bAuMoinsUnPointAGauche);
    SAFE_DELETE_LIST(bAuMoinsUnPointADroite);
}
 
bool TYSetGeometriqueParcours::polyligneContientSouR(int i)
{
    bool ret = false;
    for (int j = 0; j < _ListePolylines[i].nombreDePoint(); j++)
    {
        if (_ListePolylines[i].indexePoint(j) >= _nNbPointTotal)
        {
            ret = true;
            break;
        }
    }
    return ret;
}
 
// Return Value Description for Qsort compare
//< 0 elem1 less than elem2
// 0 elem1 equivalent to elem2
//> 0 elem1 greater than elem2
int compareAbscissesCurvilignes(const void* p1, const void* p2)
{
    TYPointParcours* Srce = TYSetGeometriqueParcours::_SrceQSort;
    TYPointParcours* Dest = TYSetGeometriqueParcours::_DestQSort;
    TYPointParcours* ListePoint = TYSetGeometriqueParcours::_ListePointQSort;
    int e1 = *((int*)(p1));
    int e2 = *((int*)(p2));
    TYPointParcours& P1 = ListePoint[e1];
    TYPointParcours& P2 = ListePoint[e2];
 
    double dAbscisseCurviligneCP1 = TYPointParcours::AbscisseCurviligneCarreSurSR(P1, *Srce, *Dest);
    double dAbscisseCurviligneCP2 = TYPointParcours::AbscisseCurviligneCarreSurSR(P2, *Srce, *Dest);
 
    if (dAbscisseCurviligneCP1 < dAbscisseCurviligneCP2)
    {
        return -1;
    }
    if (dAbscisseCurviligneCP1 > dAbscisseCurviligneCP2)
    {
        return 1;
    }
    return 0;
}
 
void TYSetGeometriqueParcours::TriePointsIntersectionSuivantSR(TYPointParcours& Srce, TYPointParcours& Dest,
                                                               int* IndexePointsFrontiere,
                                                               int NbPointsFrontiere)
{
    //  int i;
    //  TYPointParcours* P;
    //  double PDist;
 
    if (NbPointsFrontiere == 0)
    {
        return;
    }
 
    /*
        for(i=0; i < NbPointsFrontiere;i++)
        {
            P = &(_ListePoint[IndexePointsFrontiere[i]]);
            if (P != NULL)
                PDist = fabs(P->x - Srce.x) + fabs(P->y-Srce.y);
        }
    */
    // Quick Sort
    TYSetGeometriqueParcours::_mutex.lock();
    TYSetGeometriqueParcours::_SrceQSort = &Srce;
    TYSetGeometriqueParcours::_DestQSort = &Dest;
    TYSetGeometriqueParcours::_ListePointQSort = _ListePoint;
    qsort((void*)IndexePointsFrontiere, (size_t)NbPointsFrontiere, sizeof(int), compareAbscissesCurvilignes);
    TYSetGeometriqueParcours::_mutex.unlock();
    // qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void
    // *elem2 ) );
 
    /*
        for(i=0; i < NbPointsFrontiere;i++)
        {
            P = &(_ListePoint[IndexePointsFrontiere[i]]);
            if (P != NULL)
                PDist = fabs(P->x - Srce.x) + fabs(P->y-Srce.y);
        }
    */
}
 
bool TYSetGeometriqueParcours::AjoutePointALaPolyLigne(int indexPolyligne, TYPointParcours& P)
{
    assert(_ListePolylines);
    assert(_ListePoint);
    // Enregistrement du point:
    _ListePoint[_nNbPointTotal] = P;
    _ListePolylines[indexPolyligne].ajoutePoint(_ListePolylines[indexPolyligne].nombreDePoint(),
                                                &(_ListePoint[_nNbPointTotal]));
    _nNbPointTotal++;
    return true;
}
 
int TYSetGeometriqueParcours::ParcourtPolyligneAPartirDe(int IndexPointRacine,
                                                         TYPolyligneParcours*& PolyligneRacine,
                                                         std::vector<bool>& pEstUnPointIntersectant,
                                                         TYSetGeometriqueParcours& geoPremierePasse)
{
    int IndexPoint = IndexPointRacine;
    int IndexPointSuivant = 0;
    // Cette methode ajoute les points rencontres sur la polyligne racine, dans le sens impose par le point
    // racine Le point racine est-il le premier ou le second point de la polyligne racine ?
    TYPolyligneParcours* PolyligneCourante = PolyligneRacine;
    TYPolyligneParcours* PolyligneSuivante = PolyligneCourante;
    do
    {
        // Memorisons la derniere polyligne non nulle:
        PolyligneRacine = PolyligneCourante;
        IndexPointSuivant = PolyligneCourante->indexePointSuivant(IndexPoint, PolyligneSuivante);
        // Enregistrer l'autre point du segment
        geoPremierePasse.AjoutePointALaPolyLigne(0, _ListePoint[IndexPointSuivant]);
        IndexPoint = IndexPointSuivant;
    } while (NULL != PolyligneSuivante && !pEstUnPointIntersectant[IndexPoint] &&
             (PolyligneCourante = PolyligneSuivante));
 
    return IndexPoint;
}
 
bool TYSetGeometriqueParcours::PolylignesInfraFermees()
{
    // Verifier que toutes les polylignes d'infra sont fermees, exceptees les ecrans
    for (int i = 0; i < _nNbPolylines; i++)
    {
        if (_ListePolylines[i].isInfra() && !_ListePolylines[i].isEcran())
        {
            if (!_ListePolylines[i].estSurUnParcourFermee())
            {
                return false;
            }
        }
    }
    return true;
}
 
bool TYSetGeometriqueParcours::ListerPointsConnexes(Connexite*& Connexes,
                                                    std::vector<bool>& pEstUnPointIntersectant)
{
    // Cette methode rempli la structure Connexes, attribut de chaque point:
    int i = 0, j = 0;
    // Initialiser la liste
    for (i = 0; i < this->_nNbPointTotal; i++)
    {
        Connexes[i].IndexesSegment[0] = -1; // Premier segment incluant ce point
        Connexes[i].IndexesSegment[1] = -1; // Second segment incluant ce point
        Connexes[i].NbSegmentsConnexes = 0; // Nb de segment incluant ce point
    }
    // Pour chaque polyligne, construire une liste de points connexes :
    // on renseigne les champs NbSegmentsConnexes & IndexesSegment
    int indexePoint = 0;
    for (i = 0; i < _nNbPolylines; i++)
    {
        assert(_ListePolylines[i].nombreDePoint() == 2);
        for (j = 0; j < _ListePolylines[i].nombreDePoint(); j++)
        {
            indexePoint = _ListePolylines[i].indexePoint(j);
            int NbSegmentsConnexes = Connexes[indexePoint].NbSegmentsConnexes;
            // A-t-on deja 2 segments connexes pour ce point ?
            if (NbSegmentsConnexes >= 2)
            {
                // Oui=>il faudrait dedoubler ce point
                TYPointParcours* _newListePoint = new TYPointParcours[_nNbPointTotal + 1];
                std::copy(_ListePoint, _ListePoint + _nNbPointTotal, _newListePoint);
                for (int a = 0; a < _nNbPolylines; a++)
                {
                    for (int b = 0; b < _ListePolylines[a].nombreDePoint(); b++)
                    {
                        int index = _ListePolylines[a].indexePoint(b);
                        _ListePolylines[a].setPoint(b, &(_newListePoint[index]));
                    }
                }
                delete[] _ListePoint;
                _ListePoint = _newListePoint;
                Connexite* newConnexes = new Connexite[_nNbPointTotal + 1];
                std::copy(Connexes, Connexes + _nNbPointTotal, newConnexes);
                delete[] Connexes;
                Connexes = newConnexes;
 
                TYPointParcours* p = &(_ListePoint[_nNbPointTotal]);
                p->isInfra = _ListePoint[indexePoint].isInfra;
                p->isEcran = _ListePoint[indexePoint].isEcran;
                p->x = _ListePoint[indexePoint].x;
                p->y = _ListePoint[indexePoint].y;
                p->z = _ListePoint[indexePoint].z;
                p->Identifiant = _nNbPointTotal;
                _ListePolylines[i].setPoint(j, p);
 
                newConnexes[_nNbPointTotal].IndexesSegment[0] = -1; // Premier segment incluant ce point
                newConnexes[_nNbPointTotal].IndexesSegment[1] = -1; // Second segment incluant ce point
                newConnexes[_nNbPointTotal].NbSegmentsConnexes = 0; // Nb de segment incluant ce point
                NbSegmentsConnexes = 0;
 
                // Fix issue #91 : array _estUnPointIntersectant must be extended
                pEstUnPointIntersectant.push_back(pEstUnPointIntersectant[indexePoint]);
 
                indexePoint = _nNbPointTotal;
                _nNbPointTotal++;
                _ListePolylines[i].indexePoint(j);
                assert(NbSegmentsConnexes < 2);
            }
            Connexes[indexePoint].IndexesSegment[NbSegmentsConnexes] = i;
            Connexes[indexePoint].NbSegmentsConnexes++;
        }
    }
    // Pour faciliter le parcours, on affecte le ptr sur les polylignes voisines de la courante
    //=> on renseigne les champs _PolyligneP0 & _PolyligneP1
    for (i = 0; i < _nNbPolylines; i++)
    {
        //_PolyligneP0 & _PolyligneP1 pointent imperativement:
        //- sur une autre polyligne que la courante
        //- sur 2 polylignes differentes (sauf si aucune polyligne voisine)
        assert(_ListePolylines[i].nombreDePoint() == 2);
        // Creons des alias de type tableau sur les voisines _PolyligneP0 & _PolyligneP1
        TYPolyligneParcours** pPolylignesVoisines[2];
        pPolylignesVoisines[0] = &(_ListePolylines[i]._PolyligneP0);
        pPolylignesVoisines[1] = &(_ListePolylines[i]._PolyligneP1);
        int NbSegmentsConnexes = Connexes[indexePoint].NbSegmentsConnexes; // verification supplementaire
 
        for (j = 0; j < 2; j++) // test enleve pour tester que pPolylignesVoisines[j] vaut bien NULL
        {
            assert((*pPolylignesVoisines[j]) == NULL); // l'initialisation devrait etre deja faite
            // On s'occupe des segments connexes au point j du segment courant
            int IndexePj = _ListePolylines[i].indexePoint(j);
            // Premier segment connexe
            int indexeSegmentj = Connexes[IndexePj].IndexesSegment[0];
            if (indexeSegmentj != i && indexeSegmentj != -1) // la voisine n'est ni la courante, ni
                                                             // inexistante
            {
                // Le premier segment connexe est un voisin acceptable
                *(pPolylignesVoisines[j]) = &(_ListePolylines[indexeSegmentj]);
            }
            else
            {
                // Testons le second segment:
                indexeSegmentj = Connexes[IndexePj].IndexesSegment[1];
                if (indexeSegmentj != i && indexeSegmentj != -1)
                // Le second segment connexe est un voisin acceptable
                {
                    *(pPolylignesVoisines[j]) = &(_ListePolylines[indexeSegmentj]);
                }
                else
                {
                    *(pPolylignesVoisines[j]) = NULL; // par securite
                }
            }
            NbSegmentsConnexes--;
        }
        // Verifions que les voisins des 2 points du segment ne sont pas les memes!
        bool bP0P1PointentSurMemePolyligne =
            (_ListePolylines[i]._PolyligneP0 == _ListePolylines[i]._PolyligneP1);
        bool bAssert = bP0P1PointentSurMemePolyligne ? (_ListePolylines[i]._PolyligneP0 == NULL) : true;
 
        assert(bAssert);
        if (!bAssert)
        {
            bAssert = true;
        }
    }
    return true;
}
 
bool TYSetGeometriqueParcours::PremierePasse(TYPointParcours& Srce, TYPointParcours& Dest,
                                             int* IndexePointsFrontiere, int NbPointsFrontiere,
                                             std::vector<bool>& pEstUnPointIntersectant, Connexite* Connexes,
                                             TYSetGeometriqueParcours& geoPremierePasse, int compteurIter)
{
 
    // Retourne false si on est enferme
    // La premiere passe consiste en la creation d'un parcours longeant toutes les polylignes intersectantes
    // 1. Ordonner les points d'intersection
 
    TriePointsIntersectionSuivantSR(Srce, Dest, IndexePointsFrontiere, NbPointsFrontiere);
 
    // 2.1 Trouver le premier point d'intersection apres S
    int i = 0;
    while (i < NbPointsFrontiere &&
           TYPointParcours::Scalaire(Srce, _ListePoint[IndexePointsFrontiere[i]], Srce, Dest) < 0)
    {
        i++;
    }
    int PremierPointIntersection = i;
    while (i < NbPointsFrontiere &&
           TYPointParcours::Scalaire(Dest, _ListePoint[IndexePointsFrontiere[i]], Dest, Srce) > 0)
    {
        i++;
    }
    int DernierPointIntersection = i;
 
    int nbPt = _nNbPointTotal;
    nbPt = 4 * _nNbPointTotal; // au pire, on parcours tout 2 fois
 
    // 3. Allouer de la memoire pour les points du trajet
    geoPremierePasse._ListePolylines = new TYPolyligneParcours[1];
    geoPremierePasse._ListePolylines[0].allouer(nbPt);
    geoPremierePasse._ListePoint = new TYPointParcours[nbPt];
    geoPremierePasse._nNbPointTotal = 0;
    geoPremierePasse._nNbPolylines = 1;
 
    // 4. Parcourir les polylignes
    geoPremierePasse.AjoutePointALaPolyLigne(0, Srce);
    for (i = PremierPointIntersection; i < DernierPointIntersection; i++)
    {
        // Le point suivant du parcourt est la prochaine intersection:
        int IndexPoint = IndexePointsFrontiere[i];
        // A quelle polyligne appartient ce point ?
        int indexPolyligne = Connexes[IndexPoint].IndexesSegment[0];
        TYPolyligneParcours* PolyligneCourante = &(_ListePolylines[indexPolyligne]);
        // Il faut parcourir cette polyligne et ses connexes pour en enregistrer les points
        // Attention au sens, car le point d'intersection peut etre le second de la polyligne
        // On enregistre pas le point racine:
        geoPremierePasse.AjoutePointALaPolyLigne(0, _ListePoint[IndexPoint]);
        IndexPoint = ParcourtPolyligneAPartirDe(IndexPoint, PolyligneCourante, pEstUnPointIntersectant,
                                                geoPremierePasse);
        // Le dernier point est-il un point d'intersection ?
        if (pEstUnPointIntersectant[IndexPoint])
        {
            // On finit par un point d'intersection
            // Est-il derriere S ?
            if (TYPointParcours::Scalaire(Srce, _ListePoint[IndexPoint], Srce, Dest) < 0)
            // Oui=>retourner faux car on est emprisonne
            {
                return false;
            }
            // Est-il devant R ?
            if (TYPointParcours::Scalaire(Dest, _ListePoint[IndexPoint], Dest, Srce) < 0)
            // Oui=>retourner faux car on est emprisonne
            {
                return false;
            }
            // On a peut etre passe d'autres points d'intersection: tant mieux !
            // Mais il faut savoir où on en est dans les points d'intersection:
            while (i < NbPointsFrontiere && IndexPoint != IndexePointsFrontiere[i])
            {
                i++;
            }
        }
        else
        {
            // On ne finit pas par un point d'intersection
            if (!PolyligneCourante->isEcran())
            {
                // TODO : return false implique qu'aucun chemin n'est valide, mais cette condition ne concerne
                // pas tous les points !
                return false; // on considere que le rayon est parti dans la nature
            }
            //=>il faut parcourir la polyligne courante dans l'autre sens
            IndexPoint = ParcourtPolyligneAPartirDe(IndexPoint, PolyligneCourante, pEstUnPointIntersectant,
                                                    geoPremierePasse);
        }
    }
    // Ajout du recepteur
    geoPremierePasse.AjoutePointALaPolyLigne(0, Dest);
    return true;
}
 
bool TYSetGeometriqueParcours::SecondePasse(TYSetGeometriqueParcours& geoPremierePasse,
                                            TYSetGeometriqueParcours& geoSecondePasse,
                                            bool bTrajetsAGaucheDeSR, TYPointParcours**& pTableauEC,
                                            int& nbPtsEC, int compteurIter, bool bIsLastSecondePasse)
{
    compteurIter++;
    int i = 0;
 
    if (!bIsLastSecondePasse && compteurIter > 2)
    {
        return false;
    }
 
    // 1. Calcul de l'EC de geoPremierePasse
    // 1.1 Recuperer les points de la premiere passe
    int nNbPointsPremierePasse = geoPremierePasse._nNbPointTotal;
 
    // XBH : 12/10/2004 - if nothing to compute, exit now!
    if (nNbPointsPremierePasse == 0)
    {
        return false;
    }
 
    TYPointParcours** TableauDePointsPremierePasse = new TYPointParcours*[nNbPointsPremierePasse];
    for (i = 0; i < nNbPointsPremierePasse; i++)
    {
        TableauDePointsPremierePasse[i] = &(geoPremierePasse._ListePoint[i]);
    }
    // calcul de l'EC de cet ensemble
    TYPointParcours** TableauDePointsEC = new TYPointParcours*[nNbPointsPremierePasse];
    int nNbPointsEC = 0;
 
    // Mettons R en seconde position dans le tableau (exige pour le calcul d'EC)
    TYPointParcours* pRecepteur = TableauDePointsPremierePasse[nNbPointsPremierePasse - 1];
    TableauDePointsPremierePasse[nNbPointsPremierePasse - 1] = TableauDePointsPremierePasse[1];
    TableauDePointsPremierePasse[1] = pRecepteur;
 
    // Sens de parcours S->R
    int indexS = 0;
    int indexR = 1;
    bool bSaGaucheDeR = TableauDePointsPremierePasse[indexS]->x < TableauDePointsPremierePasse[indexR]->x;
 
    bool premierPtsLesPlusHauts = bTrajetsAGaucheDeSR != bSaGaucheDeR;
 
    nNbPointsEC = TYSetGeometriqueParcours::EnveloppeConvexeLes2PremiersPointsEtant(
        TableauDePointsPremierePasse, nNbPointsPremierePasse, TableauDePointsEC, premierPtsLesPlusHauts);
 
    SAFE_DELETE_LIST(TableauDePointsPremierePasse);
    // 2. Parcours de l'EC, et choix du trajet sans intersection
    // 2.1. Allouer de la memoire pour les points du trajet
    int nNbPointAlloue = nNbPointsEC * nNbPointsPremierePasse * 4;
    geoSecondePasse.Clean();
    geoSecondePasse._ListePolylines = new TYPolyligneParcours[1]; // 1 seule polyligne
    geoSecondePasse._ListePolylines[0].allouer(nNbPointAlloue);   // allouer assez de points!
    geoSecondePasse._ListePoint = new TYPointParcours[nNbPointAlloue];
    geoSecondePasse._nNbPointTotal = 0;
    geoSecondePasse._nNbPolylines = 1;
    // 2.2. Ajouter les points de S vers R
    // Les points doivent etre ordonnes de S vers R
    bool bOrdonneDeSversR =
        (TableauDePointsEC[0]->Identifiant == geoPremierePasse._ListePolylines[0].indexePoint(0));
    if (!bOrdonneDeSversR)
    {
        InverseOrdreDesPoints(TableauDePointsEC, nNbPointsEC);
    }
    geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[0]);
    int nVerifNbPointsAjoutes = 1;
    int nbPts = nNbPointsEC;
    for (i = 1; i < nbPts; i++)
    {
        if (!bIsLastSecondePasse && (compteurIter < 2) &&
            this->intersects(*TableauDePointsEC[i - 1], *TableauDePointsEC[i]))
        {
            TYSetGeometriqueParcours nouvellePremierePasse;
            TYSetGeometriqueParcours nouvelleSecondePasse;
 
            // Tentative différente, si il y a un obstacle, on refait une premiere passe
            int* IndexePointsFrontiere = new int[_nNbPointTotal];
            int NbPointsFrontiere = 0;
            bool* PointsAGauche = nullptr;
            bool* PointsADroite = nullptr;
            TYPointParcours** pTableauECG = nullptr;
            TYPointParcours** pTableauECD = nullptr;
            int nbPtsECD = 0;
            int nbPtsECG = 0;
            TYSetGeometriqueParcours geoGauche;
            TYSetGeometriqueParcours geoDroite;
 
            MarquePointsADroiteEtAGauche(*TableauDePointsEC[i - 1], *TableauDePointsEC[i], PointsAGauche,
                                         PointsADroite);
            SeparationDroiteGauche(PointsAGauche, PointsADroite, geoGauche, geoDroite, false);
 
            std::vector<bool> estUnPointIntersectant;
 
            if (bTrajetsAGaucheDeSR)
            {
                geoGauche.RamenerPointsTraversantLaFrontiere(*TableauDePointsEC[i - 1], *TableauDePointsEC[i],
                                                             IndexePointsFrontiere, NbPointsFrontiere,
                                                             estUnPointIntersectant, bTrajetsAGaucheDeSR,
                                                             PointsAGauche, PointsADroite);
                Connexite* Connexes = new Connexite[geoGauche._nNbPointTotal];
                bool bOk = geoGauche.ListerPointsConnexes(Connexes, estUnPointIntersectant);
                if (!bOk)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[i]);
                    nVerifNbPointsAjoutes++;
                    SAFE_DELETE_LIST(Connexes);
                    SAFE_DELETE_LIST(pTableauECG);
                    continue;
                }
                bool bPasEnferme = geoGauche.PremierePasse(
                    *TableauDePointsEC[i - 1], *TableauDePointsEC[i], IndexePointsFrontiere,
                    NbPointsFrontiere, estUnPointIntersectant, Connexes, nouvellePremierePasse, compteurIter);
                if (!bPasEnferme)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[i]);
                    nVerifNbPointsAjoutes++;
                    SAFE_DELETE_LIST(Connexes);
                    SAFE_DELETE_LIST(pTableauECG);
                    continue;
                }
                bool bSecondePasseOk =
                    geoGauche.SecondePasse(nouvellePremierePasse, nouvelleSecondePasse, bTrajetsAGaucheDeSR,
                                           pTableauECG, nbPtsECG, compteurIter);
                if (!bSecondePasseOk)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[i]);
                    nVerifNbPointsAjoutes++;
                    SAFE_DELETE_LIST(Connexes);
                    SAFE_DELETE_LIST(pTableauECG);
                    continue;
                }
 
                int nNbPointNouvelleSecondePasse = nouvelleSecondePasse._nNbPointTotal;
                // Si on dépasse la taille allouée au tableau de points alors il faut l'étendre
                if (nVerifNbPointsAjoutes + nNbPointNouvelleSecondePasse >
                    geoSecondePasse._ListePolylines[0].getnNbPointAlloue())
                {
                    int nouvelleTaille = nVerifNbPointsAjoutes + (nbPts - i) * nNbPointNouvelleSecondePasse;
                    geoSecondePasse._ListePolylines[0].extendPtrPoints(nouvelleTaille);
                    geoSecondePasse.extendListePoint(nouvelleTaille);
                }
                for (int j = 1; j < nouvelleSecondePasse._nNbPointTotal; j++)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, nouvelleSecondePasse._ListePoint[j]);
                    nVerifNbPointsAjoutes++;
                }
                SAFE_DELETE_LIST(Connexes);
                SAFE_DELETE_LIST(pTableauECG);
            }
            else
            {
                geoDroite.RamenerPointsTraversantLaFrontiere(*TableauDePointsEC[i - 1], *TableauDePointsEC[i],
                                                             IndexePointsFrontiere, NbPointsFrontiere,
                                                             estUnPointIntersectant, bTrajetsAGaucheDeSR,
                                                             PointsAGauche, PointsADroite);
                Connexite* Connexes = new Connexite[geoDroite._nNbPointTotal];
                bool bOk = geoDroite.ListerPointsConnexes(Connexes, estUnPointIntersectant);
                if (!bOk)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[i]);
                    nVerifNbPointsAjoutes++;
                    SAFE_DELETE_LIST(Connexes);
                    SAFE_DELETE_LIST(pTableauECD);
                    continue;
                }
                bool bPasEnferme = geoDroite.PremierePasse(
                    *TableauDePointsEC[i - 1], *TableauDePointsEC[i], IndexePointsFrontiere,
                    NbPointsFrontiere, estUnPointIntersectant, Connexes, nouvellePremierePasse, compteurIter);
                if (!bPasEnferme)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[i]);
                    nVerifNbPointsAjoutes++;
                    SAFE_DELETE_LIST(Connexes);
                    SAFE_DELETE_LIST(pTableauECD);
                    continue;
                }
                bool bSecondePasseOk =
                    geoDroite.SecondePasse(nouvellePremierePasse, nouvelleSecondePasse, bTrajetsAGaucheDeSR,
                                           pTableauECD, nbPtsECD, compteurIter);
                if (!bSecondePasseOk)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[i]);
                    nVerifNbPointsAjoutes++;
                    SAFE_DELETE_LIST(Connexes);
                    SAFE_DELETE_LIST(pTableauECD);
                    continue;
                }
 
                int nNbPointNouvelleSecondePasse = nouvelleSecondePasse._nNbPointTotal;
                // Si on dépasse la taille allouée au tableau de points alors il faut l'étendre
                if (nVerifNbPointsAjoutes + nNbPointNouvelleSecondePasse >
                    geoSecondePasse._ListePolylines[0].getnNbPointAlloue())
                {
                    int nouvelleTaille = nVerifNbPointsAjoutes + (nbPts - i) * nNbPointNouvelleSecondePasse;
                    geoSecondePasse._ListePolylines[0].extendPtrPoints(nouvelleTaille);
                    geoSecondePasse.extendListePoint(nouvelleTaille);
                }
                for (int j = 1; j < nouvelleSecondePasse._nNbPointTotal; j++)
                {
                    geoSecondePasse.AjoutePointALaPolyLigne(0, nouvelleSecondePasse._ListePoint[j]);
                    nVerifNbPointsAjoutes++;
                }
 
                SAFE_DELETE_LIST(Connexes);
                SAFE_DELETE_LIST(pTableauECD);
            }
        }
        else
        {
            geoSecondePasse.AjoutePointALaPolyLigne(0, *TableauDePointsEC[i]);
            nVerifNbPointsAjoutes++;
        }
    }
 
    pTableauEC = TableauDePointsEC;
    nbPtsEC = nNbPointsEC;
    //  xbh: do not delete here as long as we returned the pointer outside this function
    //  delete [] TableauDePointsEC;
    return true;
}
 
void TYSetGeometriqueParcours::InverseOrdreDesPoints(TYPointParcours** ListeDePointsAInverser,
                                                     int nNbPointsDeLaListe)
{
    for (int i = 0; i < nNbPointsDeLaListe / 2; i++)
    {
        TYPointParcours* pTmp = ListeDePointsAInverser[nNbPointsDeLaListe - 1 - i];
        ListeDePointsAInverser[nNbPointsDeLaListe - 1 - i] = ListeDePointsAInverser[i];
        ListeDePointsAInverser[i] = pTmp;
    }
}
 
int TYSetGeometriqueParcours::AjouteLesPointsComprisEntre(TYSetGeometriqueParcours& geoPolySource,
                                                          int nIndexePoly, int nIndexeNbPremierPointAAjouter,
                                                          int nIndexeDernierPointAAjouter)
{
    int nNbPointsAjoutes = 0;
    // 1 Parcourir la polyligne source jusqu'a se positionner sur le premier point
    TYPolyligneParcours* PolyligneSource = &(geoPolySource._ListePolylines[nIndexePoly]);
 
    int i = 0;
    for (i = 0; i < PolyligneSource->nombreDePoint() &&
                PolyligneSource->indexePoint(i) != nIndexeNbPremierPointAAjouter;
         i++)
    {
        ;
    }
    for (i = i + 1; i < PolyligneSource->nombreDePoint(); i++)
    {
        TYPointParcours aTYPointParcours = PolyligneSource->point(i);
        AjoutePointALaPolyLigne(0, aTYPointParcours);
        nNbPointsAjoutes++;
        if (PolyligneSource->indexePoint(i) == nIndexeDernierPointAAjouter)
        {
            break;
        }
    }
    return nNbPointsAjoutes;
}
 
bool TYSetGeometriqueParcours::intersects(TYPointParcours& P1, TYPointParcours& P2)
{
    // On regarde les intersections avec tous les segments du set
    TYPointParcours P;
    int indexPoint1In = P1.Identifiant;
    int indexPoint2In = P2.Identifiant;
    for (int i = 0; i < _nNbPolylines; i++)
    {
        assert(_ListePolylines[i].nombreDePoint() == 2);
        int indexPoint1 = _ListePolylines[i].indexePoint1();
        int indexPoint2 = _ListePolylines[i].indexePoint2();
 
        // les 2 segments ont ils au moins un point en commun ?
        bool bMemePoint1 = (indexPoint1 == indexPoint1In) || (indexPoint1 == indexPoint2In);
        bool bMemePoint2 = (indexPoint2 == indexPoint2In) || (indexPoint2 == indexPoint1In);
        bool bMemePoints = bMemePoint1 || bMemePoint2;
 
        if (!bMemePoints)
        {
            // Non => on peut faire le test
            TYPointParcours& P3 = _ListePoint[indexPoint1];
            TYPointParcours& P4 = _ListePoint[indexPoint2];
            if (TYPointParcours::IntersectionSegments(P1, P2, P3, P4, P, true))
            // if(TYPointParcours::IntersectionSegments(P1, P2, _ListePoint[indexPoint1],
            // _ListePoint[indexPoint2], P))
            {
                return true;
            }
        }
    }
    return false;
}
 
bool TYSetGeometriqueParcours::intersects(TYSetGeometriqueParcours& geoPasse)
{
    bool ret = false;
    assert(geoPasse._nNbPolylines == 1);
    for (int i = 1; i < geoPasse._ListePolylines[0].nombreDePoint(); i++)
    {
        if (this->intersects(geoPasse._ListePoint[i - 1], geoPasse._ListePoint[i]))
        {
            ret = true;
            break;
        }
    }
    return ret;
}
 
bool TYSetGeometriqueParcours::coincideWith(TYSetGeometriqueParcours& otherGeoPasse)
{
    bool ret = false;
    assert(otherGeoPasse._nNbPolylines == 1);
    // On ne compare que des GeoParcours avec 1 Polyligne chacun et le même nombre de points
    if ((_nNbPolylines == 1) &&
        (_ListePolylines[0].nombreDePoint() == otherGeoPasse._ListePolylines[0].nombreDePoint()))
    {
        ret = true;
        for (int i = 0; i < _ListePolylines[0].nombreDePoint(); i++)
        {
            if (!(_ListePoint[i] == otherGeoPasse._ListePoint[i]))
            {
                ret = false;
                break;
            }
        }
    }
    return ret;
}
// indexePointADroite=>indexePointDuBonCote
// test du bon cote : a gauche => det >0 a droite det < 0
// texte de debug   : en dessous <-> au dessus
bool SecondVecteurADroiteDuPremier(TYPointParcours& V1, TYPointParcours& V2, double& determinant)
{
    determinant = TYPointParcours::ZCross(V1, V2);
    return (determinant < 0);
}
 
bool SecondVecteurAGaucheDuPremier(TYPointParcours& V1, TYPointParcours& V2, double& determinant)
{
    determinant = TYPointParcours::ZCross(V1, V2);
    return (determinant > 0);
}
 
int TYSetGeometriqueParcours::EnveloppeConvexeLes2PremiersPointsEtant(TYPointParcours** TableauDePoints,
                                                                      int nNbPoints,
                                                                      TYPointParcours** TableauDePointsECOut,
                                                                      bool bPremiersPointsLesPlusHauts)
{
    bool (*pDuBonCote)(TYPointParcours & V1, TYPointParcours & V2, double& determinant);
    pDuBonCote =
        bPremiersPointsLesPlusHauts ? &SecondVecteurADroiteDuPremier : &SecondVecteurAGaucheDuPremier;
 
    int nNbPointsEC = 0;
    // On teste chaque point pour voir s'il est a gauche de SP courant (en fait, si l'angle est inferieur
    // a PI) Le calcul d'enveloppe convexe suppose que les 2 premiers points sont sur l'EC, et qu'ils sont
    // les plus bas Si le premier n'est pas le plus a gauche, on swap avec le second
    bool bSaGaucheDeR = TableauDePoints[0]->x < TableauDePoints[1]->x;
    int indexS = bSaGaucheDeR ? 0 : 1;
    int indexR = bSaGaucheDeR ? 1 : 0;
 
    // Vecteur SR:
    TYPointParcours S = *(TableauDePoints[indexS]);
    TYPointParcours R = *(TableauDePoints[indexR]);
 
    // S est le premier point de l'EC:
    TableauDePointsECOut[nNbPointsEC] = TableauDePoints[indexS];
 
    nNbPointsEC++;
 
    TYPointParcours P = S;
    TYPointParcours P1 = R;
 
    int i = 0;
    TYPointParcours P2;
    TYPointParcours PP1;
    TYPointParcours PP2;
    int indexePointDuBonCote = -1;
    do
    {
        // On calcule PP1
        PP1 = TYPointParcours::vecteur2D(P, P1);
 
        // Cherchons le point le plus a gauche de PP1
        indexePointDuBonCote = -1; // on ne l'a pas encore trouve
        for (i = 2; i < nNbPoints; i++)
        {
            P2 = (*TableauDePoints[i]);
            PP2 = TYPointParcours::vecteur2D(P, P2);
            // Ne pas tester le meme point
            if (P1.Identifiant != P2.Identifiant)
            {
                double determinant = NAN; // = TYPointParcours::ZCross(PP1, PP2);
                bool bDuBonCote = (*pDuBonCote)(PP1, PP2, determinant);
                // Attention ! Lorsque les vecteurs sont colineaires, le determinant peut etre non nul
                // mais tres proche de 0.
                //=> seuil epsilon pour le determinant
                // static const double epsilonDeterminant = 1E-10;
                bool bColineraires = (fabs(determinant) < SEUIL_DETERMNANT_COLINEAIRE);
                bool bBonCandidatPourRemplacement = false;
                if (bColineraires)
                {
                    // Verifions que P2 est du meme côte que P1
                    if (TYPointParcours::Scalaire(PP1, PP2) <
                        0) // xbh: A koi sert ce test si les vecteurs sont colineaires ???
                    {
                        bBonCandidatPourRemplacement = false;
                    }
                    else
                    {
                        bBonCandidatPourRemplacement = PP2.normeCarree() > PP1.normeCarree();
                    }
                }
                else
                {
                    bBonCandidatPourRemplacement = bDuBonCote;
                }
                if (bBonCandidatPourRemplacement)
                {
                    // P2 a gauche de P1 => on remplace P1 par P2
                    P1 = P2;
                    indexePointDuBonCote = i;
                    // On recalcule PP1
                    PP1 = TYPointParcours::vecteur2D(P, P1);
                }
            }
        }
        TYPointParcours* pNouveauPointEC = NULL;
        if (indexePointDuBonCote >= 0)
        {
            // On a trouve un point plus a gauche
            pNouveauPointEC = TableauDePoints[indexePointDuBonCote];
            // Cherchons le point suivant de l'EC
            P = P1;
            P1 = R;
        }
        else
        {
            // le dernier point de l'EC est R:
            pNouveauPointEC = TableauDePoints[indexR];
        }
        // Ajoutons-le a EC
        TableauDePointsECOut[nNbPointsEC] = pNouveauPointEC;
        nNbPointsEC++;
    } while (nNbPointsEC < nNbPoints && indexePointDuBonCote >= 0);
 
    return nNbPointsEC;
}
 
int TYSetGeometriqueParcours::SelectionnePointsEntreSetRetDuCoteDeSR(TYSetGeometriqueParcours* geoSR,
                                                                     TYPointParcours** TableauDePoints,
                                                                     int nNbPoints)
{
    if (NULL == TableauDePoints || 0 == nNbPoints)
    {
        return 0;
    }
    int nNbPointsSelectiones = 2;
 
    // on ajoute les points S & R en premier:
    // ajout de S
    TableauDePoints[0] = geoSR->_ListePolylines[0].pointPtr(0);
 
    // ajout de R
    TableauDePoints[1] = geoSR->_ListePolylines[0].pointPtr(1);
 
    // Limites en X: quel est le point le plus a gauche entre S & R ?
    bool bSaGaucheDeR = TableauDePoints[0]->x < TableauDePoints[1]->x;
    TYPointParcours G, D;
    if (bSaGaucheDeR)
    {
        G = *TableauDePoints[0];
        D = *TableauDePoints[1];
    }
    else
    {
        G = *TableauDePoints[1];
        D = *TableauDePoints[0];
    }
    // Vecteur GD (Point limite Gauche & Point limite Droit)
    TYPointParcours GD = TYPointParcours::vecteur2D(G, D);
 
    int i = 0;
    TYPointParcours *p1 = nullptr, *p2 = nullptr;
    TYPointParcours p;
    int nbPts = 0;
 
    // 1. GD intersecte une des polylignes...
    bool noIntersection = true;
    for (i = 0; (i < _nNbPolylines) && (noIntersection); i++)
    {
        nbPts = _ListePolylines[i].nombreDePoint();
        for (int j = 0; (j < nbPts - 1) && (noIntersection); j++)
        {
            p1 = _ListePolylines[i].pointPtr(j);
            p2 = _ListePolylines[i].pointPtr(j + 1);
 
            if (TYPointParcours::IntersectionSegments(G, D, *p1, *p2, p))
            {
                noIntersection = false;
            }
        }
    }
 
    // Si on n'a trouve aucune intersection, il existe un trajet direct.
    if (noIntersection)
    {
        return nNbPointsSelectiones;
    }
 
    // 2. On selectionne les points interessants...
    // MinMax en largeur
    double MaxX = D.x;
    double MinX = G.x;
 
    // Comme le merge des points doubles a consistes a marquer en negatifs les points inutiles, on les
    // ecartes
    int racine = 0;
    bool bEntreSetR = false;
    TYPointParcours GP;
 
    for (i = 0; i < nNbPoints; i++)
    {
        // Est-ce un doublon ?
        int nIdentifiantRacine = _ListePoint[racine].Identifiant;
        while (i != 0 && i < nNbPoints && _ListePoint[i].Identifiant <= nIdentifiantRacine)
        {
            i++;
        }
        if (i >= nNbPoints)
        {
            break;
        }
        racine = i;
 
        bEntreSetR = (_ListePoint[i].x >= MinX && _ListePoint[i].x <= MaxX);
 
        // A gauche ?
        GP = TYPointParcours::vecteur2D(G, _ListePoint[i]);
        if (bEntreSetR && (TYPointParcours::ZCross(GD, GP) >= 0))
        {
            TableauDePoints[nNbPointsSelectiones] = &(_ListePoint[i]);
            nNbPointsSelectiones++;
        }
    }
 
    return nNbPointsSelectiones;
}
 
void TYSetGeometriqueParcours::CreerTrajetAPartirDuneListeDePointsTriee(TYPointParcours** TableauDePoints,
                                                                        int nNbPoints, bool bSens,
                                                                        bool bGardeIdentifiant)
{
    if (NULL == TableauDePoints || 0 == nNbPoints)
    {
        return;
    }
    assert(_ListePolylines == NULL);
    assert(_ListePoint == NULL);
    assert(_nNbPolylines == 0);
    assert(_nNbPointTotal == 0);
 
    // 1. Creer les points
    _ListePoint = new TYPointParcours[nNbPoints];
    _nNbPointTotal = nNbPoints;
 
    // 2. Creer la polyligne
    _ListePolylines = new TYPolyligneParcours[1];
    _nNbPolylines = 1;
    _ListePolylines[0].allouer(nNbPoints);
 
    // Copie des points
    int i = 0;
    if (bSens)
    {
        for (i = 0; i < nNbPoints; i++)
        {
            _ListePoint[i] = *TableauDePoints[i];
            _ListePolylines[0].ajoutePoint(i, &(_ListePoint[i]));
        }
        if (!bGardeIdentifiant) // a l'exterieur, on ne fait qu'un seul test...
        {
            for (i = 0; i < nNbPoints; i++)
            {
                _ListePoint[i].Identifiant = i;
            }
        }
    }
    else
    {
        for (i = 0; i < nNbPoints; i++)
        {
            _ListePoint[i] = *TableauDePoints[nNbPoints - i - 1];
            _ListePolylines[0].ajoutePoint(i, &(_ListePoint[nNbPoints - i - 1]));
        }
        if (!bGardeIdentifiant)
        {
            for (i = 0; i < nNbPoints; i++)
            {
                _ListePoint[i].Identifiant = nNbPoints - i - 1;
            }
        }
    }
}
 
bool TYSetGeometriqueParcours::AppartienneMemePolyligne(TYPointParcours* a, TYPointParcours* b,
                                                        TYPointParcours* c)
{
    OVector3D v1(b->x - a->x, b->y - a->y, 0.0f);
    OVector3D v2(c->x - b->x, c->y - b->y, 0.0f);
    TYPointParcours *p = nullptr, *pp = nullptr, *pn = nullptr;
    int nbPts = 0;
    double norme1 = NAN;
    double norme2 = NAN;
    double cosVal1 = NAN;
    double cosVal2 = NAN;
 
    bool t1 = false, t2 = false;
    t1 = t2 = false;
 
    // 1. on regarde si b appartienne a une polyligne
    for (int i = 0; i < _nNbPolylines; i++)
    {
        nbPts = _ListePolylines[i].nombreDePoint();
        for (int j = 0; j < nbPts; j++)
        {
            p = _ListePolylines[i].pointPtr(j);
 
            if (TYPointParcours::Confondus(p, b))
            {
                // On regarde si les vecteurs ab et bc sont colineaires aux segments prec et suiv
                // de la polyligne
 
                if (j > 0)
                {
                    pp = _ListePolylines[i].pointPtr(j - 1);
                    OVector3D v3(p->x - pp->x, p->y - pp->y, 0.0f);
 
                    norme1 = (v1.norme() * v3.norme());
                    cosVal1 = v1.scalar(v3) / norme1; // should be > 0
                    if (ABS(cosVal1 - 1.0f) < EPSILON_13)
                    {
                        t1 = true;
                    }
 
                    v3._x = -v3._x;
                    v3._y = -v3._y;
 
                    norme2 = (v2.norme() * v3.norme());
                    cosVal2 = v2.scalar(v3) / norme2; // should be > 0
                    if (ABS(cosVal2 - 1.0f) < EPSILON_13)
                    {
                        t2 = true;
                    }
                }
                if (j < nbPts - 1)
                {
                    pn = _ListePolylines[i].pointPtr(j + 1);
                    OVector3D v4(pn->x - p->x, pn->y - p->y, 0.0f);
 
                    norme2 = (v2.norme() * v4.norme());
                    cosVal2 = v2.scalar(v4) / norme2; // should be > 0
                    if (ABS(cosVal2 - 1.0f) < EPSILON_13)
                    {
                        t2 = true;
                    }
 
                    v4._x = -v4._x;
                    v4._y = -v4._y;
 
                    norme1 = (v1.norme() * v4.norme());
                    cosVal1 = v1.scalar(v4) / norme1; // should be > 0
                    if (ABS(cosVal1 - 1.0f) < EPSILON_13)
                    {
                        t1 = true;
                    }
                }
            }
        }
 
        if (t1 && t2)
        {
            break;
        }
    }
 
    return (t1 && t2);
}
 
bool TYSetGeometriqueParcours::extendListePoint(int nNouvelleTaille)
{
    assert(nNouvelleTaille >= _nNbPointTotal);
    TYPointParcours* newListePoint = new TYPointParcours[nNouvelleTaille];
    // Copie des points
    for (int i = 0; i < _nNbPointTotal; i++)
    {
        newListePoint[i] = this->_ListePoint[i];
    }
 
    SAFE_DELETE_LIST(this->_ListePoint);
    this->_ListePoint = newListePoint;
 
    return NULL != this->_ListePoint;
}