home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / src / plane_alg / triv_segments.c < prev    next >
Text File  |  1996-09-03  |  2KB  |  79 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  triv_segments.c
  6. +
  7. +  This file is part of the LEDA research version (LEDA-R) that can be 
  8. +  used free of charge in academic research and teaching. Any commercial
  9. +  use of this software requires a license which is distributed by the
  10. +  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
  11. +  (fax +49 681 31104).
  12. +
  13. +  Copyright (c) 1991-1996  by  Max-Planck-Institut fuer Informatik
  14. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  15. +  All rights reserved.
  16. + 
  17. *******************************************************************************/
  18.  
  19. typedef void (*rep_int_func) (const SEGMENT&, const SEGMENT&);
  20.  
  21. void TRIVIAL_SEGMENTS(const list<SEGMENT>& L,  rep_int_func report_intersection)
  22. {
  23.   POINT inter;
  24.  
  25.   int N = L.length();
  26.  
  27.   if (N == 0) return;
  28.  
  29.   SEGMENT* A = new SEGMENT[N];
  30.   SEGMENT* p = A;
  31.  
  32.   SEGMENT s;
  33.   forall(s,L) *p++ = s;
  34.  
  35.   SEGMENT* stop = p;
  36.   
  37.   for(SEGMENT* a = A; a < stop; a++ )
  38.   { 
  39.     POINT as = a->source();
  40.     POINT at = a->target();
  41.  
  42.     for(SEGMENT* b = a+1; b < stop; b++ )
  43.     { 
  44.       POINT bs = b->source();
  45.       POINT bt = b->target();
  46.  
  47.       int o1 = orientation(*a,bs); 
  48.       int o2 = orientation(*a,bt);
  49.  
  50.       if (o1 == o2 && ( o1 != 0 || o2 != 0)) continue;
  51.  
  52.       int o3 = orientation(*b,as); 
  53.       int o4 = orientation(*b,at);
  54.     
  55.       if (o1 == 0 && o2 == 0 && o3 == 0 && o4 == 0)
  56.         { 
  57.           if ( compare(as,at) > 0 )
  58.           { at = a->source(); 
  59.             as = a->target(); 
  60.            }
  61.  
  62.           if ( compare(bs,bt) > 0 )
  63.           { bt = b->source(); 
  64.             bs = b->target(); 
  65.            }
  66.           
  67.           if ((compare(as,bs) <= 0 && compare(at,bs) >= 0) || 
  68.               (compare(bs,as) <= 0 && compare(bt,as) >= 0) )
  69.              report_intersection(*a,*b);
  70.          }
  71.        else
  72.          if (o1 != o2 && o3 != o4) report_intersection(*a,*b);
  73.       }
  74.    }
  75.  
  76.   delete[] A;
  77. }
  78.  
  79.