// Copyright (c) 2003,2004,2005 INRIA Sophia-Antipolis (France). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // You can redistribute it and/or modify it under the terms of the GNU // General Public License as published by the Free Software Foundation, // either version 3 of the License, or (at your option) any later version. // // 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. // // $URL$ // $Id$ // // // Author(s) : Menelaos Karavelas #ifndef CGAL_SEGMENT_DELAUNAY_GRAPH_SITE_H #define CGAL_SEGMENT_DELAUNAY_GRAPH_SITE_H #include #include #include #include namespace CGAL { /** A Site is either a point or a segment or a point defined as the intersection of two non-parallel segments (if defined) */ template class Segment_Delaunay_graph_site_2 { public: typedef Gt Geom_traits; typedef typename Geom_traits::Point_2 Point_2; typedef typename Geom_traits::Segment_2 Segment_2; protected: typedef typename Geom_traits::FT FT; typedef typename Geom_traits::RT RT; typedef Segment_Delaunay_graph_site_2 Self; public: Segment_Delaunay_graph_site_2() : type_(0) {} static Self construct_site_2(const Point_2& p) { Self t; t.initialize_site(p); return t; } // constructs segment site using the segment (p1,p2) static Self construct_site_2(const Point_2& p1, const Point_2& p2) { Self t; t.initialize_site(p1, p2); return t; } // constructs point site using the point of intersection of the // segments (p1,p2) and (q1,q2) static Self construct_site_2(const Point_2& p1, const Point_2& p2, const Point_2& q1, const Point_2& q2) { Self t; t.initialize_site(p1, p2, q1, q2); return t; } // constructs segment site using the points of intersection of the // segment-pairs (p1,p2)-(q1,q2) and (p1,p2)-(q3,q4) as endpoints; // the segment (p1,p2) is a segment that supports the actual segment static Self construct_site_2(const Point_2& p1, const Point_2& p2, const Point_2& q1, const Point_2& q2, const Point_2& r1, const Point_2& r2) { Self t; t.initialize_site(p1, p2, q1, q2, r1, r2); return t; } // constructs segment site using either the source or the target of // (p1,p2) (that depends on the boolean is_first_exact) and the // intersection of (p1,p2) with (q1,q2) as the other endpoint static Self construct_site_2(const Point_2& p1, const Point_2& p2, const Point_2& q1, const Point_2& q2, bool is_first_exact) { Self t; t.initialize_site(p1, p2, q1, q2, is_first_exact); return t; } public: bool is_defined() const { return type_ != 0; } bool is_point() const { return (type_ & 3) == 1; } bool is_segment() const { return (type_ & 3) == 2; } bool is_input() const { return !(type_ & 12); } bool is_input(unsigned int i) const { CGAL_precondition( is_segment() && i < 2 ); if ( i == 0 ) { return !(type_ & 4); } return !(type_ & 8); } const Point_2& source_of_supporting_site() const { CGAL_precondition( is_segment() ); return p_[0]; } const Point_2& target_of_supporting_site() const { CGAL_precondition( is_segment() ); return p_[1]; } const Point_2& source_of_supporting_site(unsigned int i) const { CGAL_precondition( is_point() && !is_input() ); return (i == 0) ? p_[2] : p_[4]; } const Point_2& target_of_supporting_site(unsigned int i) const { CGAL_precondition( is_point() && !is_input() ); return (i == 0) ? p_[3] : p_[5]; } const Point_2& source_of_crossing_site(unsigned int i) const { CGAL_precondition( is_segment() && !is_input(i) ); return (i == 0) ? p_[2] : p_[4]; } const Point_2& target_of_crossing_site(unsigned int i) const { CGAL_precondition( is_segment() && !is_input(i) ); return (i == 0) ? p_[3] : p_[5]; } Point_2 point() const { CGAL_precondition ( is_point() ); if ( !is_input() ) { return compute_intersection_point(p_[2], p_[3], p_[4], p_[5]); } else { return p_[0]; } } Segment_2 segment() const { CGAL_precondition ( is_segment() ); return Segment_2( source(), target() ); } Point_2 source() const { CGAL_precondition ( is_segment() ); return compute_source(); } Point_2 target() const { CGAL_precondition ( is_segment() ); return compute_target(); } Self supporting_site() const { CGAL_precondition( is_segment() ); return construct_site_2(p_[0], p_[1]); } Self supporting_site(unsigned int i) const { CGAL_precondition( is_point() && i < 2); CGAL_precondition( !is_input() ); if ( i == 0 ) { return construct_site_2(p_[2], p_[3]); } return construct_site_2(p_[4], p_[5]); } Self crossing_site(unsigned int i) const { CGAL_precondition( is_segment() && !is_input() ); CGAL_precondition( i < 2 && !is_input(i) ); if ( i == 0 ) { return construct_site_2(p_[2], p_[3]); } else { return construct_site_2(p_[4], p_[5]); } } Self source_site() const { CGAL_precondition( is_segment() ); if ( is_input() || is_input(0) ) { return construct_site_2(p_[0]); } else { return construct_site_2(p_[0], p_[1], p_[2], p_[3]); } } Self target_site() const { CGAL_precondition( is_segment() ); if ( is_input() || is_input(1) ) { return construct_site_2(p_[1]); } else { return construct_site_2(p_[0], p_[1], p_[4], p_[5]); } } protected: void initialize_site(const Point_2& p) { type_ = 1; p_[0] = p; } void initialize_site(const Point_2& p1, const Point_2& p2) { type_ = 2; p_[0] = p1; p_[1] = p2; } void initialize_site(const Point_2& p1, const Point_2& p2, const Point_2& q1, const Point_2& q2) { // MK: Sort the segments s1 and s2 in lexicographical order so // that the computation of the intersection point is always // done in the same manner (?) type_ = 5; p_[2] = p1; p_[3] = p2; p_[4] = q1; p_[5] = q2; } void initialize_site(const Point_2& p1, const Point_2& p2, const Point_2& q1, const Point_2& q2, const Point_2& r1, const Point_2& r2) { type_ = 14; p_[0] = p1; p_[1] = p2; p_[2] = q1; p_[3] = q2; p_[4] = r1; p_[5] = r2; } void initialize_site(const Point_2& p1, const Point_2& p2, const Point_2& q1, const Point_2& q2, bool is_first_exact) { type_ = (is_first_exact ? 10 : 6); p_[0] = p1; p_[1] = p2; if ( is_first_exact ) { p_[4] = q1; p_[5] = q2; } else { p_[2] = q1; p_[3] = q2; } } Point_2 compute_source() const { CGAL_precondition( is_segment() ); if ( is_input() || is_input(0) ) { return p_[0]; } else { return compute_intersection_point(p_[0], p_[1], p_[2], p_[3]); } } Point_2 compute_target() const { CGAL_precondition( is_segment() ); if ( is_input() || is_input(1) ) { return p_[1]; } else { return compute_intersection_point(p_[0], p_[1], p_[4], p_[5]); } } // computes the point of intersection of the segments p1p2 and p3p4 static Point_2 compute_intersection_point(const Point_2& p1, const Point_2& p2, const Point_2& p3, const Point_2& p4) { RT x1 = p1.x(), y1 = p1.y(); RT x2 = p2.x(), y2 = p2.y(); RT x3 = p3.x(), y3 = p3.y(); RT x4 = p4.x(), y4 = p4.y(); RT D = determinant(x2 - x1, x4 - x3, y2 - y1, y4 - y3); RT Dt = determinant(x3 - x1, x4 - x3, y3 - y1, y4 - y3); RT t = Dt / D; return Point_2(x1 + (x2 - x1) * t, y1 + (y2 - y1) * t); } protected: Point_2 p_[6]; char type_; }; //------------------------------------------------------------------------- template std::ostream& operator<<(std::ostream& os, const Segment_Delaunay_graph_site_2& s) { if (!s.is_defined()) return os << "u"; if (s.is_point()) return os << "p " << s.point (); return os << "s " << s.segment (); } template std::istream & operator>>(std::istream &is, Segment_Delaunay_graph_site_2& t) { typedef Segment_Delaunay_graph_site_2 Site_2; typedef typename Site_2::Point_2 Point_2; char type; if (is >> type) { if (type == 'p') { Point_2 p; is >> p; t = Site_2::construct_site_2(p); } else if (type == 's') { Point_2 p1, p2; is >> p1 >> p2; t = Site_2::construct_site_2(p1, p2); } } return is; } template < class R, class Stream > Stream& operator<<(Stream& str, Segment_Delaunay_graph_site_2& t) { if ( t.is_defined() ) { if ( t.is_point() ) { str << "p " << t.point(); } else { str << "s " << t.segment().source() << " " << t.segment().target(); } } return str; } } //namespace CGAL #endif // CGAL_SEGMENT_DELAUNAY_GRAPH_SITE_H