svd_arrangement_type_c2.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 665 行 · 第 1/2 页

// Copyright (c) 2003,2004  INRIA Sophia-Antipolis (France) and
// Notre Dame University (U.S.A.).  All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $Source: /CVSROOT/CGAL/Packages/Segment_Voronoi_diagram_2/include/CGAL/predicates/Svd_arrangement_type_C2.h,v $
// $Revision: 1.9 $ $Date: 2004/08/13 16:55:51 $
// $Name:  $
//
// Author(s)     : Menelaos Karavelas <[e-mail]>




#ifndef CGAL_SVD_ARRANGEMENT_TYPE_C2_H
#define CGAL_SVD_ARRANGEMENT_TYPE_C2_H

#include <CGAL/enum.h>
#include <CGAL/determinant.h>
#include <CGAL/predicates/Svd_basic_predicates_C2.h>
#include <CGAL/predicates/Svd_are_same_points_C2.h>
#include <CGAL/predicates/Svd_are_same_segments_C2.h>

#include <iostream>

CGAL_BEGIN_NAMESPACE

namespace CGALi {
  struct Svd_arrangement_enum {
    enum Arrangement_type {
      DISJOINT = 0, // obvious
      TOUCH_1, // (p1,p2) and q, and p1 and q are identical
      TOUCH_2, // (p1,p2) and q, and p2 and q are identical
      TOUCH_11, // (p1,p2), (q1,q2), and p1, q1 are identical
      TOUCH_12, // (p1,p2), (q1,q2), and p1, q2 are identical
      TOUCH_21, // (p1,p2), (q1,q2), and p2, q1 are identical
      TOUCH_22, // (p1,p2), (q1,q2), and p2, q2 are identical
      CROSSING, // two segments intersecting at interior points
      IDENTICAL, // either two segments or two points that are identical
      INTERIOR_1, // (p1,p2) and (q1,q2), and q1, q2 are interior
                  // points of (p1,p2)
      INTERIOR_2, // (p1,p2) and (q1,q2), and p1, p2 are interior
                  // points of (q1,q2)
      INTERIOR,  // (p1,p2) and q, and q is an interior point of (p1,p2)
      TOUCH_11_INTERIOR_1, // (p1,p2) and (q1,q2), and p1, q1 are
			   // identical and q2 is an interior point of (p1,p2)
      TOUCH_11_INTERIOR_2, // (p1,p2) and (q1,q2), and p1, q1 are
			   // identical and p2 is an interior point of
			   // (q1,q2)
      TOUCH_12_INTERIOR_1, // (p1,p2) and (q1,q2), and p1, q2 are
                           // identical and q1 is an interior point of (p1,p2)
      TOUCH_12_INTERIOR_2, // (p1,p2) and (q1,q2), and p1, q2 are
			   // identical and p2 is an interior point of (q1,q2)
      TOUCH_21_INTERIOR_1, // (p1,p2) and (q1,q2), and p2, q1 are
			   // identical and q2 is an interior point of (p1,p2)
      TOUCH_21_INTERIOR_2, // (p1,p2) and (q1,q2), and p2, q1 are
  			   // identical and p1 is an interior point of (q1,q2)
      TOUCH_22_INTERIOR_1, // (p1,p2) and (q1,q2), and p2, q2 are
			   // identical and q1 is an interior point of (p1,p2)
      TOUCH_22_INTERIOR_2, // (p1,p2) and (q1,q2), and p2, q2 are
		           // identical and p1 is an interior point of (q1,q2)
      OVERLAPPING_11, // (p1,p2) and (q1,q2), and (p1,q1) is the overlap
      OVERLAPPING_12, // (p1,p2) and (q1,q2), and (p1,q1) is the overlap
      OVERLAPPING_21, // (p1,p2) and (q1,q2), and (p2,q1) is the overlap
      OVERLAPPING_22, // (p1,p2) and (q1,q2), and (p2,q2) is the overlap
      TOUCH_INTERIOR_12, // (p1,p2) and (q1,q2) and p1 is an interior
                         //  point of (q1,q2)
      TOUCH_INTERIOR_22, // (p1,p2) and (q1,q2) and p2 is an interior
                         //  point of (q1,q2)
      TOUCH_INTERIOR_11, // (p1,p2) and (q1,q2) and q1 is an interior
                         //  point of (p1,p2)
      TOUCH_INTERIOR_21  // (p1,p2) and (q1,q2) and q2 is an interior
                         //  point of (p1,p2)
    };


