arr_inc_insertion_zone_visitor.h

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

        {
          inserted_he = p_arr->insert_from_left_vertex (cv,
                                                        prev_he_left);
        }
        else
        {
          inserted_he = p_arr->insert_from_left_vertex (cv,
                                                        left_v);
        }
      }
      else
      {
        // Both endpoints are associated with arrangement vertices.
        // If possible, use the previous halfedges for both end vertices.
        if (prev_he_left != invalid_he && prev_he_right != invalid_he)
        {
          inserted_he = p_arr->insert_at_vertices (cv,
                                                   prev_he_left,
                                                   prev_he_right);
        }
        else if (prev_he_left != invalid_he)
        {
          inserted_he = p_arr->insert_at_vertices (cv,
                                                   prev_he_left,
                                                   right_v);
        }
        else if (prev_he_right != invalid_he)
        {
          inserted_he = p_arr->insert_at_vertices (cv,
                                                   prev_he_right,
                                                   left_v);

          // The returned halfedge is currently directed toward the left vertex
          // (instead of the right one), so we take its twin.
          inserted_he = inserted_he->twin();
        }
        else
        {
          inserted_he = p_arr->insert_at_vertices (cv,
                                                   left_v,
                                                   right_v);
        }
      }
    }
    else
    {
      // The left end is unbounded, but we know the fictitious halfedge that
      // contains it in its interior.
      CGAL_assertion (! left_bounded && 
                      prev_he_left != Halfedge_handle());

      if (! vertex_for_right)
      {
        // Check if the right end is also unbounded.
        const Boundary_type inf_x_right = 
          traits->boundary_in_x_2_object()(cv, MAX_END);
        const Boundary_type inf_y_right = 
          traits->boundary_in_y_2_object()(cv, MAX_END);

        if (inf_x_right == NO_BOUNDARY && inf_y_right == NO_BOUNDARY)
        {
          // The right end is bounded - we should insert the curve in the
          // interior of the unbounded face incident to prev_he_left.
          inserted_he = p_arr->insert_in_face_interior (cv,
                                                        prev_he_left);
        }
        else
        {
          // Both ends are unbounded - locate a halfedge that contains the
          // unbounded right end in its interior and perform the insertion.
          prev_he_right = arr_access.locate_along_ccb (prev_he_left->face(),
                                                       cv, MAX_END);

          inserted_he = p_arr->insert_in_face_interior (cv,
                                                        prev_he_left,
                                                        prev_he_right);
        }
      }
      else
      {
        // The right endpoint is associated with an arrangement vertex.
        // If possible, use the previous halfedge for the right vertex.
        if (prev_he_right != invalid_he)
        {
          inserted_he = p_arr->insert_from_right_vertex (cv,
                                                         prev_he_right,
                                                         prev_he_left);
        }
        else
        {
          inserted_he = p_arr->insert_from_right_vertex (cv,
                                                         right_v);
        }

        // The returned halfedge is directed to the newly created vertex
        // (the left one), so we take its twin.
        inserted_he = inserted_he->twin();
      }
    }

    // Return the inserted halfedge, and indicate we should not halt the
    // zone-computation process.
    Result    res = Result (inserted_he, false);

    return (res);
  }

  /*!
   * Handle the a subcurve that overlaps a given edge.
   * \param cv The overlapping subcurve.
   * \param he The overlapped halfedge (directed from left to right).
   * \param left_v The vertex that corresponds to the left endpoint of cv
   *               (or an invalid handle if no such arrangement vertex exists).
   * \param right_v The vertex that corresponds to the right endpoint of cv
   *               (or an invalid handle if no such arrangement vertex exists).
   * \return A handle to the halfedge obtained from the insertion of the
   *         overlapping subcurve into the arrangement.
   */
  Result found_overlap (const X_monotone_curve_2& cv,
                        Halfedge_handle he,
                        Vertex_handle left_v, Vertex_handle right_v)
  {
#ifdef ARR_INC_INSERT_DEBUG

    std::cout << "Found overlap: " << cv
              << "  with: " << he->curve() << std::endl;

    if (left_v != invalid_v)
      std::cout << "           v1 = " << left_v->point() << std::endl;

    if (right_v != invalid_v)
      std::cout << "           v2 = " << right_v->point() << std::endl;
#endif

    // Modify (perhaps split) the overlapping arrangement edge.
    Halfedge_handle   updated_he;

    if (left_v == invalid_v)
    {
      // Split the curve associated with he at the left endpoint of cv.
      traits->split_2_object() (he->curve(),
                                traits->construct_min_vertex_2_object() (cv),
                                sub_cv1, sub_cv2);

      if (right_v == invalid_v)
      {
        // The overlapping curve is contained strictly in the interior of he:
        // Split he as an intermediate step.
        updated_he = p_arr->split_edge (he,
                                        sub_cv1, sub_cv2);
        updated_he = updated_he->next();

        // Split the left subcurve at the right endpoint of cv.
        traits->split_2_object() (updated_he->curve(),
                                  traits->construct_max_vertex_2_object() (cv),
                                  sub_cv1, sub_cv2);

        // Split updated_he once again, so that the left portion corresponds
        // to the overlapping curve and the right portion corresponds to
        // sub_cv2.
        updated_he = p_arr->split_edge (updated_he,
                                        cv, sub_cv2);
      }
      else
      {
        // Split he, such that the left portion corresponds to sub_cv1 and the
        // right portion corresponds to the overlapping curve.
        updated_he = p_arr->split_edge (he,
                                        sub_cv1, cv);
        updated_he = updated_he->next();
      }
    }
    else
    {
      if (right_v == invalid_v)
      {
        // Split the curve associated with he at the right endpoint of cv.
        traits->split_2_object() (he->curve(),
                                  traits->construct_max_vertex_2_object() (cv),
                                  sub_cv1, sub_cv2);

        // Split he, such that the left portion corresponds to the overlapping
        // curve and the right portion corresponds to sub_cv2.
        updated_he = p_arr->split_edge (he,
                                        cv, sub_cv2);
      }
      else
      {
        // The entire edge is overlapped: Modify the curve associated with cv
        // to be the overlapping curve.
        updated_he = p_arr->modify_edge (he,
                                         cv);
      }
    }

    // Return the updated halfedge, and indicate we should not halt the
    // zone-computation process.
    Result    res = Result (updated_he, false);

    return (res);
  }

private:

  /*!
   * Split an arrangement edge.
   * \param he The edge to split (one of the twin halfedges).
   * \param p The split point.
   * \param arr_access An arrangement accessor.
   */
  void _split_edge (Halfedge_handle he,
                    const Point_2& p,
                    Arr_accessor<Arrangement_2>& arr_access)
  {
    // Split the curve at the split point.
    traits->split_2_object() (he->curve(),
                              p,
                              sub_cv1, sub_cv2);

    // Determine the order we send the split curves to the split_edge function,
    // depending whether the left point of sub_cv1 equals he's source (if not,
    // it equals its target).
    if (arr_access.are_equal (he->source(), sub_cv1, MIN_END))
    {
      arr_access.split_edge_ex (he,
                                p,
                                sub_cv1, sub_cv2);
    }
    else
    {
      arr_access.split_edge_ex (he,
                                p,
                                sub_cv2, sub_cv1);
    }

    return;
  }
};

CGAL_END_NAMESPACE

#endif