#include <math.h>
#include <stdlib.h>
#include <windows.h>
#include "graph.h"


VECTOR &GRAPH::RandomForce(NODE &node)
{
  // We need a random impulse [ - RAND_CONSTANT ... + RAND_CONSTANT ]
  // Range should be approx. [ - 1/4 ... + 1/4 ] of desired edge length.
  
  double r = rand();  r = r / RAND_MAX - 0.5;   // - 0.5 ... 0.5
  double x = 2.0 * r * maxRandom;

  r = rand();  r = r / RAND_MAX - 0.5;   // - 0.5 ... 0.5
  double y = r * maxRandom;
  
  if (iteration > 500) {
      x = 0.0;
      y = 0.0;  
  }


  return *new VECTOR(x, y);
}



int GRAPH::Intersect(NODE &node)
{
  int i, k;   double s, t;
  
  for (i = 0;  i < node.n;  i++) 
  {
    EDGE *e1 = node.edges[i];
    
    for (NODE *n2 = First();  n2;  n2 = n2->Next())
    {    
      if (n2 == & node)
        continue;
      
      for (k = 0;  k < n2->n;  k++)
      {
        EDGE *e2 = n2->edges[k];

        if (e1 == e2)
          continue;

        if (e2->SourceNode() == e1->SourceNode() || e2->TargetNode() == e1->SourceNode() ||
            e2->SourceNode() == e1->TargetNode() || e2->TargetNode() == e1->TargetNode()   ) 
          continue;
        
        
        if (Intersect(e1->SourceNode()->Center(), e1->TargetNode()->Center(),        
                      e2->SourceNode()->Center(), e2->TargetNode()->Center(), s, t) == 1) {
        // Beep(900, 100);  Beep(600, 120);
          return TRUE;
        }
      }                         
    }
  }
  return FALSE;
}

int GRAPH::Intersect(const VECTOR &p1, const VECTOR &p2, const VECTOR &p3, const VECTOR &p4, double &s, double &t)
{
    double  D, Dt, Ds;
    double  LS_s, LS_t;

    D  = -(p2.x - p1.x)*(p4.y - p3.y) + (p2.y - p1.y)*(p4.x - p3.x);
    Dt =  (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
    Ds = -(p3.x - p1.x)*(p4.y - p3.y) + (p3.y - p1.y)*(p4.x - p3.x);

    if (fabs(D) < D_EPS)
    {
        s = -1.;
        t = -1.;
        return -1;
    }

    LS_s = s = Ds/D;
    LS_t = t = Dt/D;

    if ( (LS_t < -D_EPS) || (LS_t > 1. + D_EPS) ||
         (LS_s < -D_EPS) || (LS_s > 1. + D_EPS) )
        return 0;

    return 1;
}