    static Arrangement_type opposite(const Arrangement_type& at) {
      // this returns the result if we swap the order of the arguments...
      if ( at == TOUCH_12 ) {
	return TOUCH_21;
      } else if ( at == TOUCH_21 ) {
	return TOUCH_12;
      } else if ( at == INTERIOR_1 ) {
	return INTERIOR_2;
      } else if ( at == INTERIOR_2 ) {
	return INTERIOR_1;
      } else if ( at == TOUCH_11_INTERIOR_1 ) {
	return TOUCH_11_INTERIOR_2;
      } else if ( at == TOUCH_11_INTERIOR_2 ) {
	return TOUCH_11_INTERIOR_1;
      } else if ( at == TOUCH_12_INTERIOR_1 ) {
	return TOUCH_21_INTERIOR_2;
      } else if ( at == TOUCH_12_INTERIOR_2 ) {
	return TOUCH_21_INTERIOR_1;
      } else if ( at == TOUCH_21_INTERIOR_1 ) {
	return TOUCH_12_INTERIOR_2;
      } else if ( at == TOUCH_21_INTERIOR_2 ) {
	return TOUCH_12_INTERIOR_1;
      } else if ( at == TOUCH_22_INTERIOR_1 ) {
	return TOUCH_22_INTERIOR_2;
      } else if ( at == TOUCH_22_INTERIOR_2 ) {
	return TOUCH_22_INTERIOR_1;
      } else if ( at == OVERLAPPING_12 ) {
	return OVERLAPPING_21;
      } else if ( at == OVERLAPPING_21 ) {
	return OVERLAPPING_12;
      } else if ( at == TOUCH_INTERIOR_12 ) {
	return TOUCH_INTERIOR_11;
      } else if ( at == TOUCH_INTERIOR_22 ) {
	return TOUCH_INTERIOR_21;
      } else if ( at == TOUCH_INTERIOR_11 ) {
	return TOUCH_INTERIOR_12;
      } else if ( at == TOUCH_INTERIOR_21 ) {
	return TOUCH_INTERIOR_22;
      }
      return at;
    }
  };

  std::ostream& operator<<(std::ostream& os,
			   const Svd_arrangement_enum::Arrangement_type&
			   at)
  {
    typedef Svd_arrangement_enum AT;

    if ( at == AT::DISJOINT ) {
      os << "DISJOINT";
    } else if ( at == AT::TOUCH_1 ) {
      os << "TOUCH_1";
    } else if ( at == AT::TOUCH_2 ) {
      os << "TOUCH_2";
    } else if ( at == AT::TOUCH_11 ) {
      os << "TOUCH_11";
    } else if ( at == AT::TOUCH_12 ) {
      os << "TOUCH_12";
    } else if ( at == AT::TOUCH_21 ) {
      os << "TOUCH_21";
    } else if ( at == AT::TOUCH_22 ) {
      os << "TOUCH_22";
    } else if ( at == AT::CROSSING ) {
      os << "CROSSING";
    } else if ( at == AT::IDENTICAL) {
      os << "IDENTICAL";
    } else if ( at == AT::INTERIOR_1 ) {
      os << "INTERIOR_1";
    } else if ( at == AT::INTERIOR_2 ) {
      os << "INTERIOR_2";
    } else if ( at == AT::INTERIOR ) {
      os << "INTERIOR";
    } else if ( at == AT::TOUCH_11_INTERIOR_1 ) {
      os << "TOUCH_11_INTERIOR_1";
    } else if ( at == AT::TOUCH_11_INTERIOR_2 ) {
      os << "TOUCH_11_INTERIOR_2";
    } else if ( at == AT::TOUCH_12_INTERIOR_1 ) {
      os << "TOUCH_12_INTERIOR_1";
    } else if ( at == AT::TOUCH_12_INTERIOR_2 ) {
      os << "TOUCH_12_INTERIOR_2";
    } else if ( at == AT::TOUCH_21_INTERIOR_1 ) {
      os << "TOUCH_21_INTERIOR_1";
    } else if ( at == AT::TOUCH_21_INTERIOR_2 ) {
      os << "TOUCH_21_INTERIOR_2";
    } else if ( at == AT::TOUCH_22_INTERIOR_1 ) {
      os << "TOUCH_22_INTERIOR_1";
    } else if ( at == AT::TOUCH_22_INTERIOR_2 ) {
      os << "TOUCH_22_INTERIOR_2";
    } else if ( at == AT::OVERLAPPING_11 ) {
      os << "OVERLAPPING_11";
    } else if ( at == AT::OVERLAPPING_12 ) {
      os << "OVERLAPPING_12";
    } else if ( at == AT::OVERLAPPING_21 ) {
      os << "OVERLAPPING_21";
    } else if ( at == AT::OVERLAPPING_22 ) {
      os << "OVERLAPPING_22";
    } else if ( at == AT::TOUCH_INTERIOR_11 ) {
      os << "TOUCH_INTERIOR_11";
    } else if ( at == AT::TOUCH_INTERIOR_12 ) {
      os << "TOUCH_INTERIOR_12";
    } else if ( at == AT::TOUCH_INTERIOR_21 ) {
      os << "TOUCH_INTERIOR_21";
    } else if ( at == AT::TOUCH_INTERIOR_22 ) {
      os << "TOUCH_INTERIOR_22";
    } else {
      CGAL_assertion( false );
    }

    return os;
  }

} // namespace CGALi

