vertex_visibility_graph_2.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 2000  Max-Planck-Institute Saarbruecken (Germany).
// 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.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Partition_2/include/CGAL/Partition_2/Vertex_visibility_graph_2.h $
// $Id: Vertex_visibility_graph_2.h 36723 2007-03-01 10:44:59Z spion $
// 
//
// Author(s)     : Susan Hert <[e-mail]>

/*
    Provides an implementation of the algorithm of Overmars and Welzl
    for computing the visibility graph of a set of non-intersecting
    line segments in the plane.  

     @inproceedings{ow-nmcvg-88
     , author =      "M. H. Overmars and Emo Welzl"
     , title =       "New methods for computing visibility graphs"
     , booktitle =   "Proc. 4th Annu. ACM Sympos. Comput. Geom."
     , year =        1988
     , pages =       "164--171"
    }

    The running time is $O(n^2)$ with linear space requirements.

    The algorithm implemented uses a sweep-line technique to construct the
    visibility graph.  The sweep data structure is a rotation tree, implemented
    in the class CGAL::Rotation_tree_2.

    A direction vector $d$ is swept from $-\pi/2$ to $\pi/2$,
    and the sweep data structure, and whenever the direction of this vector
    coincides with the slope of an edge in the rotation tree, the tree $G$
    is updated and edges of the visibility graph are reported.  To accomplish
    the updates, it is necessary to keep track of all the leaves that are
    leftmost children of their parents.  In particular, one needs to know the
    rightmost of these leftmost children.
    
    Two data structures are needed for the implementation of the algorithm:
    the sweep data structure $G$, and a stack $S$ that contains all the
    leaves in $G$ that are the leftmost children of their parents.  

    TODO:
      --is_valid function is not complete
      --??? would a list of list of sorted vertices be a better representation?

 */

#ifndef  CGAL_VERTEX_VISIBILITY_GRAPH_2_H
#define  CGAL_VERTEX_VISIBILITY_GRAPH_2_H

#include <CGAL/Segment_2.h>
#include <CGAL/Partition_2/Rotation_tree_2.h>
#include <CGAL/Partition_2/Indirect_less_xy_2.h>
#include <CGAL/Partition_2/Iterator_list.h>
#include <CGAL/Partition_2/Turn_reverser.h>
#include <CGAL/Partition_2/Point_pair_less_xy_2.h>
#include <CGAL/Segment_2_Ray_2_intersection.h>
#include <CGAL/Partition_2/Segment_less_yx_2.h>
#include <cmath>
#include <list>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <iostream>

namespace CGAL {

template <class Traits>
class Vertex_visibility_graph_2 
{
private:
   typedef Vertex_visibility_graph_2<Traits>  Self;
   typedef typename Traits::Point_2           Point_2;
   typedef typename Traits::Segment_2         Segment_2;
   typedef typename Traits::Ray_2             Ray_2;
   typedef typename Traits::Object_2          Object_2;
   typedef typename Traits::Left_turn_2        Left_turn_2;
   typedef typename Traits::Less_xy_2         Less_xy_2;
   typedef typename Traits::Orientation_2     Orientation_2;
   typedef typename Traits::Collinear_are_ordered_along_line_2 
                                            Collinear_are_ordered_along_line_2;
   typedef typename Traits::Are_strictly_ordered_along_line_2 
                                            Are_strictly_ordered_along_line_2;
   typedef typename Traits::Construct_segment_2 
                                            Construct_segment_2; 
   typedef typename Traits::Construct_ray_2   Construct_ray_2; 
   typedef typename Traits::Intersect_2       Intersect_2; 
   typedef typename Traits::Assign_2          Assign_2; 
   typedef CGAL::Segment_less_yx_2<Traits>    Segment_less_yx_2;

   typedef Rotation_tree_2<Traits>            Tree;
   typedef typename Tree::iterator            Tree_iterator;

   typedef std::list< Point_2 >               Polygon;
   typedef typename Polygon::const_iterator   Polygon_const_iterator;
   typedef typename Polygon::iterator         Polygon_iterator;

