//----------------------------------------------------------------------------
//  EgalTech 2014-2014
//----------------------------------------------------------------------------
// File : IntersLineLine.cpp       Data : 15.06.14          Versione : 1.5f6
// Contenuto : Implementazione della classe intersezione linea/linea.
//
//
//
// Modifiche : 15.06.14 DS Creazione modulo.
//
//
//----------------------------------------------------------------------------

//--------------------------- Include ----------------------------------------
#include "stdafx.h"
#include "IntersLineLine.h"
#include <algorithm>

using namespace std ;

//----------------------------------------------------------------------------
// Posizione del punto rispetto alla linea (+1=a destra, 0=nella banda di tolleranza, -1=a sinistra) 
static int
GetPointToLineSide( const Point3d& ptP, const Point3d& ptS, const Vector3d& vtDir, double dLenXY, double dTol)
{
   double dCross = CrossXY( ( ptP - ptS), vtDir) ;
   double dFat = ( dTol + EPS_ZERO) * dLenXY ;
   if ( dCross > dFat)
      return +1 ;
   else if ( dCross < - dFat)
      return -1 ;
   else
      return 0 ;
}

//----------------------------------------------------------------------------
IntersLineLine::IntersLineLine( const CurveLine& Line1, const CurveLine& Line2, bool bFinite)
{
  // Le intersezioni sono calcolate nel piano XY locale.

  // nessuna intersezione trovata
   m_bOverlaps = false ;
   m_nNumInters = 0 ;

  // verifico validità linee
   if ( ! Line1.IsValid()  ||  ! Line2.IsValid())
      return ;

  // se sono linee (infinite)
   if ( ! bFinite)
      IntersInfiniteLines( Line1, Line2) ;
   else
      IntersFiniteLines( Line1, Line2) ;
}

//----------------------------------------------------------------------------
void
IntersLineLine::IntersInfiniteLines( const CurveLine& Line1, const CurveLine& Line2)
{
  // linea 1 : Start, End, Direzione e Lunghezza
   Point3d ptS1 = Line1.GetStart() ;
   Point3d ptE1 = Line1.GetEnd() ;
   Vector3d vtDir1 = ptE1 - ptS1 ;
   double dLen1XY = vtDir1.LenXY() ;
   if ( dLen1XY < EPS_SMALL)
      return ;
  // linea 2 : Start, End, Direzione e Lunghezza
   Point3d ptS2 = Line2.GetStart() ;
   Point3d ptE2 = Line2.GetEnd() ;
   Vector3d vtDir2 = ptE2 - ptS2 ;
   double dLen2XY = vtDir2.LenXY() ;
   if ( dLen2XY < EPS_SMALL)
      return ;
  // prodotto vettoriale nel piano XY tra le direzioni delle linee
   double dCrossXY = CrossXY( vtDir1, vtDir2) ;

  // se le linee non sono parallele
   if ( abs( dCrossXY) > SIN_EPS_ANG_ZERO * ( dLen1XY * dLen2XY)) {
     // posizioni parametriche dell'intersezione sulle linee
      m_Info.IciA[0].dU = CrossXY( ( ptS2 - ptS1), vtDir2) / dCrossXY ;
      m_Info.IciB[0].dU = CrossXY( ( ptS2 - ptS1), vtDir1) / dCrossXY ;
     // calcolo i punti sulle due linee (possono differire in Z)
      m_Info.IciA[0].ptI = ptS1 + m_Info.IciA[0].dU * vtDir1 ;
      m_Info.IciB[0].ptI = ptS2 + m_Info.IciB[0].dU * vtDir2 ;
     // si intersecano sempre nel mezzo
      if ( CrossXY( ( ptS1 - ptS2), vtDir2) > 0) {
         m_Info.IciA[0].nPrevTy = ICCT_OUT ;
         m_Info.IciA[0].nNextTy = ICCT_IN ;
      }
      else {
         m_Info.IciA[0].nPrevTy = ICCT_IN ;
         m_Info.IciA[0].nNextTy = ICCT_OUT ;
      }
      if ( CrossXY( ( ptS2 - ptS1), vtDir1) > 0) {
         m_Info.IciB[0].nPrevTy = ICCT_OUT ;
         m_Info.IciB[0].nNextTy = ICCT_IN ;
      }
      else {
         m_Info.IciB[0].nPrevTy = ICCT_IN ;
         m_Info.IciB[0].nNextTy = ICCT_OUT ;
      }
      m_Info.bOverlap = false ;
      m_bOverlaps = false ;
      m_nNumInters = 1 ;      // una intersezione
      return ;
   }

  // se le linee sono parallele e non coincidenti
   if ( abs( CrossXY( ( ptS2 - ptS1), vtDir1)) > EPS_SMALL * dLen1XY)
      return ;        // non ci sono intersezioni

  // le linee sono parallele e coincidenti e sono infinite
   m_bOverlaps = true ;
   m_nNumInters = 0 ;       // non esistono estremi del tratto sovrapposto
}