//---------------------------------------------------------------------

template<class RT>
typename CGALi::Svd_arrangement_enum::Arrangement_type
svd_arrangement_type_ftC2(const RT& x1, const RT& y1,
			  const RT& x2, const RT& y2,
			  const RT& x3, const RT& y3,
			  const RT& x4, const RT& y4)
{
  typedef CGALi::Svd_arrangement_enum Enum;

  RT delta = -det2x2_by_formula(x2 - x1, x4 - x3, y2 - y1, y4 - y3);

  Sign s = CGAL::sign( delta );
  if ( s != CGAL::ZERO ) {
    return svd_arrangement_type_non_parallel_C2(x1, y1, x2, y2,
    						x3, y3, x4, y4, delta);
  } else {
    return svd_arrangement_type_parallel_C2(x1, y1, x2, y2,
					    x3, y3, x4, y4);
  }
}


//---------------------------------------------------------------------

template<class RT>
typename CGALi::Svd_arrangement_enum::Arrangement_type
svd_arrangement_type_non_parallel_C2(const RT& x1, const RT& y1,
				     const RT& x2, const RT& y2,
				     const RT& x3, const RT& y3,
				     const RT& x4, const RT& y4,
				     const RT& D)
{
  typedef CGALi::Svd_arrangement_enum Enum;

  RT Dt = -det2x2_by_formula(x3 - x1, x4 - x3,
			     y3 - y1, y4 - y3);

  RT Ds = det2x2_by_formula(x2 - x1, x3 - x1,
			    y2 - y1, y3 - y1);

  Sign s_D = CGAL::sign( D );
  Sign s_Dt = CGAL::sign( Dt );
  Sign s_Ds = CGAL::sign( Ds );

  Sign s_tdiff = CGAL::sign(Dt - D);
  Sign s_sdiff = CGAL::sign(Ds - D);

  Sign s_t = Sign(s_Dt * s_D);
  Sign s_s = Sign(s_Ds * s_D);

  Sign s_t_minus_1 = Sign(s_tdiff * s_D);
  Sign s_s_minus_1 = Sign(s_sdiff * s_D);

  if ( s_t == CGAL::NEGATIVE || s_t_minus_1 == CGAL::POSITIVE ||
       s_s == CGAL::NEGATIVE || s_s_minus_1 == CGAL::POSITIVE ) {
    //  t < 0 or t > 1 or s < 0 or s > 1
    return Enum::DISJOINT;
  }

  int it(0), is(0);
  if ( s_t == CGAL::ZERO ) {
    it = 0;
  } else if ( s_t_minus_1 == CGAL::ZERO ) {
    it = 1;
  } else {
    it = 2;
  }
  if ( s_s == CGAL::ZERO ) {
    is = 0;
  } else if ( s_s_minus_1 == CGAL::ZERO ) {
    is = 1;
  } else {
    is = 2;
  }

  if ( it == 0 ) {
    if ( is == 0 ) {
      return Enum::TOUCH_11;
    } else if ( is == 1 ) {
      return Enum::TOUCH_12;
    } else {
      return Enum::TOUCH_INTERIOR_12;
    }
  } else if ( it == 1 ) {
    if ( is == 0 ) {
      return Enum::TOUCH_21;
    } else if ( is == 1 ) {
      return Enum::TOUCH_22;
    } else {
      return Enum::TOUCH_INTERIOR_22;
    }
  } else {
    if ( is == 0 ) {
      return Enum::TOUCH_INTERIOR_11;
    } else if ( is == 1 ) {
      return Enum::TOUCH_INTERIOR_21;
    } else {
      return Enum::CROSSING;
    }
  }
}


//---------------------------------------------------------------------

template<class RT>
typename CGALi::Svd_arrangement_enum::Arrangement_type
svd_arrangement_type_parallel_C2(const RT& x1, const RT& y1,
				 const RT& x2, const RT& y2,
				 const RT& x3, const RT& y3,
				 const RT& x4, const RT& y4)
{
  typedef CGALi::Svd_arrangement_enum  Enum;

  RT D1 = det2x2_by_formula(x2 - x1, x3 - x1,
			    y2 - y1, y3 - y1);

  if ( CGAL::sign( D1 ) != CGAL::ZERO ) {
    return Enum::DISJOINT;
  }

  RT Dt3, Dt4, Dt;
  if ( CGAL::compare(x2, x1) != CGAL::EQUAL ) {
    Dt  = x2 - x1;
    Dt3 = x3 - x1;
    Dt4 = x4 - x1;
  } else {
    Dt  = y2 - y1;
    Dt3 = y3 - y1;
    Dt4 = y4 - y1;
  }

  Sign s_Dt = CGAL::sign( Dt );