   // the edge set is simply a set of point pairs.
   typedef std::pair<Point_2, Point_2>                Point_pair;
   typedef Point_pair_less_xy_2<Traits>               Point_pair_compare;
   typedef std::set< Point_pair, Point_pair_compare > Edge_set;

   // this map associates with each point (vertex), the iterator in the
   // original list that it originated from and its current visibility
   // point iterator. 
   typedef std::pair<Polygon_const_iterator, Polygon_const_iterator>   
                                               Iterator_pair;
   typedef std::map<Point_2, Iterator_pair, Less_xy_2>     Vertex_map;
   typedef typename Vertex_map::iterator                   Vertex_map_iterator;

public:
   typedef typename Edge_set::iterator                iterator;
   typedef typename Edge_set::const_iterator          const_iterator;


#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
  static Indirect_less_xy_2<Traits> indirect_less_xy_2;
  static bool compare(const Polygon_const_iterator& pit1, const Polygon_const_iterator& pit2)
  {
    return indirect_less_xy_2(pit1, pit2);
  }
#endif

   Vertex_visibility_graph_2()  {}

   //
   // first and beyond should be iterators over vertices of a polygon
   //
   template <class ForwardIterator>
   Vertex_visibility_graph_2(ForwardIterator first, ForwardIterator beyond):
     left_turn_2(Traits().left_turn_2_object()), 
     orientation_2(Traits().orientation_2_object()), 
     collinear_ordered_2(Traits().collinear_are_ordered_along_line_2_object()),
     are_strictly_ordered_along_line_2(
           Traits().are_strictly_ordered_along_line_2_object()),
     less_xy_2(Traits().less_xy_2_object()),
     construct_segment_2(Traits().construct_segment_2_object()),
     construct_ray_2(Traits().construct_ray_2_object()),
     intersect_2(Traits().intersect_2_object()),
     assign_2(Traits().assign_2_object())
   {
       build(first, beyond);
   }

   // Pre:  ccw order of points; no repeated points
   template <class ForwardIterator>
   void build(ForwardIterator first, ForwardIterator beyond)
   {
#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
      Polygon         polygon;

      for(ForwardIterator fit = first; fit != beyond; fit++){
	polygon.push_back(*fit);
      }
#else
      Polygon         polygon(first,beyond);
#endif
      Tree            tree(polygon.begin(), polygon.end());
   
      Vertex_map  vertex_map;
      initialize_vertex_map(polygon, vertex_map);
   
      // NOTE:  use the std::list as the basis here because otherwise the basis
      //        is a deque, which is buggy under MSVC++
      std::stack<Tree_iterator, std::list<Tree_iterator> > stack;
      // push on p_0, the rightmost point
      stack.push(tree.rightmost_point_ref());   
   
      Tree_iterator p, p_r, q;
      Tree_iterator z;

      while (!stack.empty())
      {
         p = stack.top();
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         if (p != tree.end())
            std::cout << "p = " << *p << std::endl;
         else
            std::cout << "p == NULL" << std::endl;
#endif
         stack.pop();
         p_r = tree.right_sibling(p);
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         if (p_r != tree.end())
            std::cout << "p_r = " << *p_r << std::endl;
         else
            std::cout << "p_r == NULL" << std::endl;
#endif
         q = tree.parent(p);
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         if (q != tree.end())
            std::cout << "q = " << *q << std::endl;
         else
            std::cout << "q == NULL" << std::endl;
#endif
         if (!tree.parent_is_p_minus_infinity(p))
         {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            std::cout << "q is not p_minus_infinity" << std::endl;
#endif
            handle(p,q,polygon,vertex_map);
         }
         z = tree.left_sibling(q);
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         if (z != tree.end())
            std::cout << "z = " << *z << std::endl;
         else
            std::cout << "z == NULL" << std::endl;
         std::cout << "erasing " << *p << " from tree " << std::endl;
#endif
         tree.erase(p);
         if ((z == tree.end()) || !left_turn_to_parent(p,z,tree))
         {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            std::cout << "making " << *p << " the left sibling of " << *q
                      << std::endl;