SaraP
117 lines
3.9 KiB
C++
117 lines
3.9 KiB
C++
//----------------------------------------------------------------------------
|
|
// EgalTech 2015-2015
|
|
//----------------------------------------------------------------------------
|
|
// File : ShortestPath.h Data : 22.12.15 Versione : 1.6l3
|
|
// Contenuto : Classe per calcolo del percorso minimo di visita di
|
|
// un insieme di oggetti.
|
|
//
|
|
//
|
|
// Modifiche : 22.12.15 DS Creazione modulo.
|
|
//
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
#pragma once
|
|
|
|
#include "/EgtDev/Include/ENkShortestPath.h"
|
|
|
|
//----------------------------------------------------------------------------
|
|
#define MAXDIST 1073741823U // 2^30 - 1 per evitare overflow
|
|
|
|
//----------------------------------------------------------------------------
|
|
struct SpPoint {
|
|
double dXi ;
|
|
double dYi ;
|
|
double dZi ;
|
|
double dHi ;
|
|
double dVi ;
|
|
double dXf ;
|
|
double dYf ;
|
|
double dZf ;
|
|
double dHf ;
|
|
double dVf ;
|
|
} ;
|
|
|
|
struct OpenBound {
|
|
int nF ;
|
|
double dX ;
|
|
double dY ;
|
|
double dZ ;
|
|
double dH ;
|
|
double dV ;
|
|
} ;
|
|
|
|
struct NODE {
|
|
NODE* pPrev ;
|
|
unsigned nPos ;
|
|
NODE* pNext ;
|
|
} ;
|
|
|
|
//----------------------------------------------------------------------------
|
|
class ShortestPath : public IShortestPath
|
|
{
|
|
public :
|
|
~ShortestPath( void) override ;
|
|
bool AddPoint( double dX, double dY) override ;
|
|
bool AddPoint( double dXi, double dYi, double dXf, double dYf) override ;
|
|
bool AddPoint( double dXi, double dYi, double dZi, double dHi, double dVi,
|
|
double dXf, double dYf, double dZf, double dHf, double dVf) override ;
|
|
bool SetOpenBound( bool bStartVsEnd, int nFlag, double dX, double dY) override ;
|
|
bool SetOpenBound( bool bStartVsEnd, int nFlag, double dX, double dY, double dZ, double dH, double dV) override ;
|
|
bool SetAngularParams( double dAngHAdd, double dAngHMul, double dAngVAdd, double dAngVMul) override ;
|
|
bool SetZzOwStep( double dStep) override ;
|
|
bool Calculate( int nType) override ;
|
|
bool GetOrder( INTVECTOR& vOrder) override ;
|
|
bool GetMinLength( double& dMinLen) override ;
|
|
|
|
public :
|
|
ShortestPath( void) ;
|
|
|
|
private :
|
|
bool Tsp( void) ;
|
|
bool CalculateImprovements( NODE* pPath) ;
|
|
void CalcDistances( void) ;
|
|
unsigned GetDistance( float dDx, float dDy, float dDz, float dDh, float dDv) ;
|
|
void PreparePath( NODE* pPath) ;
|
|
void SavePath( NODE* pPath) ;
|
|
void RestorePath( NODE* pPath) ;
|
|
long long unsigned TotalCost( NODE* pPath) ;
|
|
void UpdateOrder( NODE* pPath) ;
|
|
unsigned Index( unsigned i, unsigned j)
|
|
{ return ( i * m_nNumPnts + j) ; }
|
|
unsigned ArcCost( unsigned i, unsigned j)
|
|
{ return m_Dists[ Index( i, j)] ; }
|
|
long long unsigned NearNeighbor( void) ;
|
|
unsigned CheapArc( unsigned i) ;
|
|
long long unsigned FarNeighbor( void) ;
|
|
unsigned HighArc( unsigned i) ;
|
|
long long unsigned PointOpt( NODE* pPath) ;
|
|
long long unsigned TwoOpt( NODE* pPath) ;
|
|
long long unsigned Hybrid( NODE* pPath) ;
|
|
bool ZigZag( void) ;
|
|
long long unsigned TotalCost( void) ;
|
|
|
|
private :
|
|
static const int MAX_SPPS = 32766 ; // 2^15-2 per evitare problemi nell'allocazione di m_Dists a 32bit
|
|
|
|
private :
|
|
int m_nType ;
|
|
bool m_bSolved ;
|
|
float m_dAngHAdd ;
|
|
float m_dAngHMul ;
|
|
float m_dAngVAdd ;
|
|
float m_dAngVMul ;
|
|
float m_dStep ;
|
|
unsigned m_nNumPnts ;
|
|
SpPoint m_Points[MAX_SPPS+1] ;
|
|
unsigned m_nOrder[MAX_SPPS+1] ;
|
|
OpenBound m_ObStart ;
|
|
OpenBound m_ObEnd ;
|
|
unsigned* m_Dists ;
|
|
bool* m_Available ;
|
|
NODE* m_pMain ;
|
|
NODE* m_pDupl ;
|
|
long long unsigned m_nTotMin ;
|
|
long long unsigned m_nMinCost ;
|
|
} ;
|