/*******************************************************************************
+
+  LEDA 3.5
+
+  triv_segments.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

typedef void (*rep_int_func) (const SEGMENT&, const SEGMENT&);

void TRIVIAL_SEGMENTS(const list<SEGMENT>& L,  rep_int_func report_intersection)
{
  POINT inter;

  int N = L.length();

  if (N == 0) return;

  SEGMENT* A = new SEGMENT[N];
  SEGMENT* p = A;

  SEGMENT s;
  forall(s,L) *p++ = s;

  SEGMENT* stop = p;
  
  for(SEGMENT* a = A; a < stop; a++ )
  { 
    POINT as = a->source();
    POINT at = a->target();

    for(SEGMENT* b = a+1; b < stop; b++ )
    { 
      POINT bs = b->source();
      POINT bt = b->target();

      int o1 = orientation(*a,bs); 
      int o2 = orientation(*a,bt);

      if (o1 == o2 && ( o1 != 0 || o2 != 0)) continue;

      int o3 = orientation(*b,as); 
      int o4 = orientation(*b,at);
	
      if (o1 == 0 && o2 == 0 && o3 == 0 && o4 == 0)
        { 
          if ( compare(as,at) > 0 )
          { at = a->source(); 
            as = a->target(); 
           }

          if ( compare(bs,bt) > 0 )
          { bt = b->source(); 
            bs = b->target(); 
           }
          
          if ((compare(as,bs) <= 0 && compare(at,bs) >= 0) || 
              (compare(bs,as) <= 0 && compare(bt,as) >= 0) )
             report_intersection(*a,*b);
         }
       else
         if (o1 != o2 && o3 != o4) report_intersection(*a,*b);
      }
   }

  delete[] A;
}

