vertex_visibility_graph_2_impl.h

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

#endif
          return false;
       }
       else
       {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
          cout << "looker sees point" << endl;
#endif
         return true;
       }
    }
    else if ((*looker).second.first == next_vis_endpt ||
             point_to_see == next_vis_endpt)
    // point to see or looker is not adjacent to old visibility, so check 
    // intersection with previous visibility segment
    {
       if (orientation_2(*vis_endpt, *prev_vis_endpt, (*looker).first) !=
           orientation_2(*vis_endpt, *prev_vis_endpt, *point_to_see) &&
           orientation_2((*looker).first, *point_to_see, *vis_endpt) !=
           orientation_2((*looker).first, *point_to_see, *prev_vis_endpt))
       {
#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 
    // neither is adjacent to the old visibility point so check intersection
    // with both visibility segments
    {
       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;
#endif
         return false;
       }
       else if (orientation_2(*vis_endpt, *prev_vis_endpt, (*looker).first) !=
                orientation_2(*vis_endpt, *prev_vis_endpt, *point_to_see) &&
                orientation_2((*looker).first, *point_to_see, *vis_endpt) !=
                orientation_2((*looker).first, *point_to_see, *prev_vis_endpt))
       {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         cout << "looker does NOT see point" << endl;
#endif
         return false;
       }
       else // no intersection
       {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         cout << "looker sees point" << endl;
#endif
         return true;
       }
   }
}
   
template <class Traits>
void Vertex_visibility_graph_2<Traits>::update_visibility(
                                                      Vertex_map_iterator p_it,
                                                      Vertex_map_iterator q_it,
                                                      const Polygon& polygon,
                                                      int are_adjacent)
{
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
      std::cout << "updating visibility:  " << std::endl;
#endif
   Polygon_const_iterator prev_q; 
   Polygon_const_iterator turn_q; 
   if ((*q_it).second.first == polygon.begin()) 
      prev_q = polygon.end();
   else
      prev_q = (*q_it).second.first; 
   prev_q--;

   // determine if the vertex before or after q is the one that will
   // be encountered next when moving in the direction from p to q.
   if (prev_q == (*p_it).second.first)
   {
      turn_q = (*q_it).second.first; 
      turn_q++;
      if (turn_q == polygon.end()) turn_q = polygon.begin();
   }
   else
      turn_q = prev_q;

#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
   std::cout << "prev_q = " << *prev_q  << " turn_q = " << *turn_q 
             << std::endl;
#endif

   if (are_adjacent)
   {
      if (orientation_2((*p_it).first, (*q_it).first, *turn_q) == RIGHT_TURN)
      {
         (*p_it).second.second = (*q_it).second.second; // p sees what q sees
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << "adjacent with right turn; p now sees what q sees" 
                   << std::endl;
#endif
      }
      else // turn left or go straight
      {
         (*p_it).second.second = (*q_it).second.first;  // p sees q
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << "adjacent and NOT right turn; p now sees q " 
                   << std::endl;
#endif
      }
   }
   // if not adjacent, the edge was an interior one and so the "next" vertex
   // (the turn vertex) has to be the one that follows q.
   //
   // if Segment(q) == vis(p), i.e., p already sees q's segment
   else if ((*q_it).second.first == (*p_it).second.second ||
            prev_q == (*p_it).second.second)
   {
      turn_q = (*q_it).second.first; turn_q++;
      if (turn_q == polygon.end()) turn_q = polygon.begin();

#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
      std::cout << "prev_q = " << *prev_q  << " turn_q = " << *turn_q 
                << std::endl;
#endif
      // q sees nothing or there is not a right turn to the point after q
      if ((*q_it).second.second == polygon.end() || 
          orientation_2((*p_it).first, (*q_it).first, *turn_q) != RIGHT_TURN)
      {
         (*p_it).second.second = (*q_it).second.first; // p sees q
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << "p sees q's segment, q sees nothing and not right to "
                   << " next point; p sees q " << std::endl;
#endif
      }
      else
      {
         (*p_it).second.second = (*q_it).second.second; // p sees what q sees
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << "p sees q's segment, q sees something;"
                   << " p sees what q sees" << std::endl;
#endif 
      }
   }
   // Before(p,q,vis(p)) == true if q lies nearer to p than segment vis(p)
   // NOTE:  it is known that p is always looking to the right.
   else  if ((*p_it).second.second != polygon.end())  // if p sees something
   {
      Polygon_const_iterator next_v_p = (*p_it).second.second; next_v_p++;
      if (next_v_p == polygon.end()) next_v_p = polygon.begin();

      // don't need to do this for the previous visibility point since
      // if it were closer to p than q when looking from p to q, q would
      // not be visible.
      Segment_2 next_seg = construct_segment_2(*(*p_it).second.second, 
                                               *next_v_p);
      Ray_2 ray = construct_ray_2((*p_it).first, (*q_it).first);
      Segment_2 i_seg;
      Point_2 i_point;
         
      Object_2 next_result = intersect_2(next_seg, ray);
         
      if (assign_2(i_point, next_result)) 
      {
         if (collinear_ordered_2((*p_it).first, (*q_it).first, i_point))
         {
            (*p_it).second.second = (*q_it).second.first;
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            std::cout << "p sees something in direction of q, but q is closer;"
                      << " p sees q" << std::endl;
#endif 
         }
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         else 
         {
            std::cout << "p sees something in direction of q that's closer "
                      << "than q; p doesn't see  q" << std::endl;
         }
#endif 
      }
      else if (assign_2(i_seg, next_result))
      {
         if (collinear_ordered_2((*p_it).first,(*q_it).first,i_seg.source()) &&
             collinear_ordered_2((*p_it).first,(*q_it).first,i_seg.target()))
         {
            (*p_it).second.second = (*q_it).second.first;
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            std::cout << "p sees something in direction of q, but q is closer;"
                      << " p sees q" << std::endl;
#endif 
         }
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         else 
         {
            std::cout << "p sees something in direction of q that's closer "
                      << " than q; p doesn't see  q" << std::endl;
         }
#endif 
      }
      else
      {
         (*p_it).second.second = (*q_it).second.first;
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         std::cout << "p doesn't see something in direction of q; p sees q" 
                   << std::endl;
#endif 
      }
   }
   else // p sees what q sees
   {
      (*p_it).second.second = (*q_it).second.first;
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
      std::cout << "p sees nothing; p sees what q sees" << std::endl;
#endif 
   }
}

