EgtNumKernel/ShortestPathZigZag.cpp

//----------------------------------------------------------------------------
//  EgalTech 2015-2015
//----------------------------------------------------------------------------
// File : ShortestPathZigZag.cpp      Data : 22.12.15        Versione : 1.6l4
// Contenuto : Calcolo del percorso minimo per strisce parallele.
//             Le coordinate di inizio e fine di ogni punto sono considerate
//             coincidenti.
//
//
// Modifiche : 22.12.15 DS Creazione modulo.
//
//
//----------------------------------------------------------------------------

//--------------------------- Include ----------------------------------------
#include "stdafx.h"
#include "DllMain.h"
#include "ShortestPath.h"
#include "/EgtDev/Include/EGnStringUtils.h"

using namespace std ;

//----------------------------------------------------------------------------
#if defined( _DEBUG)
   #define MY_LOG(szOut)     LOG_INFO( GetENkLogger(), szOut) ;
#else
   #define MY_LOG(szOut)     ;
#endif

//----------------------------------------------------------------------------
enum { SORT_NONE = 0,
       SORT_X_INC = 1,
       SORT_X_DEC = 2,
       SORT_Y_INC = 3,
       SORT_Y_DEC = 4} ;
const double LIN_TOL = 0.1 ; 

//----------------------------------------------------------------------------
int
GetMainSort( int nType)
{
   switch ( nType) {
   case IShortestPath::SP_ZIGZAG_X :
   case IShortestPath::SP_ONEWAY_XP :
   case IShortestPath::SP_ONEWAY_XM :
      return SORT_Y_INC ;
   case IShortestPath::SP_ZIGZAG_Y :
   case IShortestPath::SP_ONEWAY_YP :
   case IShortestPath::SP_ONEWAY_YM :
      return SORT_X_INC ;
   default :
      return SORT_NONE ;
   }
}

//----------------------------------------------------------------------------
int
GetStepSort( int nType, int nPrevSort)
{
   switch ( nType) {
   case IShortestPath::SP_ZIGZAG_X :
      return ( nPrevSort == SORT_X_INC) ? SORT_X_DEC : SORT_X_INC ;
   case IShortestPath::SP_ZIGZAG_Y :
      return ( nPrevSort == SORT_Y_INC) ? SORT_Y_DEC : SORT_Y_INC ;
   case IShortestPath::SP_ONEWAY_XP :
      return SORT_X_INC ;
   case IShortestPath::SP_ONEWAY_XM :
      return SORT_X_DEC ;
   case IShortestPath::SP_ONEWAY_YP :
      return SORT_Y_INC ;
   case IShortestPath::SP_ONEWAY_YM :
      return SORT_Y_DEC ;
   default :
      return SORT_NONE ;
   }
}

//----------------------------------------------------------------------------
void 
SortPaths( SpPoint aPoints[], unsigned aIndices[], unsigned nNumPnts, int nSort)
{
  // Bubble sort
   for ( unsigned i = 0 ; i < nNumPnts ; ++ i) {
      for ( unsigned j = nNumPnts - 1 ; j > i ; -- j) {
         bool bSwap = false ;
         switch ( nSort) {
         default:
         case SORT_X_INC :
            if ( abs( aPoints[aIndices[j]].dXi - aPoints[aIndices[j - 1]].dXi) < LIN_TOL)
               bSwap = ( aPoints[aIndices[j]].dYi < aPoints[aIndices[j - 1]].dYi) ;
            else
               bSwap = ( aPoints[aIndices[j]].dXi < aPoints[aIndices[j - 1]].dXi) ;
            break ;
         case SORT_X_DEC :
            if ( abs( aPoints[aIndices[j]].dXi - aPoints[aIndices[j - 1]].dXi) < LIN_TOL)
               bSwap = ( aPoints[aIndices[j]].dYi < aPoints[aIndices[j - 1]].dYi) ;
            else
               bSwap = ( aPoints[aIndices[j]].dXi > aPoints[aIndices[j - 1]].dXi + LIN_TOL) ;
            break ;
         case SORT_Y_INC :
            if ( abs( aPoints[aIndices[j]].dYi - aPoints[aIndices[j - 1]].dYi) < LIN_TOL)
               bSwap = ( aPoints[aIndices[j]].dXi < aPoints[aIndices[j - 1]].dXi) ;
            else
               bSwap = ( aPoints[aIndices[j]].dYi < aPoints[aIndices[j - 1]].dYi) ;
            break ;
         case SORT_Y_DEC :
            if ( abs( aPoints[aIndices[j]].dYi - aPoints[aIndices[j - 1]].dYi) < LIN_TOL)
               bSwap = ( aPoints[aIndices[j]].dXi < aPoints[aIndices[j - 1]].dXi) ;
            else
               bSwap = ( aPoints[aIndices[j]].dYi > aPoints[aIndices[j - 1]].dYi) ;
            break ;
         }
         if ( bSwap)
            swap( aIndices[j], aIndices[j - 1]) ;
      }
   }
}

//----------------------------------------------------------------------------
bool
ShortestPath::ZigZag( void)
{
  // Almeno un punto
   if ( m_nNumPnts < 1)
      return false ;

  // Ordino i percorsi secondo la direzione di avanzamento principale 
   int nSort = GetMainSort( m_nType) ;
   for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i)
      m_nOrder[i] = i ;
   SortPaths( m_Points, m_nOrder, m_nNumPnts, nSort) ;

   bool bGroupOnX = ( nSort == SORT_X_INC) ;

  // Fino a quando non ho ordinato tutti percorsi 
   unsigned nCount = 0 ;
   unsigned i = 0 ;
   nSort  = GetStepSort( m_nType, SORT_NONE) ; 
   while ( nCount < m_nNumPnts) {

     // Cerco i percorsi che appartengono al range 
      if ( bGroupOnX) {
         double dRange = m_Points[m_nOrder[nCount]].dXi + m_dStep ;
         for ( i = nCount + 1 ; i < m_nNumPnts && m_Points[m_nOrder[i]].dXi < dRange - LIN_TOL ; ++ i)
            ;
      }
      else {
         double dRange = m_Points[m_nOrder[nCount]].dYi + m_dStep ;
         for ( i = nCount + 1 ; i < m_nNumPnts && m_Points[m_nOrder[i]].dYi < dRange - LIN_TOL ; ++ i)
            ;
      }

     // Ordino i percorsi trovati 
      SortPaths( m_Points, &m_nOrder[nCount], i - nCount, nSort) ;

      nCount = i ;
      nSort  = GetStepSort( m_nType, nSort) ; 
   }

  // ne calcolo il risultato
   m_nMinCost = TotalCost() ;
   string sOut = "-- ZigZag/OneWay : TotalCost = " + to_string( m_nMinCost) ;
   MY_LOG( sOut.c_str()) ;

   return true ;
}

//----------------------------------------------------------------------------
long long unsigned 
ShortestPath::TotalCost( void) 
{
   long long unsigned nCost = 0 ;
  // ciclo sui nodi
   for ( unsigned i = 1 ; i < m_nNumPnts ; ++ i) {
      double dDx = m_Points[m_nOrder[i]].dXi - m_Points[m_nOrder[i-1]].dXi ;
      double dDy = m_Points[m_nOrder[i]].dYi - m_Points[m_nOrder[i-1]].dYi ;
      double dDz = m_Points[m_nOrder[i]].dZi - m_Points[m_nOrder[i-1]].dZi ;
      nCost += (long long unsigned)( sqrt( dDx * dDx + dDy * dDy + dDz * dDz)) ;
   }
   return nCost ;
}