vertex_visibility_graph_2.h

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

#endif
            tree.set_left_sibling(p,q);
         }
         else
         {
            // NOTE: no need to check here if z is p_infinity since you are
            // moving DOWN the tree instead of up and p_infinity is at the root
            Turn_reverser<Point_2, Left_turn_2> right_turn(left_turn_2);

            while ((tree.rightmost_child(z) != tree.end()) &&
                   !right_turn(*p,*tree.rightmost_child(z),*z))
            {
               z = tree.rightmost_child(z);
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
               std::cout << "    z = " << *z << std::endl;
#endif
            }
            tree.set_rightmost_child(p,z);
            if (!stack.empty() && z == stack.top())
            {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
               std::cout << "popping " << *z << " from top of stack "
                         << std::endl;
#endif
               z = stack.top();
               stack.pop();
            }
         }
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << " p is now " << *p << std::endl;
#endif
         if (tree.left_sibling(p) == tree.end() && 
             !tree.parent_is_p_infinity(p))
         {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            std::cout << "pushing " << *p << std::endl;
#endif
            stack.push(p);
         }
         if (p_r != tree.end()) stack.push(p_r);
      }
//      print_edge_set(edges);
   }


   void clear()
   {
      edges.clear();
   }

   iterator begin()
   {
      return edges.begin();
   }

   const_iterator begin() const
   {
      return edges.begin();
   }

   const_iterator end() const
   {
      return edges.end();
   }

   iterator end()
   {
      return edges.end();
   }

   void insert_edge(const Point_pair& edge)
   {
      if (less_xy_2(edge.first,edge.second))
         edges.insert(edge);
      else
         edges.insert(Point_pair(edge.second, edge.first));
   }

   bool is_an_edge(const Point_pair& edge)
   {
      if (less_xy_2(edge.first,edge.second))
         return edges.find(edge) != edges.end();
      else 
         return edges.find(Point_pair(edge.second, edge.first)) != edges.end();
   }

#if 0
// ??? need to finish this ???
   template <class ForwardIterator>
   bool is_valid(ForwardIterator first, ForwardIterator beyond)
   {
      std::vector<Point_2> vertices(first, beyond);
      bool edge_there[vertices.size()];
   
      // for each edge in the graph determine if it is either an edge of the
      // polygon or, if not, if it intersects the polygon in the interior of
      // the edge.
      for (iterator e_it = edges.begin(); e_it != edges.end(); e_it++)
      {
         Segment_2 s = construct_segment_2((*e_it).first, (*e_it).second);
         if (is_an_edge(*e_it))
            edge_there[edge_num] = true;
         else if (do_intersect_in_interior(s, first, beyond))
         return false;
      }
      // check if all the edges of the polygon are present
      //
      // ??? how do you check if there are missing edges ???
   }
#endif


private:

   void print_vertex_map(const Vertex_map& vertex_map, 
                         const Polygon& polygon)
   {
      typedef typename Vertex_map::const_iterator    const_iterator;

      for (const_iterator it = vertex_map.begin(); it != vertex_map.end();it++)
      {
         if ((*it).second.second != polygon.end())
         std::cout << (*it).first << " sees " << *((*it).second.second) 
                   << std::endl;
      }
   }

   template<class E>
   void print_edge_set(const E& edges)
   {
      typedef typename E::iterator   iterator;
      for (iterator it = edges.begin(); it != edges.end(); it++)
      {
         std::cout << (*it).first << " " << (*it).second << std::endl;
      }
   }

   // want to determine, for each vertex p of the polygon, the line segment
   // immediately below it.  For vertical edges, the segment below is not the
   // one that begins at the other endpoint of the edge.
   void initialize_vertex_map(const Polygon& polygon, 
                              Vertex_map& vertex_map);

   // determines if one makes a left turn going from p to q to q's parent.
   // if q's parent is p_infinity, then a left turn is made when p's x value
   // is less than q's x value or the x values are the same and p's y value is
   // less than q's.
   // if p, q, and q's parent are collinear, then one makes a "left turn"
   // if q is between p and q's parent (since this means that p can't see 
   // q's parent and thus should not become a child of that node)
   bool left_turn_to_parent(Tree_iterator p, Tree_iterator q, Tree& tree);


   // returns true if q is the vertex after p
   bool is_next_to(const Polygon& polygon, Polygon_const_iterator p, 
                   Polygon_const_iterator q) const
   {
      Polygon_const_iterator next = p; next++;
      if (next == polygon.end()) next = polygon.begin();
      return (q == next);
   }

   // returns true if q is the vertex before or after p
   bool are_adjacent(const Polygon& polygon, Polygon_const_iterator p, 
                     Polygon_const_iterator q) const
   {
      Polygon_const_iterator next = p; next++;
      if (next == polygon.end()) next = polygon.begin();
      if (q == next) return true;
      next = q; next++;
      if (next == polygon.end()) next = polygon.begin();
      if (p == next) return true;
      return false;
   }

   // returns true if the diagonal from p to q cuts the interior angle at p
   bool diagonal_in_interior(const Polygon& polygon, 
                             Polygon_const_iterator p,
                             Polygon_const_iterator q);
 

   // returns true if the looker can see the point_to_see 
   bool point_is_visible(const Polygon& polygon, 
                         Polygon_const_iterator point_to_see, 
                         Vertex_map_iterator looker);
   
   void update_visibility(Vertex_map_iterator p_it,
                          Vertex_map_iterator q_it, 
                          const Polygon& polygon, int are_adjacent);

   void update_collinear_visibility(Vertex_map_iterator p_it,
                                    Vertex_map_iterator q_it, 
                                    const Polygon& polygon);

   // The segment between points p and q is a potential visibility edge
   // This function determines if the edge should be added or not (based
   // on p's current visibility point) and updates p's visibility point
   // where appropriate
   void handle(Tree_iterator p, Tree_iterator q, const Polygon& polygon,
               Vertex_map& vertex_map);

private:
   Left_turn_2                            left_turn_2;
   Orientation_2                         orientation_2;
   Collinear_are_ordered_along_line_2    collinear_ordered_2;
   Are_strictly_ordered_along_line_2     are_strictly_ordered_along_line_2;
   Less_xy_2                             less_xy_2;
   Construct_segment_2                   construct_segment_2;
   Construct_ray_2                       construct_ray_2;
   Intersect_2                           intersect_2;
   Assign_2                              assign_2;
   Edge_set                              edges;
};


#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
template <class Traits>
Indirect_less_xy_2<Traits>
Vertex_visibility_graph_2<Traits>::indirect_less_xy_2; 
#endif
}

#include <CGAL/Partition_2/Vertex_visibility_graph_2_impl.h>

#endif // CGAL_VERTEX_VISIBILITY_GRAPH_2_H