template <class Traits>
void Vertex_visibility_graph_2<Traits>::update_collinear_visibility(
                                                    Vertex_map_iterator p_it,
                                                    Vertex_map_iterator q_it,
                                                    const Polygon& polygon)
{
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
   std::cout << "updating collinear visibility" << std::endl;
#endif
   Polygon_const_iterator prev_q; 
   if ((*q_it).second.first == polygon.begin()) 
      prev_q = polygon.end();
   else
      prev_q = (*q_it).second.first;
   prev_q--;

   Polygon_const_iterator next_q = (*q_it).second.first; 
   next_q++;
   if (next_q == polygon.end()) next_q = polygon.begin();

#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
   std::cout << "q's neighbors are: prev " << *prev_q 
             << " q " << (*q_it).first 
             << " next " << *next_q << std::endl;
#endif

   // if the point before q is above the line containing p and q, make
   // this p's visibility point
   if (left_turn_2((*p_it).first, (*q_it).first, *prev_q))
   {
      if (point_is_visible(polygon, prev_q, p_it))
         (*p_it).second.second = prev_q;
   }
   // check the same thing for the point after q and, if it is still visible
   // (even after possibly updating the visibility in the above if) the
   // update again.
   if (left_turn_2((*p_it).first, (*q_it).first, *next_q))
   {
      if (point_is_visible(polygon, next_q, p_it))
         (*p_it).second.second = next_q;
   }
}

   // 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
template <class Traits>
void Vertex_visibility_graph_2<Traits>::handle(Tree_iterator p, 
                                        Tree_iterator q, 
                                        const Polygon& polygon,
                                        Vertex_map& vertex_map)
{
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
      std::cout << "Handling edge from " << (*p).x() << " " << (*p).y() 
                << " to " << (*q).x() << " " << (*q).y() << std::endl;
#endif
   Vertex_map_iterator p_it = vertex_map.find(*p);
   Vertex_map_iterator q_it = vertex_map.find(*q);
   CGAL_assertion (p_it != vertex_map.end());
   CGAL_assertion (q_it != vertex_map.end());
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
   std::cout << "p currently sees : ";
   if ((*p_it).second.second != polygon.end())
      std::cout << *((*p_it).second.second) << endl;
   else
      std::cout << " NADA" << endl;
#endif

   // if p and q are adjacent
   if (are_adjacent(polygon, (*p_it).second.first, (*q_it).second.first))
   {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
      cout << "are adjacent" << endl;
#endif
      insert_edge(Point_pair(*p,*q));
      update_visibility(p_it, q_it, polygon, 1);
   }
   else 
   {
      bool interior_at_p = diagonal_in_interior(polygon, (*p_it).second.first,
                                                (*q_it).second.first);
      bool interior_at_q = diagonal_in_interior(polygon, (*q_it).second.first,
                                                (*p_it).second.first);
      // line of site is through the interior of the polygon
      if (interior_at_p && interior_at_q)
      {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
         cout << "both interior" << endl;
#endif
         // if p sees something and q is visible only through collinear
         // points then update p's visibility if one of the points adjacent
         // to q is above the line unless p's current visibility point 
         // obscures the view.
         if ((*p_it).second.second != polygon.end() &&
             are_strictly_ordered_along_line_2((*p_it).first,
                                             *(*p_it).second.second,
                                                (*q_it).first))
         {
            update_collinear_visibility(p_it, q_it, polygon);
         }
         // p current sees nothing or q is visible to p
         else if ((*p_it).second.second == polygon.end() ||
                  point_is_visible(polygon, (*q_it).second.first, p_it))
         {
            insert_edge(Point_pair(*p,*q));
            update_visibility(p_it, q_it, polygon, 0);
         }
      }
      else if (!interior_at_p && !interior_at_q) // both points exterior
      {
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
            cout << "both exterior" << endl;
#endif
         // p currently sees nothing or q is visible to p
         if ((*p_it).second.second == polygon.end() ||
             point_is_visible(polygon, (*q_it).second.first, p_it))
         {
            (*p_it).second.second = (*q_it).second.first;
         }
      }
   }
#ifdef CGAL_VISIBILITY_GRAPH_DEBUG
   std::cout << "p now sees : ";
   if ((*p_it).second.second != polygon.end())
      std::cout << *((*p_it).second.second) << endl;
   else
      std::cout << " NADA" << endl;
#endif
}

}