//----------------------------------------------------------------------------
void
IntersLineLine::IntersFiniteLines( const CurveLine& Line1, const CurveLine& Line2)
{
  // verifico sovrapposizione box
   BBox3d boxL1 ;
   if ( ! Line1.GetLocalBBox( boxL1))
      return ;
   BBox3d boxL2 ;
   if ( ! Line2.GetLocalBBox( boxL2))
      return ;
   if ( ! boxL1.OverlapsXY( boxL2))
      return ;

  // segmento 1 : Start, End, Direzione e Lunghezza
   Point3d ptS1 = Line1.GetStart() ;
   Point3d ptE1 = Line1.GetEnd() ;
   Vector3d vtDir1 = ptE1 - ptS1 ;
   double dLen1XY = vtDir1.LenXY() ;
   if ( dLen1XY < EPS_SMALL)
      return ;
  // segmento 2 : Start, Direzione e Lunghezza
   Point3d ptS2 = Line2.GetStart() ;
   Point3d ptE2 = Line2.GetEnd() ;
   Vector3d vtDir2 = ptE2 - ptS2 ;
   double dLen2XY = vtDir2.LenXY() ;
   if ( dLen2XY < EPS_SMALL)
      return ;
  // posizioni estremi segmento 1 rispetto a linea 2
   int nS1Side = GetPointToLineSide( ptS1, ptS2, vtDir2, dLen2XY, EPS_SMALL) ;
   int nE1Side = GetPointToLineSide( ptE1, ptS2, vtDir2, dLen2XY, EPS_SMALL) ;
   if ( ( nS1Side == 1  &&  nE1Side == 1)  ||  ( nS1Side == -1  &&  nE1Side == -1))
      return ;
  // posizioni estremi segmento 2 rispetto a linea 1
   int nS2Side = GetPointToLineSide( ptS2, ptS1, vtDir1, dLen1XY, EPS_SMALL) ;
   int nE2Side = GetPointToLineSide( ptE2, ptS1, vtDir1, dLen1XY, EPS_SMALL) ;
   if ( ( nS2Side == 1  &&  nE2Side == 1)  ||  ( nS2Side == -1  &&  nE2Side == -1))
      return ;
  // prodotto vettoriale nel piano XY tra le direzioni delle linee
   double dCrossXY = CrossXY( vtDir1, vtDir2) ;
  // flag per linee parallele
   bool bParallel = ( abs( dCrossXY) < SIN_EPS_ANG_ZERO * ( dLen1XY * dLen2XY)) ;
  // flag per segmenti che si allontanano significativamente
   bool bFarEnds = ( nS1Side != 0  ||  nE1Side != 0  ||  nS2Side != 0  ||  nE2Side != 0) ;

  // analisi casi speciali di quasi parallelismo
   // segmento sovrapposto all'altro
   double dDist1, dDist2 ;
   if ( nS1Side == 0  ||  nE1Side == 0  ||  nS1Side == nE1Side) {
      dDist1 = CrossXY( ptS1 - ptS2, vtDir2) ;
      dDist2 = CrossXY( ptE1 - ptS2, vtDir2) ;
      if ( abs( dDist1 - dDist2) < EPS_SMALL * dLen2XY) {
         bParallel = true ;
         bFarEnds = ! ( (nS1Side == 0  &&  nE1Side == 0)  ||  (nS2Side == 0  &&  nE2Side == 0)) ;
      }
   }
   else if ( nS2Side == 0  ||  nE2Side == 0  ||  nS2Side == nE2Side) {
      dDist1 = CrossXY( ptS2 - ptS1, vtDir1) ;
      dDist2 = CrossXY( ptE2 - ptS1, vtDir1) ;
      if ( abs( dDist1 - dDist2) < EPS_SMALL * dLen1XY) {
         bParallel = true ;
         bFarEnds = ! ( (nS1Side == 0  &&  nE1Side == 0)  ||  (nS2Side == 0  &&  nE2Side == 0)) ;
      }
   }
   // estremità sovrapposte di poco
   if ( ! bParallel  &&  abs( dCrossXY) < ( 0.1 * DEGTORAD) * ( dLen1XY * dLen2XY)) {
      if (( nS1Side == 0  &&  nS2Side == 0  &&  ScalarXY( vtDir1, vtDir2) < 0  &&  ! AreSamePointXYEpsilon( ptS1, ptS2, 2 * EPS_SMALL))  ||
          ( nS1Side == 0  &&  nE2Side == 0  &&  ScalarXY( vtDir1, vtDir2) > 0  &&  ! AreSamePointXYEpsilon( ptS1, ptE2, 2 * EPS_SMALL))  ||
          ( nE1Side == 0  &&  nS2Side == 0  &&  ScalarXY( vtDir1, vtDir2) > 0  &&  ! AreSamePointXYEpsilon( ptE1, ptS2, 2 * EPS_SMALL))  ||
          ( nE1Side == 0  &&  nE2Side == 0  &&  ScalarXY( vtDir1, vtDir2) < 0  &&  ! AreSamePointXYEpsilon( ptE1, ptE2, 2 * EPS_SMALL))) {
         bParallel = true ;
         bFarEnds = false ;
      }
   }

  // se non sono paralleli e si allontanano tra loro abbastanza
   if ( ! bParallel  &&  bFarEnds) {
     // posizioni parametriche dell'intersezione sulle linee
      m_Info.IciA[0].dU = CrossXY( ( ptS2 - ptS1), vtDir2) / dCrossXY ;
      m_Info.IciB[0].dU = CrossXY( ( ptS2 - ptS1), vtDir1) / dCrossXY ;
     // verifica posizione intersezione su prima linea
      int nPos1 = ICurve::PP_NULL ;     // fuori
      if ( abs( m_Info.IciA[0].dU * dLen1XY) < EPS_SMALL)
         nPos1 = ICurve::PP_START ;     // vicino a inizio
      else if ( abs(( 1 - m_Info.IciA[0].dU) * dLen1XY) < EPS_SMALL)
         nPos1 = ICurve::PP_END ;       // vicino a fine
      else if ( m_Info.IciA[0].dU > 0  &&  m_Info.IciA[0].dU < 1)
         nPos1 = ICurve::PP_MID ;       // nell'interno
      else
         return ;
     // verifica posizione intersezione su seconda linea
      int nPos2 = ICurve::PP_NULL ;     // fuori
      if ( abs( m_Info.IciB[0].dU * dLen2XY) < EPS_SMALL)
         nPos2 = ICurve::PP_START ;     // vicino a inizio
      else if ( abs(( 1 - m_Info.IciB[0].dU) * dLen2XY) < EPS_SMALL)
         nPos2 = ICurve::PP_END ;       // vicino a fine
      else if ( m_Info.IciB[0].dU > 0  &&  m_Info.IciB[0].dU < 1)
         nPos2 = ICurve::PP_MID ;       // nell'interno
      else
         return ;
     // limito i parametri a stare sui segmenti (0...1)
      m_Info.IciA[0].dU = min( max( m_Info.IciA[0].dU, 0.), 1.) ;
      m_Info.IciB[0].dU = min( max( m_Info.IciB[0].dU, 0.), 1.) ;
     // calcolo i punti sulle due linee (possono differire in Z)
      m_Info.IciA[0].ptI = ptS1 + m_Info.IciA[0].dU * vtDir1 ;
      m_Info.IciB[0].ptI = ptS2 + m_Info.IciB[0].dU * vtDir2 ;
     // calcolo tipo di intersezione
      m_Info.IciA[0].nPrevTy = ICCT_NULL ;
      m_Info.IciA[0].nNextTy = ICCT_NULL ;
      m_Info.IciB[0].nPrevTy = ICCT_NULL ;
      m_Info.IciB[0].nNextTy = ICCT_NULL ;
      // si incontrano alle estremità, non si può dire alcunché
      if ( ( nPos1 == ICurve::PP_START  ||  nPos1 == ICurve::PP_END)  &&
           ( nPos2 == ICurve::PP_START  ||  nPos2 == ICurve::PP_END)) {
         ; // rimangono tutti NULL
      }
      // l'inizio di 1 interseca il mezzo di 2
      else if ( nPos1 == ICurve::PP_START) {
         if ( dCrossXY > 0)
            m_Info.IciA[0].nNextTy = ICCT_OUT ;      // NULL + OUT
         else
            m_Info.IciA[0].nNextTy = ICCT_IN ;       // NULL + IN
         // curva B                                     NULL + NULL
      }
      // la fine di 1 interseca il mezzo di 2
      else if ( nPos1 == ICurve::PP_END) {
         if ( dCrossXY < 0)
            m_Info.IciA[0].nPrevTy = ICCT_OUT ;      // OUT + NULL
         else
            m_Info.IciA[0].nPrevTy = ICCT_IN ;       // IN + NULL
         // curva B                                     NULL + NULL
      }
      // l'inizio di 2 interseca il mezzo di 1
      else if ( nPos2 == ICurve::PP_START) {
         // curva A                                     NULL + NULL
         if ( - dCrossXY > 0)
            m_Info.IciB[0].nNextTy = ICCT_OUT ;      // NULL + OUT
         else
            m_Info.IciB[0].nNextTy = ICCT_IN ;       // NULL + IN
      }
      // la fine di 2 interseca il mezzo di 1
      else if ( nPos2 == ICurve::PP_END) {
         // curva A                                     NULL + NULL
         if ( - dCrossXY < 0)
            m_Info.IciB[0].nPrevTy = ICCT_OUT ;      // OUT + NULL
         else
            m_Info.IciB[0].nPrevTy = ICCT_IN ;       // IN + NULL
      }
      // si intersecano nel mezzo
      else {
         if ( CrossXY( ( ptS1 - ptS2), vtDir2) > 0) {
            m_Info.IciA[0].nPrevTy = ICCT_OUT ;
            m_Info.IciA[0].nNextTy = ICCT_IN ;
         }
         else {
            m_Info.IciA[0].nPrevTy = ICCT_IN ;
            m_Info.IciA[0].nNextTy = ICCT_OUT ;
         }
         if ( CrossXY( ( ptS2 - ptS1), vtDir1) > 0) {
            m_Info.IciB[0].nPrevTy = ICCT_OUT ;
            m_Info.IciB[0].nNextTy = ICCT_IN ;
         }
         else {
            m_Info.IciB[0].nPrevTy = ICCT_IN ;
            m_Info.IciB[0].nNextTy = ICCT_OUT ;
         }
      }
      m_Info.bOverlap = false ;
      m_bOverlaps = false ;
      m_nNumInters = 1 ;
      return ;
   }

  // se le linee sono parallele e non coincidenti
   if ( bParallel  &&  bFarEnds) 
      return ;        // non ci sono intersezioni

  // le linee sono parallele e coincidenti, si cercano eventuali sovrapposizioni
   // determino se sono equiversi o controversi
   bool bEqVers = ( ScalarXY( vtDir1, vtDir2) > 0) ;
   // calcolo dei valori parametrici degli estremi del secondo segmento sul primo
   double dUmin = ScalarXY( ( ptS2 - ptS1), vtDir1) / vtDir1.SqLenXY() ;
   double dUmax = ScalarXY( ( ptE2 - ptS1), vtDir1) / vtDir1.SqLenXY() ;
   if ( ! bEqVers)
      swap( dUmin, dUmax) ;
   // estremo inferiore del primo coincide con superiore del secondo -> un punto estremo
   if ( ( dUmax * vtDir1).IsSmall()) {
      m_Info.IciA[0].dU = 0 ;
      m_Info.IciB[0].dU = ( bEqVers ? 1 : 0) ;
      m_Info.IciA[0].ptI = ptS1 + m_Info.IciA[0].dU * vtDir1 ;
      m_Info.IciB[0].ptI = ptS2 + m_Info.IciB[0].dU * vtDir2 ;
      m_Info.IciA[0].nPrevTy = ICCT_NULL ;
      m_Info.IciA[0].nNextTy = ICCT_NULL ;
      m_Info.IciB[0].nPrevTy = ICCT_NULL ;
      m_Info.IciB[0].nNextTy = ICCT_NULL ;
      m_Info.bOverlap = false ;
      m_bOverlaps = false ;
      m_nNumInters = 1 ;
      return ;
   }
   // estremo superiore del primo coincide con inferiore del secondo -> un punto estremo
   else if ( ( ( 1 - dUmin) * vtDir1).IsSmall()) {
      m_Info.IciA[0].dU = 1 ;
      m_Info.IciB[0].dU = ( bEqVers ? 0 : 1) ;
      m_Info.IciA[0].ptI = ptS1 + m_Info.IciA[0].dU * vtDir1 ;
      m_Info.IciB[0].ptI = ptS2 + m_Info.IciB[0].dU * vtDir2 ;
      m_Info.IciA[0].nPrevTy = ICCT_NULL ;
      m_Info.IciA[0].nNextTy = ICCT_NULL ;
      m_Info.IciB[0].nPrevTy = ICCT_NULL ;
      m_Info.IciB[0].nNextTy = ICCT_NULL ;
      m_Info.bOverlap = false ;
      m_bOverlaps = false ;
      m_nNumInters = 1 ;
      return ;
   }
   // esterni -> nessuna intersezione
   else if ( dUmax < 0  ||  1 < dUmin) {
      return ;
   }
   // altrimenti si sovrappongono -> tratto comune
   else {
     // devo prendere il massimo dei minimi
      if ( dUmin > 0) {
         m_Info.IciA[0].dU = dUmin ;
         m_Info.IciB[0].dU = ( bEqVers ? 0 : 1) ;
      }
      else {
         m_Info.IciA[0].dU = 0 ;
         m_Info.IciB[0].dU = ScalarXY( ( ptS1 - ptS2), vtDir2) / vtDir2.SqLenXY() ;
      }
      m_Info.IciA[0].ptI = ptS1 + m_Info.IciA[0].dU * vtDir1 ;
      m_Info.IciB[0].ptI = ptS2 + m_Info.IciB[0].dU * vtDir2 ;
      m_Info.IciA[0].nPrevTy = ICCT_NULL ;
      m_Info.IciA[0].nNextTy = ICCT_ON ;
      if ( bEqVers) {
         m_Info.IciB[0].nPrevTy = ICCT_NULL ;
         m_Info.IciB[0].nNextTy = ICCT_ON ;
      }
      else {
         m_Info.IciB[0].nPrevTy = ICCT_ON ;
         m_Info.IciB[0].nNextTy = ICCT_NULL ;
      }
     // e il minimo dei massimi
      if ( dUmax < 1) {
         m_Info.IciA[1].dU = dUmax ;
         m_Info.IciB[1].dU = ( bEqVers ? 1 : 0) ;
      }
      else {
         m_Info.IciA[1].dU = 1 ;
         m_Info.IciB[1].dU = ScalarXY( ( ptS1 + vtDir1 - ptS2), vtDir2) / vtDir2.SqLenXY() ;
      }
      m_Info.IciA[1].ptI = ptS1 + m_Info.IciA[1].dU * vtDir1 ;
      m_Info.IciB[1].ptI = ptS2 + m_Info.IciB[1].dU * vtDir2 ;
      m_Info.IciA[1].nPrevTy = ICCT_ON ;
      m_Info.IciA[1].nNextTy = ICCT_NULL ;
      if ( bEqVers) {
         m_Info.IciB[1].nPrevTy = ICCT_ON ;
         m_Info.IciB[1].nNextTy = ICCT_NULL ;
      }
      else {
         m_Info.IciB[1].nPrevTy = ICCT_NULL ;
         m_Info.IciB[1].nNextTy = ICCT_ON ;
      }
      m_Info.bOverlap = true ;
      m_Info.bCBOverEq = bEqVers ;
      m_bOverlaps = true ;
      m_nNumInters = 1 ;
      return ;
   }
}