vertex_visibility_graph_2_impl.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_impl.h $
// $Id: Vertex_visibility_graph_2_impl.h 31311 2006-05-29 08:30:22Z wein $
// 
//
// Author(s)     : Susan Hert <[e-mail]>

namespace CGAL {


/*
// ??? need to finish this ???
template <class Traits>
template <class ForwardIterator>
bool 
Vertex_visibility_graph_2<Traits>::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 ???
}

*/

// 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.
template <class Traits>
void 
Vertex_visibility_graph_2<Traits>::initialize_vertex_map(
                              const Polygon& polygon, Vertex_map& vertex_map)
{
   typedef typename Vertex_map::value_type           Map_pair;

   // Create an event list that is a list of circulators for the polygon
   Iterator_list<Polygon_const_iterator>     
                           iterator_list(polygon.begin(), polygon.end());

   // Sort the event list (iterators to points) from left to right 
   // (using less_xy)
#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
   iterator_list.sort(&Self::compare);
#else
   iterator_list.sort(Indirect_less_xy_2<Traits>());
#endif
   // Create an ordered list of edge endpoints (iterators), initially empty
   typedef std::set< Point_pair, Segment_less_yx_2 > Ordered_edge_set;
   typedef typename Ordered_edge_set::iterator       Ordered_edge_set_iterator;

   Ordered_edge_set              ordered_edges;
   Ordered_edge_set_iterator     edge_it;
   Vertex_map_iterator   vm_it;
   Vertex_map_iterator   vis_it;

   Polygon_const_iterator event_it;
   Polygon_const_iterator next_endpt;
   Polygon_const_iterator prev_endpt;

   // initialize the map by associating iterators and points and indicating 
   // that no points can see anything.
   for (Polygon_const_iterator it = polygon.begin();it != polygon.end();it++)
   {
      vertex_map.insert(Map_pair(*it, Iterator_pair(it, polygon.end())));
   }
      
   // now go through the events in sorted order.  
   while (!iterator_list.empty())
   {
      event_it = iterator_list.front();
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
      std::cout << "event = " << *event_it << std::endl;     
#endif
      next_endpt = event_it; next_endpt++;
      if (next_endpt == polygon.end()) next_endpt = polygon.begin();
      iterator_list.pop_front();

      // the first edge that is not less than (below) this edge, so ...
      edge_it = ordered_edges.lower_bound(Point_pair(*event_it,*next_endpt));

      // ...if there is no edge below this one then nothing is visible,
      // otherwise....
      if (edge_it != ordered_edges.begin())
      {
         edge_it--; // ...the first visible edge is the previous edge

         // find the event point in the vertex map
         vm_it = vertex_map.find(*event_it);

         // Find the entry for the edge's first endpoint in the vertex map.
         vis_it = vertex_map.find((*edge_it).first);
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << "the potential visibility point is " << (*vis_it).first 
                   << endl;
#endif
         // an edge that ends at this event point cannot be below this 
         // endpoint
         if (!is_next_to(polygon, (*vis_it).second.first, event_it))
         {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            cout << "the edge beginning at  " << *(*vis_it).second.first 
                 << " is visible" << endl;
#endif
            // set the visibility iterator for this point to the iterator
            // corresponding to the edge endpoint that is to the left of
            // the vertical line
            if (less_xy_2((*vis_it).first,  (*vm_it).first))
            {
               Polygon_const_iterator next_vtx = (*vis_it).second.first;
               next_vtx++; 
               if (next_vtx == polygon.end()) next_vtx = polygon.begin();
               (*vm_it).second.second = next_vtx;
            }
            else
               (*vm_it).second.second = (*vis_it).second.first;
         }
         // skip over the edge that ends at this event point. If there 
         // is another edge above this event's edge then it is visible. 
         // since it can't also end at the event point.
         else if (edge_it != ordered_edges.begin() &&
                  --edge_it != ordered_edges.begin())
         {
            vis_it = vertex_map.find((*edge_it).first);
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            std::cout << "the edge beginning at  " << *(*vis_it).second.first 
                      << " is visible" << endl;
#endif
            // set the visibility iterator for this point to the iterator
            // corresponding to the edge endpoint that is to the left of
            // the vertical line
            if (less_xy_2((*vis_it).first,  (*vm_it).first))
            {
                Polygon_const_iterator next_vtx = (*vis_it).second.first;
                next_vtx++; 
                if (next_vtx == polygon.end()) next_vtx = polygon.begin();
                (*vm_it).second.second = next_vtx;
            }
            else
                (*vm_it).second.second = (*vis_it).second.first;
         }
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         else
            std::cout << "nothing is visible " << endl;
#endif
      }
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
      else
         cout << "nothing is visible " << endl;
#endif
      prev_endpt = event_it; 
      if (prev_endpt == polygon.begin()) 
         prev_endpt = polygon.end();
      prev_endpt--;
      // if the other endpoint of the next edge is to the right of the
      // sweep line, then insert this edge
      if (less_xy_2(*event_it, *next_endpt))
      {
         ordered_edges.insert(Point_pair(*event_it,*next_endpt));
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
             cout << "inserting edge from "
                  << *event_it << " to " << *next_endpt << endl;
#endif
      }
      else // other endpoint not to the right, so erase it 
      {
         ordered_edges.erase(Point_pair(*event_it,*next_endpt));
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << "erasing edge from "
                   << *event_it << " to " << *next_endpt << endl;
#endif
      }
      // if the other endpoint of the previous edge is to the right of the
      // sweep line, insert it
      if (less_xy_2(*event_it, *prev_endpt))
      {
         ordered_edges.insert(Point_pair(*prev_endpt,*event_it));
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         cout << "inserting edge from "
              << *prev_endpt << " to " << *event_it << endl;
#endif
       }
       else // other endpoint is not to the right, so erase it
       {
          ordered_edges.erase(Point_pair(*prev_endpt,*event_it));
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
          std::cout << "erasing edge from "
                    << *prev_endpt << " to " << *event_it << endl;
#endif
       }
   }
}

// 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)
template <class Traits>
bool 
Vertex_visibility_graph_2<Traits>::left_turn_to_parent(
                                   Tree_iterator p, 
                                   Tree_iterator q, 
                                   Tree& tree)
{
   if (tree.parent_is_p_infinity(q)) 
   {
      return (less_xy_2(*p, *q));
   }
   else if (orientation_2(*p, *q, *(*q).parent()) == COLLINEAR &&
            (collinear_ordered_2(*p, *q, *(*q).parent()) ||
             collinear_ordered_2(*p, *q, *(*q).parent())))
      
   {
      return true;
   }
   else
   {
      return left_turn_2(*p, *q, *(*q).parent());
   }
}

// returns true if the diagonal from p to q cuts the interior angle at p

template <class Traits>
bool 
Vertex_visibility_graph_2<Traits>::diagonal_in_interior(
                             const Polygon& polygon, 
                             Polygon_const_iterator p,
                             Polygon_const_iterator q)
{
   Turn_reverser<Point_2, Left_turn_2> right_turn(left_turn_2);
   Polygon_const_iterator before_p;
   if (p == polygon.begin())
      before_p = polygon.end();
   else 
      before_p = p;
   before_p--;
   Polygon_const_iterator after_p = p; after_p++;
   if (after_p == polygon.end()) after_p = polygon.begin();

   if (right_turn(*before_p, *p, *after_p))
   {
      if (right_turn(*before_p, *p, *q) && right_turn(*q, *p, *after_p))
         return false;
   }
   else // left turn or straight at vertex
   {
/*
      // p should not be able to see q through its own edge
      if (are_strictly_ordered_along_line(*p, *after_p, *q))
         return false;
*/
      if (right_turn(*before_p, *p, *q) || right_turn(*q, *p, *after_p))
         return false;
   }
   return true;
}
 

// returns true if the looker can see the point_to_see 
template <class Traits>
bool Vertex_visibility_graph_2<Traits>::point_is_visible(
                                           const Polygon& polygon, 
                                           Polygon_const_iterator point_to_see,
                                           Vertex_map_iterator looker)
{
   // Collect pointers to the current visibility segments for the looker
   // (the current visibility point and the two vertices flanking this vertex)
   Polygon_const_iterator vis_endpt = (*looker).second.second;
   Polygon_const_iterator next_vis_endpt = vis_endpt; next_vis_endpt++;
   if (next_vis_endpt == polygon.end()) next_vis_endpt = polygon.begin();
   Polygon_const_iterator prev_vis_endpt;
   if (vis_endpt == polygon.begin())
      prev_vis_endpt = polygon.end();
   else
      prev_vis_endpt = vis_endpt;
   prev_vis_endpt--;

#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
     cout << "looker is " << (*looker).first << " point to see is " 
          << *point_to_see;
     cout << " visibility points are prev: " << *prev_vis_endpt
          << " vis: " << *vis_endpt << " next: " << *next_vis_endpt << endl;
#endif

    // if the point to see is the current visibility point or if the looker 
    // and the point to see flank the old visibility point, they are visible 
    // to each other since it is known at this point that the edge from 
    // the looker to the point to see goes through the interior of the polygon
    if ((*looker).second.second == point_to_see)
        
    {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
       std::cout << "looker sees point" << std::endl;
#endif
       return true;
    }
    else if (((*looker).second.first == prev_vis_endpt && 
              point_to_see == next_vis_endpt) ||
             ((*looker).second.first == next_vis_endpt && 
              point_to_see == prev_vis_endpt))
    {
       if (orientation_2(*prev_vis_endpt, *vis_endpt, *next_vis_endpt) == 
           COLLINEAR &&
           (collinear_ordered_2((*looker).first, *vis_endpt, *point_to_see) ||
            collinear_ordered_2(*point_to_see, *vis_endpt, (*looker).first)))
       {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
          cout << "looker does NOT see point" << endl;
#endif
          return false;
       }
       else                      
       {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
          cout << "looker sees point" << endl;
#endif
          return true;
       }
    }
    else if ((*looker).second.first == prev_vis_endpt ||
             point_to_see == prev_vis_endpt)
    // point to see or looker is not adjacent to old visibility, so check 
    // intersection with next visibility segment
    {
       if (orientation_2(*vis_endpt, *next_vis_endpt, (*looker).first) !=
           orientation_2(*vis_endpt, *next_vis_endpt, *point_to_see) &&
           orientation_2((*looker).first, *point_to_see, *vis_endpt) !=
           orientation_2((*looker).first, *point_to_see, *next_vis_endpt))
       {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
          cout << "looker does NOT see point" << endl;